Cgl  0.60.3
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
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
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 */
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" */
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" */
135 #endif
136 
137 typedef struct {
138 long dist; /* distance from/to root */
139 int pred; /* index of the predecessor */
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 
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 
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;
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
cut * get_cut(cycle *s_cyc)
void get_parity_ilp()
int n_it_zero
Definition: Cgl012cut.hpp:198
int mr
Definition: Cgl012cut.hpp:61
int n_it_violated
Definition: Cgl012cut.hpp:176
edge ** even_adj_list
Definition: Cgl012cut.hpp:117
double * min_loss_by_weak
Definition: Cgl012cut.hpp:95
double * loss_odd_weak
Definition: Cgl012cut.hpp:94
int parentNode
Definition: Cgl012cut.hpp:44
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)
void free_ilp()
log_var ** vlog
Definition: Cgl012cut.hpp:456
double score_by_moving(int i, short int itype, double thresh)
pool_cut ** list
Definition: Cgl012cut.hpp:186
cut ** list
Definition: Cgl012cut.hpp:169
int * mrhs
Definition: Cgl012cut.hpp:70
int * mtcnt
Definition: Cgl012cut.hpp:65
void add_tight_constraint()
double weight
Definition: Cgl012cut.hpp:106
double maxgap
Definition: Cgl012cut.hpp:453
double * slack
Definition: Cgl012cut.hpp:84
int * constr_list
Definition: Cgl012cut.hpp:174
short int get_ori_cut_coef(int n_of_constr, int *constr_list, int *ccoef, int *crhs, short int only_viol)
char csense
Definition: Cgl012cut.hpp:163
int * var
Definition: Cgl012cut.hpp:100
short int * type
Definition: Cgl012cut.hpp:101
cgl_node * nodes
Definition: Cgl012cut.hpp:132
void free_parity_ilp()
int index
Definition: Cgl012cut.hpp:45
cgl_arc * firstArc
Definition: Cgl012cut.hpp:43
void update_log_var()
int * ccoef
Definition: Cgl012cut.hpp:191
double * loss_even_weak
Definition: Cgl012cut.hpp:93
short int * type_odd_weak
Definition: Cgl012cut.hpp:91
Cgl012Cut()
Default constructor.
separation_graph * initialize_sep_graph()
cut_list * basic_separation()
parity_ilp * p_ilp
Definition: Cgl012cut.hpp:450
int * mtcnt
Definition: Cgl012cut.hpp:80
int endpoint2
Definition: Cgl012cut.hpp:105
012Cut Generator Class
Definition: Cgl012cut.hpp:207
int * mtind
Definition: Cgl012cut.hpp:66
cut * get_current_cut()
virtual ~Cgl012Cut()
Destructor.
double weight
Definition: Cgl012cut.hpp:143
void initialize()
int n_of_constr
Definition: Cgl012cut.hpp:173
double * xstar
Definition: Cgl012cut.hpp:83
cgl_arc * arcs
Definition: Cgl012cut.hpp:133
short int * col_to_delete
Definition: Cgl012cut.hpp:86
int distanceBack
Definition: Cgl012cut.hpp:46
void restart(short int failure)
int crhs
Definition: Cgl012cut.hpp:162
void print_constr(int i)
void free_log_var()
int nnodes
Definition: Cgl012cut.hpp:51
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)
int sep_iter
Definition: Cgl012cut.hpp:455
void modify_current(int i, short int itype)
char * msense
Definition: Cgl012cut.hpp:71
ilp * inp_ilp
Definition: Cgl012cut.hpp:449
int constr
Definition: Cgl012cut.hpp:108
cycle ** list
Definition: Cgl012cut.hpp:150
short int best_cut(int *ccoef, int *crhs, double *violation, short int update, short int only_viol)
int * gcd
Definition: Cgl012cut.hpp:87
double cut_score(int *ccoef, int crhs, double viol, short int only_viol)
const double * xstar
Definition: Cgl012cut.hpp:72
double score
Definition: Cgl012cut.hpp:180
double gap
Definition: Cgl012cut.hpp:452
cgl_node * nodes
Definition: Cgl012cut.hpp:53
double violation
Definition: Cgl012cut.hpp:164
int mnz
Definition: Cgl012cut.hpp:63
void print_cut(cut *v_cut)
int * constr_list
Definition: Cgl012cut.hpp:155
int * cind
Definition: Cgl012cut.hpp:160
void print_parity_ilp()
int length
Definition: Cgl012cut.hpp:144
edge ** edge_list
Definition: Cgl012cut.hpp:145
short int * possible_weak
Definition: Cgl012cut.hpp:88
short int * mrhs
Definition: Cgl012cut.hpp:82
int * mtbeg
Definition: Cgl012cut.hpp:79
int cnzcnt
Definition: Cgl012cut.hpp:159
edge ** odd_adj_list
Definition: Cgl012cut.hpp:118
int * mtbeg
Definition: Cgl012cut.hpp:64
info_weak * weak
Definition: Cgl012cut.hpp:109
int to
Definition: Cgl012cut.hpp:38
short int * type_even_weak
Definition: Cgl012cut.hpp:89
int * vlb
Definition: Cgl012cut.hpp:68
int it_found
Definition: Cgl012cut.hpp:179
short int * row_to_delete
Definition: Cgl012cut.hpp:85
int * vub
Definition: Cgl012cut.hpp:69
cut_list * tabu_012()
double score
Definition: Cgl012cut.hpp:194
void print_cut_list(cut_list *cuts)
int length
Definition: Cgl012cut.hpp:37
short int parity
Definition: Cgl012cut.hpp:107
short int * in_constr_list
Definition: Cgl012cut.hpp:156
cut * define_cut(int *ccoef, int crhs)
Cgl012Cut & operator=(const Cgl012Cut &rhs)
Assignment operator.
int n_of_constr
Definition: Cgl012cut.hpp:154
int mc
Definition: Cgl012cut.hpp:62
int * cval
Definition: Cgl012cut.hpp:161
void print_cur_cut()
int * mtind
Definition: Cgl012cut.hpp:81
void alloc_parity_ilp(int mr, int mc, int mnz)
int * mtval
Definition: Cgl012cut.hpp:67
void initialize_log_var()
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)
int pool_index
Definition: Cgl012cut.hpp:193
cgl_arc * arcs
Definition: Cgl012cut.hpp:54
short int best_neighbour(cut_list *out_cuts)