Cgl  trunk
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines
Cgl012cut.hpp
Go to the documentation of this file.
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
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines