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

- File List
- File Members

# /home/coin/svn-release/Alps-1.5.2/Cgl/src/CglZeroHalf/Cgl012cut.hpp

Go to the documentation of this file.

    00001 // $Id: Cgl012cut.hpp 1149 2013-10-21 18:23:53Z tkr $
    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
    00060 typedef struct {
    00061 int mr; /* number of rows in the ILP matrix */
    00062 int mc; /* number of columns in the ILP matrix */
    00063 int mnz; /* number of nonzero's in the ILP matrix */
    00064 int *mtbeg; /* starting position of each row in arrays mtind and mtval */
    00065 int *mtcnt; /* number of entries of each row in arrays mtind and mtval */
    00066 int *mtind; /* column indices of the nonzero entries of the ILP matrix */
    00067 int *mtval; /* values of the nonzero entries of the ILP matrix */
    00068 int *vlb; /* lower bounds on the variables */
    00069 int *vub; /* upper bounds on the variables */
    00070 int *mrhs; /* right hand sides of the constraints */
    00071 char *msense; /* senses of the constraints: 'L', 'G' or 'E' */
    00072 const double *xstar; /* current optimal solution of the LP relaxation */
    00073 } ilp;
    00074
    00075 typedef struct {
    00076 int mr; /* number of rows in the parity ILP matrix */
    00077 int mc; /* number of columns in the parity ILP matrix */
    00078 int mnz; /* number of 1's in the parity ILP matrix */
    00079 int *mtbeg; /* starting position of each row in arrays mtind and mtval */
    00080 int *mtcnt; /* number of entries of each row in arrays mtind and mtval */
    00081 int *mtind; /* column indices of the 1's of the parity ILP matrix */
    00082 short int *mrhs; /* right hand side parity of the constraints */
    00083 double *xstar; /* current optimal solution of the LP relaxation */
    00084 double *slack; /* slack of the constraints w.r.t. xstar */
    00085 short int *row_to_delete; /* flag for marking rows not to be considered */
    00086 short int *col_to_delete; /* flag for marking columns not to be considered */
    00087 int *gcd; /* greatest common divisor of each row in the input ILP matrix */
    00088 short int *possible_weak; /* possible weakening types of each column */
    00089 short int *type_even_weak; /* type of even weakening of each column
    00090                               (lower or upper bound weakening) */
    00091 short int *type_odd_weak; /* type of odd weakening of each column
    00092                               (lower or upper bound weakening) */
    00093 double *loss_even_weak; /* loss for the even weakening of each column */
    00094 double *loss_odd_weak; /* loss for the odd weakening of each column */
    00095 double *min_loss_by_weak; /* minimum loss for the weakening of each column */
    00096 } parity_ilp;
    00097
    00098 typedef struct {
    00099 int nweak; /* number of variables weakened */
    00100 int *var; /* list of variables weakened */
    00101 short int *type; /* type of weakening (lower or upper bound weakening) */
    00102 } info_weak;
    00103
    00104 typedef struct {
    00105 int endpoint1, endpoint2; /* endpoints of the edge */
    00106 double weight; /* edge weight */
    00107 short int parity; /* edge parity (even or odd) */
    00108 int constr; /* constraint associated with the edge */
    00109 info_weak *weak; /* weakening information */
    00110 } edge;
    00111
    00112 typedef struct {
    00113 int nnodes; /* number of nodes */
    00114 int nedges; /* number of edges */
    00115 int *nodes; /* indexes of the ILP columns corresponding to the nodes */
    00116 int *ind; /* indexes of the nodes corresponding to the ILP columns */
    00117 edge **even_adj_list; /* pointers to the even edges */
    00118 edge **odd_adj_list; /* pointers to the odd edges */
    00119 } separation_graph;
    00120
    00121 #ifndef CGL_NEW_SHORT
    00122 typedef struct {
    00123 int nnodes; /* number of nodes */
    00124 int narcs; /* number of arcs */
    00125 node *nodes; /* array of the nodes - see "types_db.h" */
    00126 arc *arcs; /* array of the arcs - see "types_db.h" */
    00127 } auxiliary_graph;
    00128 #else
    00129 typedef struct {
    00130 int nnodes; /* number of nodes */
    00131 int narcs; /* number of arcs */
    00132 cgl_node *nodes; /* array of the nodes - see "types_db.h" */
    00133 cgl_arc *arcs; /* array of the arcs - see "types_db.h" */
    00134 } auxiliary_graph;
    00135 #endif
    00136
    00137 typedef struct {
    00138 long dist; /* distance from/to root */
    00139 int pred; /* index of the predecessor */
    00140 } short_path_node;
    00141
    00142 typedef struct {
    00143 double weight; /* overall weight of the cycle */
    00144 int length; /* number of edges in the cycle */
    00145 edge **edge_list; /* list of edges in the cycle */
    00146 } cycle;
    00147
    00148 typedef struct {
    00149 int cnum; /* overall number of cycles */
    00150 cycle **list; /* pointers to the cycles in the list */
    00151 } cycle_list;
    00152
    00153 typedef struct {
    00154 int n_of_constr; /* number of constraints combined to get the cut */
    00155 int *constr_list; /* list of the constraints combined */
    00156 short int *in_constr_list; /* flag saying whether a given constraint is
    00157                               in the list of constraints of the cut (IN)
    00158                               or not (OUT) */
    00159 int cnzcnt; /* overall number of nonzero's in the cut */
    00160 int *cind; /* column indices of the nonzero entries of the cut */
    00161 int *cval; /* values of the nonzero entries of the cut */
    00162 int crhs; /* right hand side of the cut */
    00163 char csense; /* sense of the cut: 'L', 'G' or 'E' */
    00164 double violation; /* violation of the cut w.r.t. the current LP solution */
    00165 } cut;
    00166
    00167 typedef struct {
    00168 int cnum; /* overall number of cuts */
    00169 cut **list; /* pointers to the cuts in the list */
    00170 } cut_list;
    00171
    00172 typedef struct {
    00173 int n_of_constr; /* number of constraints combined to get the cut */
    00174 int *constr_list; /* list of the constraints combined */
    00175 int code; /* identifier of the cut */
    00176 int n_it_violated; /* number of consecutive iterations (starting from the
    00177                       last and going backward) in which the cut was
    00178                       violated by the LP solution */
    00179 int it_found; /* iteration in which the cut was separated */
    00180 double score; /* score of the cut, used to choose wich cut should be
    00181                  added to the current LP (if any) */
    00182 } pool_cut;
    00183
    00184 typedef struct {
    00185 int cnum; /* overall number of cuts */
    00186 pool_cut **list; /* pointers to the cuts in the list */
    00187 int *ncod; /* number of cuts with a given code in the pool */
    00188 } pool_cut_list;
    00189
    00190 typedef struct {
    00191 int *ccoef; /* coefficients of the cut */
    00192 int crhs; /* right hand side of the cut */
    00193 int pool_index; /* index of the cut in the pool */
    00194 double score; /* cut score (to be maximized) */
    00195 } select_cut;
    00196
    00197 typedef struct {
    00198 int n_it_zero; /* number of consecutive iterations (starting from the
    00199                    last and going backward) in which each variable took
    00200                    the value 0 in the LP solution */
    00201 } log_var;
    00207 class Cgl012Cut {
    00208
    00209 public:
    00210
    00213 int sep_012_cut(
    00214 /*
    00215   INPUT parameters:
    00216 */
    00217 int mr, /* number of rows in the ILP matrix */
    00218 int mc, /* number of columns in the ILP matrix */
    00219 int mnz, /* number of nonzero's in the ILP matrix */
    00220 int *mtbeg, /* starting position of each row in arrays mtind and mtval */
    00221 int *mtcnt, /* number of entries of each row in arrays mtind and mtval */
    00222 int *mtind, /* column indices of the nonzero entries of the ILP matrix */
    00223 int *mtval, /* values of the nonzero entries of the ILP matrix */
    00224 int *vlb, /* lower bounds on the variables */
    00225 int *vub, /* upper bounds on the variables */
    00226 int *mrhs, /* right hand sides of the constraints */
    00227 char *msense, /* senses of the constraints: 'L', 'G' or 'E' */
    00228 const double *xstar, /* current optimal solution of the LP relaxation */
    00229 bool aggressive, /* flag asking whether as many cuts as possible are
    00230                          required on output (TRUE) or not (FALSE) */
    00231 /*
    00232   OUTPUT parameters (the memory for the vectors is allocated INTERNALLY
    00233   by the procedure: if some memory is already allocated, it is FREED):
    00234 */
    00235 int *cnum, /* number of violated 0-1/2 cuts identified by the procedure */
    00236 int *cnzcnt, /* overall number of nonzero's in the cuts */
    00237 int **cbeg, /* starting position of each cut in arrays cind and cval */
    00238 int **ccnt, /* number of entries of each cut in arrays cind and cval */
    00239 int **cind, /* column indices of the nonzero entries of the cuts */
    00240 int **cval, /* values of the nonzero entries of the cuts */
    00241 int **crhs, /* right hand sides of the cuts */
    00242 char **csense /* senses of the cuts: 'L', 'G' or 'E' */
    00243 /*
    00244   NOTE that all the numerical input/output vectors are INTEGER (with
    00245   the exception of xstar), since the procedure is intended to work
    00246   with pure ILP's, and that the ILP matrix has to be given on input
    00247   in ROW format.
    00248 */
    00249                 );
    00250 void ilp_load(
    00251               int mr, /* number of rows in the ILP matrix */
    00252               int mc, /* number of columns in the ILP matrix */
    00253               int mnz, /* number of nonzero's in the ILP matrix */
    00254               int *mtbeg, /* starting position of each row in arrays mtind and mtval */
    00255               int *mtcnt, /* number of entries of each row in arrays mtind and mtval */
    00256               int *mtind, /* column indices of the nonzero entries of the ILP matrix */
    00257               int *mtval, /* values of the nonzero entries of the ILP matrix */
    00258               int *vlb, /* lower bounds on the variables */
    00259               int *vub, /* upper bounds on the variables */
    00260               int *mrhs, /* right hand sides of the constraints */
    00261               char *msense /* senses of the constraints: 'L', 'G' or 'E' */
    00262               );
    00263 void free_ilp();
    00264 /* alloc_parity_ilp: allocate the memory for the parity ILP data structure */
    00265
    00266 void alloc_parity_ilp(
    00267                       int mr, /* number of rows in the ILP matrix */
    00268                       int mc, /* number of columns in the ILP matrix */
    00269                       int mnz /* number of nonzero's in the ILP matrix */
    00270                       );
    00271 void free_parity_ilp();
    00272   void initialize_log_var();
    00273 /* free_log_var */
    00274   void free_log_var();
    00275 private:
    00276 /* best_weakening: find the best upper/lower bound weakening of a set
    00277    of variables */
    00278
    00279 int best_weakening(
    00280                    int n_to_weak, /* number of variables to weaken */
    00281 int *vars_to_weak, /* indices of the variables to weaken */
    00282 short int original_parity, /* original parity of the constraint to weaken */
    00283 double original_slack, /* original slack of the constraint to weaken */
    00284 double *best_even_slack, /* best possible slack of a weakened constraint
    00285                            with even right-hand-side */
    00286 double *best_odd_slack, /* best possible slack of a weakened constraint
    00287                           with odd right-hand-side */
    00288 info_weak **info_even_weak, /* weakening information about the best possible
    00289                                even weakened constraint */
    00290 info_weak **info_odd_weak, /* weakening information about the best possible
    00291                               odd weakened constraint */
    00292 short int only_odd, /* flag which tells whether only an odd weakening is of
    00293                        interest (TRUE) or both weakenings are (FALSE) */
    00294 short int only_viol /* flag which tells whether only an inequality of
    00295                         slack smaller than MAX_SLACK is of interest (TRUE)
    00296                         otherwise (FALSE) */
    00297                    );
    00298
    00299 /* best_cut: find the coefficients, the rhs and the violation of the
    00300    best possible cut that can be obtained by weakening a given set of
    00301    coefficients to even and a rhs to odd, dividing by 2 and rounding */
    00302
    00303 short int best_cut(
    00304                    int *ccoef, /* vector of the coefficients */
    00305                    int *crhs, /* pointer to rhs value */
    00306                    double *violation, /* violation of the cut */
    00307                    short int update, /* TRUE/FALSE: if TRUE, the new ccoef and crhs are
    00308                                         given on output */
    00309                    short int only_viol /* flag which tells whether only an inequality of
    00310                         slack smaller than MAX_SLACK is of interest (TRUE)
    00311                         otherwise (FALSE) */
    00312                               );
    00313 /* get_cut: extract a hopefully violated cut from an odd cycle of the
    00314    separation graph */
    00315
    00316 cut *get_cut(
    00317              cycle *s_cyc /* shortest odd cycles identified in the separation graph */
    00318              );
    00319
    00320 /* update_log_var: update the log information for the problem variables */
    00321   void update_log_var();
    00322
    00323 /* basic_separation: try to identify violated 0-1/2 cuts by using the
    00324    original procedure described in Caprara and Fischetti's MP paper */
    00325
    00326   cut_list *basic_separation();
    00327
    00328 /* score_by_moving: compute the score of the best cut obtainable from
    00329    the current local search solution by inserting/deleting a constraint */
    00330
    00331 double score_by_moving(
    00332                        int i, /* constraint to be moved */
    00333                        short int itype, /* type of move - ADD or DEL */
    00334                        double thresh /* minimum value of an interesting score */
    00335                        );
    00336 /* modify_current: update the current local search solution by inserting/
    00337    deleting a constraint */
    00338
    00339 void modify_current(
    00340                     int i, /* constraint to be moved */
    00341                     short int itype /* type of move - ADD or DEL */
    00342                     );
    00343
    00344 /* best neighbour: find the cut to be added/deleted from the current
    00345    solution among those allowed by the tabu rules */
    00346
    00347   short int best_neighbour(cut_list *out_cuts /* list of the violated cuts found */);
    00348
    00349 /* add_tight_constraint: initialize the current cut by adding a tight
    00350    constraint to it */
    00351
    00352   void add_tight_constraint();
    00353
    00354 /* tabu_012: try to identify violated 0-1/2 cuts by a simple tabu search
    00355    procedure adapted from that used by Battiti and Protasi for finding
    00356    large cliques */
    00357
    00358   cut_list *tabu_012();
    00359 /* initialize: initialize the data structures for local search */
    00360
    00361   void initialize();
    00362 /* restart: perform a restart of the search - IMPORTANT: in the current
    00363    implementation vector last_moved is not cleared at restart */
    00364
    00365   void restart(short int failure /* flag forcing the restart if some trouble occurred */);
    00366   void print_constr(int i /* constraint to be printed */);
    00367   void print_parity_ilp();
    00368
    00369 /* get_parity_ilp: construct an internal data structure containing all the
    00370    information which can be useful for  0-1/2 cut separation */
    00371
    00372   void get_parity_ilp();
    00373 /* initialize_sep_graph: allocate and initialize the data structure
    00374    to contain the information associated with a separation graph */
    00375
    00376   separation_graph *initialize_sep_graph();
    00377   void print_cut(cut *v_cut);
    00378 /* get_ori_cut_coef: get the coefficients of a cut, before dividing by 2 and
    00379    rounding, starting from the list of the constraints combined to get
    00380    the cut */
    00381
    00382 short int get_ori_cut_coef(
    00383                            int n_of_constr, /* number of constraints combined */
    00384                            int *constr_list, /* list of the constraints combined */
    00385                            int *ccoef, /* cut left hand side coefficients */
    00386                            int *crhs, /* cut right hand side */
    00387                            short int only_viol /* flag which tells whether only an inequality of
    00388                         slack smaller than MAX_SLACK is of interest (TRUE)
    00389                         otherwise (FALSE) */
    00390                            );
    00391 /* define_cut: construct a cut data structure from a vector of
    00392    coefficients and a right-hand-side */
    00393
    00394 cut *define_cut(
    00395                 int *ccoef, /* coefficients of the cut */
    00396                 int crhs /* right hand side of the cut */
    00397                 );
    00398
    00399 /* cut_score: define the score of a (violated) cut */
    00400
    00401 double cut_score(
    00402                  int *ccoef, /* cut left hand side coefficients */
    00403                  int crhs, /* cut right hand side */
    00404                  double viol, /* cut violation */
    00405                  short int only_viol /* flag which tells whether only an inequality of
    00406                         slack smaller than MAX_SLACK is of interest (TRUE)
    00407                         otherwise (FALSE) */
    00408                  );
    00409 /* get_current_cut: return a cut data type with the information about
    00410    the current cut of the search procedure */
    00411
    00412   cut *get_current_cut();
    00413 /* print_cur_cut: display cur_cut on output */
    00414
    00415   void print_cur_cut();
    00416   void print_cut_list(cut_list *cuts);
    00418 public:
    00421
    00422   Cgl012Cut ();
    00423
    00425   Cgl012Cut (
    00426     const Cgl012Cut &);
    00427
    00429   Cgl012Cut &
    00430     operator=(
    00431     const Cgl012Cut& rhs);
    00432
    00434   virtual ~Cgl012Cut ();
    00436
    00437 private:
    00438
    00439   // Private member methods
    00440
    00443
    00444
    00445
    00448
    00449 ilp *inp_ilp; /* input ILP data structure */
    00450 parity_ilp *p_ilp; /* parity ILP data structure */
    00451 int iter;
    00452 double gap;
    00453 double maxgap;
    00454 int errorNo;
    00455 int sep_iter; /* number of the current separation iteration */
    00456 log_var **vlog; /* information about the value attained
    00457                                   by the variables in the last iterations,
    00458                                   used to possibly set to 0 some coefficient
    00459                                   > 0 in a cut to be added */
    00460 bool aggr; /* flag saying whether as many cuts as possible are required
    00461                    from the separation procedure (TRUE) or not (FALSE) */
    00463 };
    00464 #endif