-
Notifications
You must be signed in to change notification settings - Fork 3
/
node.h
159 lines (132 loc) · 4.31 KB
/
node.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
// (C) 2011, Marius Posta ([email protected])
// Check LICENSE.txt for the legal blah-blah.
#ifndef NODE_H
#define NODE_H
// Include the correct BTT wrapper header,
#include "instance.h"
#ifdef __cplusplus
// compiling in c++ (e.g. g++)
#include "BTT//bundle_solver.hpp"
#else
// compiling in c99 (e.g. clang)
#include "BTT//bundle_solver.h"
#endif
// Adjustable array data structure
typedef struct
{
void **e;
int n;
int alloc_size;
int alloc_size_increment;
} adj_array_t;
adj_array_t *adj_array_create (int alloc_size_increment);
void adj_array_destroy (adj_array_t *adj_array);
void adj_array_push (adj_array_t *adj_array, void *e);
void *adj_array_pop (adj_array_t *adj_array);
// Branch-and-bound search tree node data structure
typedef struct node_t node_t;
struct node_t
{
node_t *left, *right; // subnodes
int min_open, max_open; // minimum and maximum number of open locations
word_t *fix_mask; // n-bit-vector of fixed locations, mask
word_t *fix_val; // n-bit-vector of fixed locations, value
double *mul; // best multipliers
double lb, ub; // lower and upper bounds
int branch_i; // branching location
int id; // node number (low is old, high is recent)
};
node_t *node_alloc (instance_t *inst);
void node_set (instance_t *inst, node_t *parent, node_t *node); // in-place copy
void node_destroy (node_t *node);
void node_create_children (instance_t *inst, node_t *parent); // creates parent->left and parent->right
// Heap functions
void heap_sift_down (adj_array_t *h_node, int root, enum node_selection_t strategy);
void heap_sift_up (adj_array_t *h_node, int current, enum node_selection_t strategy);
// Node evaluation data structures
typedef struct node_eval_t node_eval_t;
// Subgradient cache element data structure
typedef struct
{
long min_open, max_open, n_x1;
unsigned long x_hash, fixed_x_hash, subg_hash;
word_t *x;
word_t *fixed_x;
double *subg;
long double eps0;
} hyperplane_t;
// Argument to BTT callback functions
typedef struct
{
struct bundle_callbacks callbacks;
node_t *node;
node_eval_t *node_eval;
} bundle_callback_data_t;
struct node_eval_t // stores everything necessary for node evaluation
{
instance_t *inst;
// statistical counters
int node_counter;
int n_node_eval;
int n_lag_eval;
// bundle-related stuff
char *bundle_cfg;
bundle_callback_data_t cbdata;
bundle_solver_t *bundle;
double *bundle_mul;
double *bundle_mul_alloc;
double *bundle_subg;
int bundle_max_gi;
int bundle_n_gi;
int bundle_n_fi;
// lag. relax. evaluation related stuff
double z;
double *rc;
int *x;
int *int_subg;
int *x1;
int n_x1;
int n_fixed_0, n_fixed_1;
ic_pair_t *queue;
double *min_c;
// impl. br. related stuff
int *partition;
int *I1;
int *Is;
int *I0;
double z_b0, z_b1;
// subgradient cache and bloom filter related stuff
hyperplane_t current_hyperplane;
hyperplane_t *cache;
ic_pair_t *selection;
int n_selected;
int fresh_idx;
unsigned short *bloom;
int bloom_size;
unsigned long *hash_salt;
int n_hash_salt;
// misc.
RngStream rng;
};
node_eval_t *node_eval_create (instance_t *inst);
void node_eval_reset (node_eval_t *node_eval, double approx_z);
void node_eval_destroy (node_eval_t *node_eval);
// Lagragian relaxation evaluation
int node_eval_lagrangian_fixed (node_eval_t *node_eval, node_t *node, double *mul);
double node_eval_lagrangian (node_eval_t *node_eval, node_t *node, double *mul);
// Bundle search & BTT callbacks
int node_eval_improve_mul (node_eval_t *node_eval, node_t *node, int max_subg, double ub);
double bundle_eval (struct bundle_callbacks *callbacks_ptr, const double *Lam_val, const unsigned *Lam_idx, unsigned Lam_count);
int bundle_get_subg (struct bundle_callbacks *callbacks_ptr, double *Eps, const unsigned **Indices);
void bundle_set_subg (struct bundle_callbacks *callbacks_ptr, double *subgradient, unsigned );
// Subgradient cache & Bloom filter functions
void select_hyperplanes_in_cache (node_eval_t *node_eval, node_t *node);
unsigned long get_hash_x (word_t *x, int n_words);
unsigned long get_hash_subg (int *subg, int m);
int check_bloom_filter (node_eval_t *node_eval);
void add_bloom_filter (node_eval_t *node_eval, short val);
// SSE intrinsics
double clamped_sum (double * x, double * y, size_t count);
void initialize_count (int * z, size_t count, int value);
void clamped_count (int * z, double * x, double * y, size_t count);
#endif