Cgl
trunk
|
00001 // $Id$ 00002 // Copyright (C) 2010, International Business Machines 00003 // Corporation and others. All Rights Reserved. 00004 // This code is licensed under the terms of the Eclipse Public License (EPL). 00006 #ifndef CGL012CUT 00007 #define CGL012CUT 00008 #include <cstdio> 00009 #include <cstdlib> 00010 #include <cmath> 00011 00012 #define CGL_NEW_SHORT 00013 #ifndef CGL_NEW_SHORT 00014 typedef /* arc */ 00015 struct arc_st 00016 { 00017 int len; /* length of the arc */ 00018 struct node_st *head; /* head node */ 00019 } 00020 arc; 00021 00022 typedef /* node */ 00023 struct node_st 00024 { 00025 arc *first; /* first outgoing arc */ 00026 int dist; /* tentative shortest path length */ 00027 struct node_st *parent; /* parent pointer */ 00028 struct node_st *next; /* next node in queue */ 00029 struct node_st *prev; /* previous node in queue */ 00030 int status; /* status of node */ 00031 int temp; /* for temporary labels */ 00032 int index; /* index of the node in the graph */ 00033 } node; 00034 #endif 00035 typedef struct 00036 { 00037 int length; // Length of arc 00038 int to; // To node 00039 } cgl_arc; 00040 00041 typedef struct 00042 { 00043 cgl_arc * firstArc; // First outgoing arc 00044 int parentNode; // Parent node in shortest path 00045 int index; // Which node I am 00046 int distanceBack; // Distance back to source 00047 } cgl_node; 00048 00049 typedef struct 00050 { 00051 int nnodes; // Number of nodes in graph 00052 int narcs; // Number of arcs in graph 00053 cgl_node * nodes; 00054 cgl_arc * arcs; 00055 } cgl_graph; 00056 /* #define PRINT */ 00057 /* #define PRINT_CUTS */ 00058 #define REDUCTION 00059 /* #define TIME */ 00060 #undef TIME 00061 00062 #define TRUE 1 00063 #define FALSE 0 00064 00065 #define ODD 1 00066 #define EVEN 0 00067 00068 #define NONE -1 00069 #define BOTH 2 00070 00071 #define IN 1 00072 #define OUT 0 00073 #define ADD 1 00074 #define DEL 0 00075 00076 #define LOWER_BOUND 0 00077 #define UPPER_BOUND 1 00078 00079 #define EPS 0.0001 /* small tolerance */ 00080 //#define EPS 0.000001 /* small tolerance */ 00081 #define ZERO 0.000001 /* estimated accuracy for doubles */ 00082 //#define ZERO 0.0001 /* estimated accuracy for doubles */ 00083 #define INF 1000000000.0 00084 #define IINF 1000000000 00085 00086 #define MAX_SLACK 1.0 00087 #define MAX_LOSS 1.0 00088 #define MAX_CYCLE_WEIGHT 1.0 00089 #define MIN_VIOLATION 0.001 00090 #define MIN_SCORE_RANGE 10.0 00091 #define MAX_SCORE_RANGE ZERO /* 1.0 */ 00092 00093 #define ISCALE 10000 00094 00095 //#define MAX_CUTS 10 00096 00097 #define MAX_CUT_POOL 10000 00098 #define MAX_CUT_COD 10000 00099 #define MAX_ITER_POOL 100 00100 #define CLEAN_THRESH 0.9 00101 #define MANY_IT_ZERO 10 00102 00103 #define mod2(I) ( I % 2 == 0 ? 0 : 1 ) 00104 00105 typedef struct { 00106 int mr; /* number of rows in the ILP matrix */ 00107 int mc; /* number of columns in the ILP matrix */ 00108 int mnz; /* number of nonzero's in the ILP matrix */ 00109 int *mtbeg; /* starting position of each row in arrays mtind and mtval */ 00110 int *mtcnt; /* number of entries of each row in arrays mtind and mtval */ 00111 int *mtind; /* column indices of the nonzero entries of the ILP matrix */ 00112 int *mtval; /* values of the nonzero entries of the ILP matrix */ 00113 int *vlb; /* lower bounds on the variables */ 00114 int *vub; /* upper bounds on the variables */ 00115 int *mrhs; /* right hand sides of the constraints */ 00116 char *msense; /* senses of the constraints: 'L', 'G' or 'E' */ 00117 const double *xstar; /* current optimal solution of the LP relaxation */ 00118 } ilp; 00119 00120 typedef struct { 00121 int mr; /* number of rows in the parity ILP matrix */ 00122 int mc; /* number of columns in the parity ILP matrix */ 00123 int mnz; /* number of 1's in the parity ILP matrix */ 00124 int *mtbeg; /* starting position of each row in arrays mtind and mtval */ 00125 int *mtcnt; /* number of entries of each row in arrays mtind and mtval */ 00126 int *mtind; /* column indices of the 1's of the parity ILP matrix */ 00127 short int *mrhs; /* right hand side parity of the constraints */ 00128 double *xstar; /* current optimal solution of the LP relaxation */ 00129 double *slack; /* slack of the constraints w.r.t. xstar */ 00130 short int *row_to_delete; /* flag for marking rows not to be considered */ 00131 short int *col_to_delete; /* flag for marking columns not to be considered */ 00132 int *gcd; /* greatest common divisor of each row in the input ILP matrix */ 00133 short int *possible_weak; /* possible weakening types of each column */ 00134 short int *type_even_weak; /* type of even weakening of each column 00135 (lower or upper bound weakening) */ 00136 short int *type_odd_weak; /* type of odd weakening of each column 00137 (lower or upper bound weakening) */ 00138 double *loss_even_weak; /* loss for the even weakening of each column */ 00139 double *loss_odd_weak; /* loss for the odd weakening of each column */ 00140 double *min_loss_by_weak; /* minimum loss for the weakening of each column */ 00141 } parity_ilp; 00142 00143 typedef struct { 00144 int nweak; /* number of variables weakened */ 00145 int *var; /* list of variables weakened */ 00146 short int *type; /* type of weakening (lower or upper bound weakening) */ 00147 } info_weak; 00148 00149 typedef struct { 00150 int endpoint1, endpoint2; /* endpoints of the edge */ 00151 double weight; /* edge weight */ 00152 short int parity; /* edge parity (even or odd) */ 00153 int constr; /* constraint associated with the edge */ 00154 info_weak *weak; /* weakening information */ 00155 } edge; 00156 00157 typedef struct { 00158 int nnodes; /* number of nodes */ 00159 int nedges; /* number of edges */ 00160 int *nodes; /* indexes of the ILP columns corresponding to the nodes */ 00161 int *ind; /* indexes of the nodes corresponding to the ILP columns */ 00162 edge **even_adj_list; /* pointers to the even edges */ 00163 edge **odd_adj_list; /* pointers to the odd edges */ 00164 } separation_graph; 00165 00166 #ifndef CGL_NEW_SHORT 00167 typedef struct { 00168 int nnodes; /* number of nodes */ 00169 int narcs; /* number of arcs */ 00170 node *nodes; /* array of the nodes - see "types_db.h" */ 00171 arc *arcs; /* array of the arcs - see "types_db.h" */ 00172 } auxiliary_graph; 00173 #else 00174 typedef struct { 00175 int nnodes; /* number of nodes */ 00176 int narcs; /* number of arcs */ 00177 cgl_node *nodes; /* array of the nodes - see "types_db.h" */ 00178 cgl_arc *arcs; /* array of the arcs - see "types_db.h" */ 00179 } auxiliary_graph; 00180 #endif 00181 00182 typedef struct { 00183 long dist; /* distance from/to root */ 00184 int pred; /* index of the predecessor */ 00185 } short_path_node; 00186 00187 typedef struct { 00188 double weight; /* overall weight of the cycle */ 00189 int length; /* number of edges in the cycle */ 00190 edge **edge_list; /* list of edges in the cycle */ 00191 } cycle; 00192 00193 typedef struct { 00194 int cnum; /* overall number of cycles */ 00195 cycle **list; /* pointers to the cycles in the list */ 00196 } cycle_list; 00197 00198 typedef struct { 00199 int n_of_constr; /* number of constraints combined to get the cut */ 00200 int *constr_list; /* list of the constraints combined */ 00201 short int *in_constr_list; /* flag saying whether a given constraint is 00202 in the list of constraints of the cut (IN) 00203 or not (OUT) */ 00204 int cnzcnt; /* overall number of nonzero's in the cut */ 00205 int *cind; /* column indices of the nonzero entries of the cut */ 00206 int *cval; /* values of the nonzero entries of the cut */ 00207 int crhs; /* right hand side of the cut */ 00208 char csense; /* sense of the cut: 'L', 'G' or 'E' */ 00209 double violation; /* violation of the cut w.r.t. the current LP solution */ 00210 } cut; 00211 00212 typedef struct { 00213 int cnum; /* overall number of cuts */ 00214 cut **list; /* pointers to the cuts in the list */ 00215 } cut_list; 00216 00217 typedef struct { 00218 int n_of_constr; /* number of constraints combined to get the cut */ 00219 int *constr_list; /* list of the constraints combined */ 00220 int code; /* identifier of the cut */ 00221 int n_it_violated; /* number of consecutive iterations (starting from the 00222 last and going backward) in which the cut was 00223 violated by the LP solution */ 00224 int it_found; /* iteration in which the cut was separated */ 00225 double score; /* score of the cut, used to choose wich cut should be 00226 added to the current LP (if any) */ 00227 } pool_cut; 00228 00229 typedef struct { 00230 int cnum; /* overall number of cuts */ 00231 pool_cut **list; /* pointers to the cuts in the list */ 00232 int *ncod; /* number of cuts with a given code in the pool */ 00233 } pool_cut_list; 00234 00235 typedef struct { 00236 int *ccoef; /* coefficients of the cut */ 00237 int crhs; /* right hand side of the cut */ 00238 int pool_index; /* index of the cut in the pool */ 00239 double score; /* cut score (to be maximized) */ 00240 } select_cut; 00241 00242 typedef struct { 00243 int n_it_zero; /* number of consecutive iterations (starting from the 00244 last and going backward) in which each variable took 00245 the value 0 in the LP solution */ 00246 } log_var; 00252 class Cgl012Cut { 00253 00254 public: 00255 00258 int sep_012_cut( 00259 /* 00260 INPUT parameters: 00261 */ 00262 int mr, /* number of rows in the ILP matrix */ 00263 int mc, /* number of columns in the ILP matrix */ 00264 int mnz, /* number of nonzero's in the ILP matrix */ 00265 int *mtbeg, /* starting position of each row in arrays mtind and mtval */ 00266 int *mtcnt, /* number of entries of each row in arrays mtind and mtval */ 00267 int *mtind, /* column indices of the nonzero entries of the ILP matrix */ 00268 int *mtval, /* values of the nonzero entries of the ILP matrix */ 00269 int *vlb, /* lower bounds on the variables */ 00270 int *vub, /* upper bounds on the variables */ 00271 int *mrhs, /* right hand sides of the constraints */ 00272 char *msense, /* senses of the constraints: 'L', 'G' or 'E' */ 00273 const double *xstar, /* current optimal solution of the LP relaxation */ 00274 bool aggressive, /* flag asking whether as many cuts as possible are 00275 required on output (TRUE) or not (FALSE) */ 00276 /* 00277 OUTPUT parameters (the memory for the vectors is allocated INTERNALLY 00278 by the procedure: if some memory is already allocated, it is FREED): 00279 */ 00280 int *cnum, /* number of violated 0-1/2 cuts identified by the procedure */ 00281 int *cnzcnt, /* overall number of nonzero's in the cuts */ 00282 int **cbeg, /* starting position of each cut in arrays cind and cval */ 00283 int **ccnt, /* number of entries of each cut in arrays cind and cval */ 00284 int **cind, /* column indices of the nonzero entries of the cuts */ 00285 int **cval, /* values of the nonzero entries of the cuts */ 00286 int **crhs, /* right hand sides of the cuts */ 00287 char **csense /* senses of the cuts: 'L', 'G' or 'E' */ 00288 /* 00289 NOTE that all the numerical input/output vectors are INTEGER (with 00290 the exception of xstar), since the procedure is intended to work 00291 with pure ILP's, and that the ILP matrix has to be given on input 00292 in ROW format. 00293 */ 00294 ) const; 00295 void ilp_load( 00296 int mr, /* number of rows in the ILP matrix */ 00297 int mc, /* number of columns in the ILP matrix */ 00298 int mnz, /* number of nonzero's in the ILP matrix */ 00299 int *mtbeg, /* starting position of each row in arrays mtind and mtval */ 00300 int *mtcnt, /* number of entries of each row in arrays mtind and mtval */ 00301 int *mtind, /* column indices of the nonzero entries of the ILP matrix */ 00302 int *mtval, /* values of the nonzero entries of the ILP matrix */ 00303 int *vlb, /* lower bounds on the variables */ 00304 int *vub, /* upper bounds on the variables */ 00305 int *mrhs, /* right hand sides of the constraints */ 00306 char *msense /* senses of the constraints: 'L', 'G' or 'E' */ 00307 ); 00308 void free_ilp(); 00309 /* alloc_parity_ilp: allocate the memory for the parity ILP data structure */ 00310 00311 void alloc_parity_ilp( 00312 int mr, /* number of rows in the ILP matrix */ 00313 int mc, /* number of columns in the ILP matrix */ 00314 int mnz /* number of nonzero's in the ILP matrix */ 00315 ); 00316 void free_parity_ilp(); 00317 void initialize_log_var() const; 00318 /* free_log_var */ 00319 void free_log_var(); 00320 private: 00321 /* best_weakening: find the best upper/lower bound weakening of a set 00322 of variables */ 00323 00324 int best_weakening( 00325 int n_to_weak, /* number of variables to weaken */ 00326 int *vars_to_weak, /* indices of the variables to weaken */ 00327 short int original_parity, /* original parity of the constraint to weaken */ 00328 double original_slack, /* original slack of the constraint to weaken */ 00329 double *best_even_slack, /* best possible slack of a weakened constraint 00330 with even right-hand-side */ 00331 double *best_odd_slack, /* best possible slack of a weakened constraint 00332 with odd right-hand-side */ 00333 info_weak **info_even_weak, /* weakening information about the best possible 00334 even weakened constraint */ 00335 info_weak **info_odd_weak, /* weakening information about the best possible 00336 odd weakened constraint */ 00337 short int only_odd, /* flag which tells whether only an odd weakening is of 00338 interest (TRUE) or both weakenings are (FALSE) */ 00339 short int only_viol /* flag which tells whether only an inequality of 00340 slack smaller than MAX_SLACK is of interest (TRUE) 00341 otherwise (FALSE) */ 00342 ) const; 00343 00344 /* best_cut: find the coefficients, the rhs and the violation of the 00345 best possible cut that can be obtained by weakening a given set of 00346 coefficients to even and a rhs to odd, dividing by 2 and rounding */ 00347 00348 short int best_cut( 00349 int *ccoef, /* vector of the coefficients */ 00350 int *crhs, /* pointer to rhs value */ 00351 double *violation, /* violation of the cut */ 00352 short int update, /* TRUE/FALSE: if TRUE, the new ccoef and crhs are 00353 given on output */ 00354 short int only_viol /* flag which tells whether only an inequality of 00355 slack smaller than MAX_SLACK is of interest (TRUE) 00356 otherwise (FALSE) */ 00357 ) const; 00358 /* get_cut: extract a hopefully violated cut from an odd cycle of the 00359 separation graph */ 00360 00361 cut *get_cut( 00362 cycle *s_cyc /* shortest odd cycles identified in the separation graph */ 00363 ) const; 00364 00365 /* update_log_var: update the log information for the problem variables */ 00366 void update_log_var() const; 00367 00368 /* basic_separation: try to identify violated 0-1/2 cuts by using the 00369 original procedure described in Caprara and Fischetti's MP paper */ 00370 00371 cut_list *basic_separation() const; 00372 00373 /* score_by_moving: compute the score of the best cut obtainable from 00374 the current local search solution by inserting/deleting a constraint */ 00375 00376 double score_by_moving( 00377 int i, /* constraint to be moved */ 00378 short int itype, /* type of move - ADD or DEL */ 00379 double thresh /* minimum value of an interesting score */ 00380 ); 00381 /* modify_current: update the current local search solution by inserting/ 00382 deleting a constraint */ 00383 00384 void modify_current( 00385 int i, /* constraint to be moved */ 00386 short int itype /* type of move - ADD or DEL */ 00387 ); 00388 00389 /* best neighbour: find the cut to be added/deleted from the current 00390 solution among those allowed by the tabu rules */ 00391 00392 short int best_neighbour(cut_list *out_cuts /* list of the violated cuts found */); 00393 00394 /* add_tight_constraint: initialize the current cut by adding a tight 00395 constraint to it */ 00396 00397 void add_tight_constraint(); 00398 00399 /* tabu_012: try to identify violated 0-1/2 cuts by a simple tabu search 00400 procedure adapted from that used by Battiti and Protasi for finding 00401 large cliques */ 00402 00403 cut_list *tabu_012(); 00404 /* initialize: initialize the data structures for local search */ 00405 00406 void initialize(); 00407 /* restart: perform a restart of the search - IMPORTANT: in the current 00408 implementation vector last_moved is not cleared at restart */ 00409 00410 void restart(short int failure /* flag forcing the restart if some trouble occurred */); 00411 void print_constr(int i /* constraint to be printed */); 00412 void print_parity_ilp(); 00413 00414 /* get_parity_ilp: construct an internal data structure containing all the 00415 information which can be useful for 0-1/2 cut separation */ 00416 00417 void get_parity_ilp() const; 00418 /* initialize_sep_graph: allocate and initialize the data structure 00419 to contain the information associated with a separation graph */ 00420 00421 separation_graph *initialize_sep_graph() const; 00422 void print_cut(cut *v_cut); 00423 /* get_ori_cut_coef: get the coefficients of a cut, before dividing by 2 and 00424 rounding, starting from the list of the constraints combined to get 00425 the cut */ 00426 00427 short int get_ori_cut_coef( 00428 int n_of_constr, /* number of constraints combined */ 00429 int *constr_list, /* list of the constraints combined */ 00430 int *ccoef, /* cut left hand side coefficients */ 00431 int *crhs, /* cut right hand side */ 00432 short int only_viol /* flag which tells whether only an inequality of 00433 slack smaller than MAX_SLACK is of interest (TRUE) 00434 otherwise (FALSE) */ 00435 ) const; 00436 /* define_cut: construct a cut data structure from a vector of 00437 coefficients and a right-hand-side */ 00438 00439 cut *define_cut( 00440 int *ccoef, /* coefficients of the cut */ 00441 int crhs /* right hand side of the cut */ 00442 ) const; 00443 00444 /* cut_score: define the score of a (violated) cut */ 00445 00446 double cut_score( 00447 int *ccoef, /* cut left hand side coefficients */ 00448 int crhs, /* cut right hand side */ 00449 double viol, /* cut violation */ 00450 short int only_viol /* flag which tells whether only an inequality of 00451 slack smaller than MAX_SLACK is of interest (TRUE) 00452 otherwise (FALSE) */ 00453 ); 00454 /* get_current_cut: return a cut data type with the information about 00455 the current cut of the search procedure */ 00456 00457 cut *get_current_cut(); 00458 /* print_cur_cut: display cur_cut on output */ 00459 00460 void print_cur_cut(); 00461 void print_cut_list(cut_list *cuts); 00463 public: 00466 00467 Cgl012Cut (); 00468 00470 Cgl012Cut ( 00471 const Cgl012Cut &); 00472 00474 Cgl012Cut & 00475 operator=( 00476 const Cgl012Cut& rhs); 00477 00479 virtual ~Cgl012Cut (); 00481 00482 private: 00483 00484 // Private member methods 00485 00488 00489 00490 00493 00494 ilp *inp_ilp; /* input ILP data structure */ 00495 parity_ilp *p_ilp; /* parity ILP data structure */ 00496 mutable int iter; 00497 mutable double gap; 00498 mutable double maxgap; 00499 mutable int errorNo; 00500 mutable int sep_iter; /* number of the current separation iteration */ 00501 mutable log_var **vlog; /* information about the value attained 00502 by the variables in the last iterations, 00503 used to possibly set to 0 some coefficient 00504 > 0 in a cut to be added */ 00505 mutable bool aggr; /* flag saying whether as many cuts as possible are required 00506 from the separation procedure (TRUE) or not (FALSE) */ 00508 }; 00509 #endif