1 // $Id$ 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). 5 /** @file 012cut.h Include file for C coded 0-1/2 separator */ 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; 202 /** 012Cut Generator Class 203 204 This class is to make Cgl01cut thread safe etc 205 */ 206 207 class Cgl012Cut { 208 209 public: 210 211 /**@name Generate Cuts */ 212 //@{ 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); 417 //@} 418 public: 419 /**@name Constructors and destructors */ 420 //@{ 421 /// Default constructor 422 Cgl012Cut (); 423 424 /// Copy constructor 425 Cgl012Cut ( 426 const Cgl012Cut &); 427 428 /// Assignment operator 429 Cgl012Cut & 430 operator=( 431 const Cgl012Cut& rhs); 432 433 /// Destructor 434 virtual ~Cgl012Cut (); 435 //@} 436 437 private: 438 439 // Private member methods 440 441 /**@name Private methods */ 442 //@{ 443 //@} 444 445 446 /**@name Private member data */ 447 //@{ 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) */ 462 //@} 463 }; 464 #endif 465