- Main Page
- Related Pages
- Modules
- Namespaces
- Classes
- Files

- File List
- File Members

Cgl012cut.hpp
Go to the documentation of this file.
1 // $Id: Cgl012cut.hpp 1149 2013-10-21 18:23:53Z tkr $
2 // Copyright (C) 2010, International Business Machines
3 // Corporation and others. All Rights Reserved.
4 // This code is licensed under the terms of the Eclipse Public License (EPL).
6 #ifndef CGL012CUT
7 #define CGL012CUT
8 #include <cstdio>
9 #include <cstdlib>
10 #include <cmath>
11
12 #define CGL_NEW_SHORT
13 #ifndef CGL_NEW_SHORT
14 typedef /* arc */
15 struct arc_st
16 {
17 int len; /* length of the arc */
18 struct node_st *head; /* head node */
19 }
20 arc;
21
22 typedef /* node */
23 struct node_st
24 {
25 arc *first; /* first outgoing arc */
26 int dist; /* tentative shortest path length */
27 struct node_st *parent; /* parent pointer */
28 struct node_st *next; /* next node in queue */
29 struct node_st *prev; /* previous node in queue */
30 int status; /* status of node */
31 int temp; /* for temporary labels */
32 int index; /* index of the node in the graph */
33 } node;
34 #endif
35 typedef struct
36 {
37 int length; // Length of arc
38 int to; // To node
39 } cgl_arc;
40
41 typedef struct
42 {
43 cgl_arc * firstArc; // First outgoing arc
44 int parentNode; // Parent node in shortest path
45 int index; // Which node I am
46 int distanceBack; // Distance back to source
47 } cgl_node;
48
49 typedef struct
50 {
51 int nnodes; // Number of nodes in graph
52 int narcs; // Number of arcs in graph
53 cgl_node * nodes;
54 cgl_arc * arcs;
55 } cgl_graph;
56 /* #define PRINT */
57 /* #define PRINT_CUTS */
58 #define REDUCTION
59
60 typedef struct {
61 int mr; /* number of rows in the ILP matrix */
62 int mc; /* number of columns in the ILP matrix */
63 int mnz; /* number of nonzero's in the ILP matrix */
64 int *mtbeg; /* starting position of each row in arrays mtind and mtval */
65 int *mtcnt; /* number of entries of each row in arrays mtind and mtval */
66 int *mtind; /* column indices of the nonzero entries of the ILP matrix */
67 int *mtval; /* values of the nonzero entries of the ILP matrix */
68 int *vlb; /* lower bounds on the variables */
69 int *vub; /* upper bounds on the variables */
70 int *mrhs; /* right hand sides of the constraints */
71 char *msense; /* senses of the constraints: 'L', 'G' or 'E' */
72 const double *xstar; /* current optimal solution of the LP relaxation */
73 } ilp;
74
75 typedef struct {
76 int mr; /* number of rows in the parity ILP matrix */
77 int mc; /* number of columns in the parity ILP matrix */
78 int mnz; /* number of 1's in the parity ILP matrix */
79 int *mtbeg; /* starting position of each row in arrays mtind and mtval */
80 int *mtcnt; /* number of entries of each row in arrays mtind and mtval */
81 int *mtind; /* column indices of the 1's of the parity ILP matrix */
82 short int *mrhs; /* right hand side parity of the constraints */
83 double *xstar; /* current optimal solution of the LP relaxation */
84 double *slack; /* slack of the constraints w.r.t. xstar */
85 short int *row_to_delete; /* flag for marking rows not to be considered */
86 short int *col_to_delete; /* flag for marking columns not to be considered */
87 int *gcd; /* greatest common divisor of each row in the input ILP matrix */
88 short int *possible_weak; /* possible weakening types of each column */
89 short int *type_even_weak; /* type of even weakening of each column
90 (lower or upper bound weakening) */
91 short int *type_odd_weak; /* type of odd weakening of each column
92 (lower or upper bound weakening) */
93 double *loss_even_weak; /* loss for the even weakening of each column */
94 double *loss_odd_weak; /* loss for the odd weakening of each column */
95 double *min_loss_by_weak; /* minimum loss for the weakening of each column */
96 } parity_ilp;
97
98 typedef struct {
99 int nweak; /* number of variables weakened */
100 int *var; /* list of variables weakened */
101 short int *type; /* type of weakening (lower or upper bound weakening) */
102 } info_weak;
103
104 typedef struct {
105 int endpoint1, endpoint2; /* endpoints of the edge */
106 double weight; /* edge weight */
107 short int parity; /* edge parity (even or odd) */
108 int constr; /* constraint associated with the edge */
109 info_weak *weak; /* weakening information */
110 } edge;
111
112 typedef struct {
113 int nnodes; /* number of nodes */
114 int nedges; /* number of edges */
115 int *nodes; /* indexes of the ILP columns corresponding to the nodes */
116 int *ind; /* indexes of the nodes corresponding to the ILP columns */
117 edge **even_adj_list; /* pointers to the even edges */
118 edge **odd_adj_list; /* pointers to the odd edges */
119 } separation_graph;
120
121 #ifndef CGL_NEW_SHORT
122 typedef struct {
123 int nnodes; /* number of nodes */
124 int narcs; /* number of arcs */
125 node *nodes; /* array of the nodes - see "types_db.h" */
126 arc *arcs; /* array of the arcs - see "types_db.h" */
127 } auxiliary_graph;
128 #else
129 typedef struct {
130 int nnodes; /* number of nodes */
131 int narcs; /* number of arcs */
132 cgl_node *nodes; /* array of the nodes - see "types_db.h" */
133 cgl_arc *arcs; /* array of the arcs - see "types_db.h" */
134 } auxiliary_graph;
135 #endif
136
137 typedef struct {
138 long dist; /* distance from/to root */
139 int pred; /* index of the predecessor */
140 } short_path_node;
141
142 typedef struct {
143 double weight; /* overall weight of the cycle */
144 int length; /* number of edges in the cycle */
145 edge **edge_list; /* list of edges in the cycle */
146 } cycle;
147
148 typedef struct {
149 int cnum; /* overall number of cycles */
150 cycle **list; /* pointers to the cycles in the list */
151 } cycle_list;
152
153 typedef struct {
154 int n_of_constr; /* number of constraints combined to get the cut */
155 int *constr_list; /* list of the constraints combined */
156 short int *in_constr_list; /* flag saying whether a given constraint is
157 in the list of constraints of the cut (IN)
158 or not (OUT) */
159 int cnzcnt; /* overall number of nonzero's in the cut */
160 int *cind; /* column indices of the nonzero entries of the cut */
161 int *cval; /* values of the nonzero entries of the cut */
162 int crhs; /* right hand side of the cut */
163 char csense; /* sense of the cut: 'L', 'G' or 'E' */
164 double violation; /* violation of the cut w.r.t. the current LP solution */
165 } cut;
166
167 typedef struct {
168 int cnum; /* overall number of cuts */
169 cut **list; /* pointers to the cuts in the list */
170 } cut_list;
171
172 typedef struct {
173 int n_of_constr; /* number of constraints combined to get the cut */
174 int *constr_list; /* list of the constraints combined */
175 int code; /* identifier of the cut */
176 int n_it_violated; /* number of consecutive iterations (starting from the
177 last and going backward) in which the cut was
178 violated by the LP solution */
179 int it_found; /* iteration in which the cut was separated */
180 double score; /* score of the cut, used to choose wich cut should be
181 added to the current LP (if any) */
182 } pool_cut;
183
184 typedef struct {
185 int cnum; /* overall number of cuts */
186 pool_cut **list; /* pointers to the cuts in the list */
187 int *ncod; /* number of cuts with a given code in the pool */
188 } pool_cut_list;
189
190 typedef struct {
191 int *ccoef; /* coefficients of the cut */
192 int crhs; /* right hand side of the cut */
193 int pool_index; /* index of the cut in the pool */
194 double score; /* cut score (to be maximized) */
195 } select_cut;
196
197 typedef struct {
198 int n_it_zero; /* number of consecutive iterations (starting from the
199 last and going backward) in which each variable took
200 the value 0 in the LP solution */
201 } log_var;
207 class Cgl012Cut {
208
209 public:
210
213 int sep_012_cut(
214 /*
215 INPUT parameters:
216 */
217 int mr, /* number of rows in the ILP matrix */
218 int mc, /* number of columns in the ILP matrix */
219 int mnz, /* number of nonzero's in the ILP matrix */
220 int *mtbeg, /* starting position of each row in arrays mtind and mtval */
221 int *mtcnt, /* number of entries of each row in arrays mtind and mtval */
222 int *mtind, /* column indices of the nonzero entries of the ILP matrix */
223 int *mtval, /* values of the nonzero entries of the ILP matrix */
224 int *vlb, /* lower bounds on the variables */
225 int *vub, /* upper bounds on the variables */
226 int *mrhs, /* right hand sides of the constraints */
227 char *msense, /* senses of the constraints: 'L', 'G' or 'E' */
228 const double *xstar, /* current optimal solution of the LP relaxation */
229 bool aggressive, /* flag asking whether as many cuts as possible are
230 required on output (TRUE) or not (FALSE) */
231 /*
232 OUTPUT parameters (the memory for the vectors is allocated INTERNALLY
233 by the procedure: if some memory is already allocated, it is FREED):
234 */
235 int *cnum, /* number of violated 0-1/2 cuts identified by the procedure */
236 int *cnzcnt, /* overall number of nonzero's in the cuts */
237 int **cbeg, /* starting position of each cut in arrays cind and cval */
238 int **ccnt, /* number of entries of each cut in arrays cind and cval */
239 int **cind, /* column indices of the nonzero entries of the cuts */
240 int **cval, /* values of the nonzero entries of the cuts */
241 int **crhs, /* right hand sides of the cuts */
242 char **csense /* senses of the cuts: 'L', 'G' or 'E' */
243 /*
244 NOTE that all the numerical input/output vectors are INTEGER (with
245 the exception of xstar), since the procedure is intended to work
246 with pure ILP's, and that the ILP matrix has to be given on input
247 in ROW format.
248 */
249 );
250 void ilp_load(
251 int mr, /* number of rows in the ILP matrix */
252 int mc, /* number of columns in the ILP matrix */
253 int mnz, /* number of nonzero's in the ILP matrix */
254 int *mtbeg, /* starting position of each row in arrays mtind and mtval */
255 int *mtcnt, /* number of entries of each row in arrays mtind and mtval */
256 int *mtind, /* column indices of the nonzero entries of the ILP matrix */
257 int *mtval, /* values of the nonzero entries of the ILP matrix */
258 int *vlb, /* lower bounds on the variables */
259 int *vub, /* upper bounds on the variables */
260 int *mrhs, /* right hand sides of the constraints */
261 char *msense /* senses of the constraints: 'L', 'G' or 'E' */
262 );
263 void free_ilp();
264 /* alloc_parity_ilp: allocate the memory for the parity ILP data structure */
265
266 void alloc_parity_ilp(
267 int mr, /* number of rows in the ILP matrix */
268 int mc, /* number of columns in the ILP matrix */
269 int mnz /* number of nonzero's in the ILP matrix */
270 );
271 void free_parity_ilp();
272 void initialize_log_var();
273 /* free_log_var */
274 void free_log_var();
275 private:
276 /* best_weakening: find the best upper/lower bound weakening of a set
277 of variables */
278
279 int best_weakening(
280 int n_to_weak, /* number of variables to weaken */
281 int *vars_to_weak, /* indices of the variables to weaken */
282 short int original_parity, /* original parity of the constraint to weaken */
283 double original_slack, /* original slack of the constraint to weaken */
284 double *best_even_slack, /* best possible slack of a weakened constraint
285 with even right-hand-side */
286 double *best_odd_slack, /* best possible slack of a weakened constraint
287 with odd right-hand-side */
288 info_weak **info_even_weak, /* weakening information about the best possible
289 even weakened constraint */
290 info_weak **info_odd_weak, /* weakening information about the best possible
291 odd weakened constraint */
292 short int only_odd, /* flag which tells whether only an odd weakening is of
293 interest (TRUE) or both weakenings are (FALSE) */
294 short int only_viol /* flag which tells whether only an inequality of
295 slack smaller than MAX_SLACK is of interest (TRUE)
296 otherwise (FALSE) */
297 );
298
299 /* best_cut: find the coefficients, the rhs and the violation of the
300 best possible cut that can be obtained by weakening a given set of
301 coefficients to even and a rhs to odd, dividing by 2 and rounding */
302
303 short int best_cut(
304 int *ccoef, /* vector of the coefficients */
305 int *crhs, /* pointer to rhs value */
306 double *violation, /* violation of the cut */
307 short int update, /* TRUE/FALSE: if TRUE, the new ccoef and crhs are
308 given on output */
309 short int only_viol /* flag which tells whether only an inequality of
310 slack smaller than MAX_SLACK is of interest (TRUE)
311 otherwise (FALSE) */
312 );
313 /* get_cut: extract a hopefully violated cut from an odd cycle of the
314 separation graph */
315
316 cut *get_cut(
317 cycle *s_cyc /* shortest odd cycles identified in the separation graph */
318 );
319
320 /* update_log_var: update the log information for the problem variables */
321 void update_log_var();
322
323 /* basic_separation: try to identify violated 0-1/2 cuts by using the
324 original procedure described in Caprara and Fischetti's MP paper */
325
326 cut_list *basic_separation();
327
328 /* score_by_moving: compute the score of the best cut obtainable from
329 the current local search solution by inserting/deleting a constraint */
330
331 double score_by_moving(
332 int i, /* constraint to be moved */
333 short int itype, /* type of move - ADD or DEL */
334 double thresh /* minimum value of an interesting score */
335 );
336 /* modify_current: update the current local search solution by inserting/
337 deleting a constraint */
338
339 void modify_current(
340 int i, /* constraint to be moved */
341 short int itype /* type of move - ADD or DEL */
342 );
343
344 /* best neighbour: find the cut to be added/deleted from the current
345 solution among those allowed by the tabu rules */
346
347 short int best_neighbour(cut_list *out_cuts /* list of the violated cuts found */);
348
349 /* add_tight_constraint: initialize the current cut by adding a tight
350 constraint to it */
351
352 void add_tight_constraint();
353
354 /* tabu_012: try to identify violated 0-1/2 cuts by a simple tabu search
355 procedure adapted from that used by Battiti and Protasi for finding
356 large cliques */
357
358 cut_list *tabu_012();
359 /* initialize: initialize the data structures for local search */
360
361 void initialize();
362 /* restart: perform a restart of the search - IMPORTANT: in the current
363 implementation vector last_moved is not cleared at restart */
364
365 void restart(short int failure /* flag forcing the restart if some trouble occurred */);
366 void print_constr(int i /* constraint to be printed */);
367 void print_parity_ilp();
368
369 /* get_parity_ilp: construct an internal data structure containing all the
370 information which can be useful for 0-1/2 cut separation */
371
372 void get_parity_ilp();
373 /* initialize_sep_graph: allocate and initialize the data structure
374 to contain the information associated with a separation graph */
375
376 separation_graph *initialize_sep_graph();
377 void print_cut(cut *v_cut);
378 /* get_ori_cut_coef: get the coefficients of a cut, before dividing by 2 and
379 rounding, starting from the list of the constraints combined to get
380 the cut */
381
382 short int get_ori_cut_coef(
383 int n_of_constr, /* number of constraints combined */
384 int *constr_list, /* list of the constraints combined */
385 int *ccoef, /* cut left hand side coefficients */
386 int *crhs, /* cut right hand side */
387 short int only_viol /* flag which tells whether only an inequality of
388 slack smaller than MAX_SLACK is of interest (TRUE)
389 otherwise (FALSE) */
390 );
391 /* define_cut: construct a cut data structure from a vector of
392 coefficients and a right-hand-side */
393
394 cut *define_cut(
395 int *ccoef, /* coefficients of the cut */
396 int crhs /* right hand side of the cut */
397 );
398
399 /* cut_score: define the score of a (violated) cut */
400
401 double cut_score(
402 int *ccoef, /* cut left hand side coefficients */
403 int crhs, /* cut right hand side */
404 double viol, /* cut violation */
405 short int only_viol /* flag which tells whether only an inequality of
406 slack smaller than MAX_SLACK is of interest (TRUE)
407 otherwise (FALSE) */
408 );
409 /* get_current_cut: return a cut data type with the information about
410 the current cut of the search procedure */
411
412 cut *get_current_cut();
413 /* print_cur_cut: display cur_cut on output */
414
415 void print_cur_cut();
416 void print_cut_list(cut_list *cuts);
418 public:
421 Cgl012Cut ();
423
425 Cgl012Cut (
426 const Cgl012Cut &);
427
429 Cgl012Cut &
430 operator=(
431 const Cgl012Cut& rhs);
432
434 virtual ~Cgl012Cut ();
436
437 private:
438
439 // Private member methods
440
443
444
445
448
449 ilp *inp_ilp; /* input ILP data structure */
450 parity_ilp *p_ilp; /* parity ILP data structure */
451 int iter;
452 double gap;
453 double maxgap;
454 int errorNo;
455 int sep_iter; /* number of the current separation iteration */
456 log_var **vlog; /* information about the value attained
457 by the variables in the last iterations,
458 used to possibly set to 0 some coefficient
459 > 0 in a cut to be added */
460 bool aggr; /* flag saying whether as many cuts as possible are required
461 from the separation procedure (TRUE) or not (FALSE) */
463 };
464 #endif
Cgl012Cut::free_parity_ilp
void free_parity_ilp()
info_weak::nweak
int nweak
Definition: Cgl012cut.hpp:99
cgl_graph
Definition: Cgl012cut.hpp:49
Cgl012Cut::errorNo
int errorNo
Definition: Cgl012cut.hpp:454
cgl_graph::narcs
int narcs
Definition: Cgl012cut.hpp:52
pool_cut_list
Definition: Cgl012cut.hpp:184
log_var::n_it_zero
int n_it_zero
Definition: Cgl012cut.hpp:198
ilp::mr
int mr
Definition: Cgl012cut.hpp:61
pool_cut::n_it_violated
int n_it_violated
Definition: Cgl012cut.hpp:176
separation_graph::even_adj_list
edge ** even_adj_list
Definition: Cgl012cut.hpp:117
parity_ilp::min_loss_by_weak
double * min_loss_by_weak
Definition: Cgl012cut.hpp:95
separation_graph::nnodes
int nnodes
Definition: Cgl012cut.hpp:113
short_path_node
Definition: Cgl012cut.hpp:137
Cgl012Cut::sep_012_cut
int sep_012_cut(int mr, int mc, int mnz, int *mtbeg, int *mtcnt, int *mtind, int *mtval, int *vlb, int *vub, int *mrhs, char *msense, const double *xstar, bool aggressive, int *cnum, int *cnzcnt, int **cbeg, int **ccnt, int **cind, int **cval, int **crhs, char **csense)
parity_ilp::loss_odd_weak
double * loss_odd_weak
Definition: Cgl012cut.hpp:94
Cgl012Cut::vlog
log_var ** vlog
Definition: Cgl012cut.hpp:456
cgl_node::parentNode
int parentNode
Definition: Cgl012cut.hpp:44
cgl_arc
Definition: Cgl012cut.hpp:35
edge
Definition: Cgl012cut.hpp:104
pool_cut_list::list
pool_cut ** list
Definition: Cgl012cut.hpp:186
Cgl012Cut::initialize
void initialize()
Cgl012Cut::free_ilp
void free_ilp()
cut_list::list
cut ** list
Definition: Cgl012cut.hpp:169
ilp::mrhs
int * mrhs
Definition: Cgl012cut.hpp:70
ilp::mtcnt
int * mtcnt
Definition: Cgl012cut.hpp:65
Cgl012Cut::add_tight_constraint
void add_tight_constraint()
edge
struct EDGE edge
edge::weight
double weight
Definition: Cgl012cut.hpp:106
parity_ilp::slack
double * slack
Definition: Cgl012cut.hpp:84
pool_cut::constr_list
int * constr_list
Definition: Cgl012cut.hpp:174
Cgl012Cut::best_neighbour
short int best_neighbour(cut_list *out_cuts)
auxiliary_graph::narcs
int narcs
Definition: Cgl012cut.hpp:131
cut::csense
char csense
Definition: Cgl012cut.hpp:163
separation_graph
Definition: Cgl012cut.hpp:112
Cgl012Cut::basic_separation
cut_list * basic_separation()
info_weak::var
int * var
Definition: Cgl012cut.hpp:100
cut_list::cnum
int cnum
Definition: Cgl012cut.hpp:168
Cgl012Cut::update_log_var
void update_log_var()
info_weak::type
short int * type
Definition: Cgl012cut.hpp:101
auxiliary_graph::nodes
cgl_node * nodes
Definition: Cgl012cut.hpp:132
cgl_node::index
int index
Definition: Cgl012cut.hpp:45
Cgl012Cut::initialize_sep_graph
separation_graph * initialize_sep_graph()
Cgl012Cut::aggr
bool aggr
Definition: Cgl012cut.hpp:460
cgl_node::firstArc
cgl_arc * firstArc
Definition: Cgl012cut.hpp:43
cgl_node
Definition: Cgl012cut.hpp:41
Cgl012Cut::Cgl012Cut
Cgl012Cut()
Default constructor.
Cgl012Cut::cut_score
double cut_score(int *ccoef, int crhs, double viol, short int only_viol)
Cgl012Cut::initialize_log_var
void initialize_log_var()
Cgl012Cut::best_weakening
int best_weakening(int n_to_weak, int *vars_to_weak, short int original_parity, double original_slack, double *best_even_slack, double *best_odd_slack, info_weak **info_even_weak, info_weak **info_odd_weak, short int only_odd, short int only_viol)
select_cut::ccoef
int * ccoef
Definition: Cgl012cut.hpp:191
parity_ilp::loss_even_weak
double * loss_even_weak
Definition: Cgl012cut.hpp:93
parity_ilp::type_odd_weak
short int * type_odd_weak
Definition: Cgl012cut.hpp:91
select_cut::crhs
int crhs
Definition: Cgl012cut.hpp:192
select_cut
Definition: Cgl012cut.hpp:190
Cgl012Cut::inp_ilp
ilp * inp_ilp
Definition: Cgl012cut.hpp:449
Cgl012Cut::~Cgl012Cut
virtual ~Cgl012Cut()
Destructor.
parity_ilp::mtcnt
int * mtcnt
Definition: Cgl012cut.hpp:80
edge::endpoint2
int endpoint2
Definition: Cgl012cut.hpp:105
Cgl012Cut::score_by_moving
double score_by_moving(int i, short int itype, double thresh)
pool_cut_list::cnum
int cnum
Definition: Cgl012cut.hpp:185
pool_cut
Definition: Cgl012cut.hpp:172
ilp::mtind
int * mtind
Definition: Cgl012cut.hpp:66
cycle::weight
double weight
Definition: Cgl012cut.hpp:143
cycle_list::cnum
int cnum
Definition: Cgl012cut.hpp:149
Cgl012Cut::get_current_cut
cut * get_current_cut()
pool_cut::n_of_constr
int n_of_constr
Definition: Cgl012cut.hpp:173
Cgl012Cut::p_ilp
parity_ilp * p_ilp
Definition: Cgl012cut.hpp:450
separation_graph::ind
int * ind
Definition: Cgl012cut.hpp:116
Cgl012Cut::restart
void restart(short int failure)
parity_ilp::xstar
double * xstar
Definition: Cgl012cut.hpp:83
parity_ilp
Definition: Cgl012cut.hpp:75
auxiliary_graph::arcs
cgl_arc * arcs
Definition: Cgl012cut.hpp:133
parity_ilp::mc
int mc
Definition: Cgl012cut.hpp:77
parity_ilp::col_to_delete
short int * col_to_delete
Definition: Cgl012cut.hpp:86
cgl_node::distanceBack
int distanceBack
Definition: Cgl012cut.hpp:46
cut::crhs
int crhs
Definition: Cgl012cut.hpp:162
Cgl012Cut::ilp_load
void ilp_load(int mr, int mc, int mnz, int *mtbeg, int *mtcnt, int *mtind, int *mtval, int *vlb, int *vub, int *mrhs, char *msense)
cgl_graph::nnodes
int nnodes
Definition: Cgl012cut.hpp:51
info_weak
Definition: Cgl012cut.hpp:98
ilp
Definition: Cgl012cut.hpp:60
ilp::msense
char * msense
Definition: Cgl012cut.hpp:71
cut
Definition: Cgl012cut.hpp:153
short_path_node::pred
int pred
Definition: Cgl012cut.hpp:139
Cgl012Cut::sep_iter
int sep_iter
Definition: Cgl012cut.hpp:455
edge::constr
int constr
Definition: Cgl012cut.hpp:108
cycle_list::list
cycle ** list
Definition: Cgl012cut.hpp:150
short_path_node::dist
long dist
Definition: Cgl012cut.hpp:138
parity_ilp::gcd
int * gcd
Definition: Cgl012cut.hpp:87
parity_ilp::mnz
int mnz
Definition: Cgl012cut.hpp:78
Cgl012Cut::free_log_var
void free_log_var()
Cgl012Cut::operator=
Cgl012Cut & operator=(const Cgl012Cut &rhs)
Assignment operator.
ilp::xstar
const double * xstar
Definition: Cgl012cut.hpp:72
pool_cut::score
double score
Definition: Cgl012cut.hpp:180
cgl_graph::nodes
cgl_node * nodes
Definition: Cgl012cut.hpp:53
cycle
Definition: Cgl012cut.hpp:142
Cgl012Cut
012Cut Generator Class
Definition: Cgl012cut.hpp:207
cut::violation
double violation
Definition: Cgl012cut.hpp:164
Cgl012Cut::print_parity_ilp
void print_parity_ilp()
ilp::mnz
int mnz
Definition: Cgl012cut.hpp:63
Cgl012Cut::print_cut_list
void print_cut_list(cut_list *cuts)
auxiliary_graph::nnodes
int nnodes
Definition: Cgl012cut.hpp:130
Cgl012Cut::modify_current
void modify_current(int i, short int itype)
cut::constr_list
int * constr_list
Definition: Cgl012cut.hpp:155
cut::cind
int * cind
Definition: Cgl012cut.hpp:160
Cgl012Cut::define_cut
cut * define_cut(int *ccoef, int crhs)
cycle::length
int length
Definition: Cgl012cut.hpp:144
cycle::edge_list
edge ** edge_list
Definition: Cgl012cut.hpp:145
parity_ilp::possible_weak
short int * possible_weak
Definition: Cgl012cut.hpp:88
parity_ilp::mrhs
short int * mrhs
Definition: Cgl012cut.hpp:82
parity_ilp::mtbeg
int * mtbeg
Definition: Cgl012cut.hpp:79
cut::cnzcnt
int cnzcnt
Definition: Cgl012cut.hpp:159
separation_graph::odd_adj_list
edge ** odd_adj_list
Definition: Cgl012cut.hpp:118
ilp::mtbeg
int * mtbeg
Definition: Cgl012cut.hpp:64
cut_list
Definition: Cgl012cut.hpp:167
edge::weak
info_weak * weak
Definition: Cgl012cut.hpp:109
Cgl012Cut::gap
double gap
Definition: Cgl012cut.hpp:452
cgl_arc::to
int to
Definition: Cgl012cut.hpp:38
parity_ilp::type_even_weak
short int * type_even_weak
Definition: Cgl012cut.hpp:89
parity_ilp::mr
int mr
Definition: Cgl012cut.hpp:76
ilp::vlb
int * vlb
Definition: Cgl012cut.hpp:68
Cgl012Cut::get_cut
cut * get_cut(cycle *s_cyc)
pool_cut::it_found
int it_found
Definition: Cgl012cut.hpp:179
parity_ilp::row_to_delete
short int * row_to_delete
Definition: Cgl012cut.hpp:85
ilp::vub
int * vub
Definition: Cgl012cut.hpp:69
select_cut::score
double score
Definition: Cgl012cut.hpp:194
log_var
Definition: Cgl012cut.hpp:197
Cgl012Cut::tabu_012
cut_list * tabu_012()
Cgl012Cut::print_constr
void print_constr(int i)
cgl_arc::length
int length
Definition: Cgl012cut.hpp:37
pool_cut_list::ncod
int * ncod
Definition: Cgl012cut.hpp:187
separation_graph::nedges
int nedges
Definition: Cgl012cut.hpp:114
Cgl012Cut::iter
int iter
Definition: Cgl012cut.hpp:451
edge::parity
short int parity
Definition: Cgl012cut.hpp:107
Cgl012Cut::best_cut
short int best_cut(int *ccoef, int *crhs, double *violation, short int update, short int only_viol)
Cgl012Cut::get_parity_ilp
void get_parity_ilp()
Cgl012Cut::alloc_parity_ilp
void alloc_parity_ilp(int mr, int mc, int mnz)
cut::in_constr_list
short int * in_constr_list
Definition: Cgl012cut.hpp:156
Cgl012Cut::print_cur_cut
void print_cur_cut()
cut::n_of_constr
int n_of_constr
Definition: Cgl012cut.hpp:154
pool_cut::code
int code
Definition: Cgl012cut.hpp:175
Cgl012Cut::get_ori_cut_coef
short int get_ori_cut_coef(int n_of_constr, int *constr_list, int *ccoef, int *crhs, short int only_viol)
ilp::mc
int mc
Definition: Cgl012cut.hpp:62
Cgl012Cut::print_cut
void print_cut(cut *v_cut)
cut::cval
int * cval
Definition: Cgl012cut.hpp:161
parity_ilp::mtind
int * mtind
Definition: Cgl012cut.hpp:81
ilp::mtval
int * mtval
Definition: Cgl012cut.hpp:67
select_cut::pool_index
int pool_index
Definition: Cgl012cut.hpp:193
separation_graph::nodes
int * nodes
Definition: Cgl012cut.hpp:115
cgl_graph::arcs
cgl_arc * arcs
Definition: Cgl012cut.hpp:54
Cgl012Cut::maxgap
double maxgap
Definition: Cgl012cut.hpp:453
auxiliary_graph
Definition: Cgl012cut.hpp:129
cycle_list
Definition: Cgl012cut.hpp:148