Cgl 0.60.9
Loading...
Searching...
No Matches
Cgl012cut.hpp
Go to the documentation of this file.
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).
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
14typedef /* arc */
15 struct arc_st
16{
17 int len; /* length of the arc */
18 struct node_st *head; /* head node */
19}
20 arc;
21
22typedef /* 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
35typedef struct
36{
37 int length; // Length of arc
38 int to; // To node
39} cgl_arc;
40
41typedef 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
49typedef 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
60typedef struct {
61int mr; /* number of rows in the ILP matrix */
62int mc; /* number of columns in the ILP matrix */
63int mnz; /* number of nonzero's in the ILP matrix */
64int *mtbeg; /* starting position of each row in arrays mtind and mtval */
65int *mtcnt; /* number of entries of each row in arrays mtind and mtval */
66int *mtind; /* column indices of the nonzero entries of the ILP matrix */
67int *mtval; /* values of the nonzero entries of the ILP matrix */
68int *vlb; /* lower bounds on the variables */
69int *vub; /* upper bounds on the variables */
70int *mrhs; /* right hand sides of the constraints */
71char *msense; /* senses of the constraints: 'L', 'G' or 'E' */
72const double *xstar; /* current optimal solution of the LP relaxation */
73} ilp;
74
75typedef struct {
76int mr; /* number of rows in the parity ILP matrix */
77int mc; /* number of columns in the parity ILP matrix */
78int mnz; /* number of 1's in the parity ILP matrix */
79int *mtbeg; /* starting position of each row in arrays mtind and mtval */
80int *mtcnt; /* number of entries of each row in arrays mtind and mtval */
81int *mtind; /* column indices of the 1's of the parity ILP matrix */
82short int *mrhs; /* right hand side parity of the constraints */
83double *xstar; /* current optimal solution of the LP relaxation */
84double *slack; /* slack of the constraints w.r.t. xstar */
85short int *row_to_delete; /* flag for marking rows not to be considered */
86short int *col_to_delete; /* flag for marking columns not to be considered */
87int *gcd; /* greatest common divisor of each row in the input ILP matrix */
88short int *possible_weak; /* possible weakening types of each column */
89short int *type_even_weak; /* type of even weakening of each column
90 (lower or upper bound weakening) */
91short int *type_odd_weak; /* type of odd weakening of each column
92 (lower or upper bound weakening) */
93double *loss_even_weak; /* loss for the even weakening of each column */
94double *loss_odd_weak; /* loss for the odd weakening of each column */
95double *min_loss_by_weak; /* minimum loss for the weakening of each column */
96} parity_ilp;
97
98typedef struct {
99int nweak; /* number of variables weakened */
100int *var; /* list of variables weakened */
101short int *type; /* type of weakening (lower or upper bound weakening) */
102} info_weak;
103
104typedef struct {
105int endpoint1, endpoint2; /* endpoints of the edge */
106double weight; /* edge weight */
107short int parity; /* edge parity (even or odd) */
108int constr; /* constraint associated with the edge */
109info_weak *weak; /* weakening information */
110} edge;
111
112typedef struct {
113int nnodes; /* number of nodes */
114int nedges; /* number of edges */
115int *nodes; /* indexes of the ILP columns corresponding to the nodes */
116int *ind; /* indexes of the nodes corresponding to the ILP columns */
117edge **even_adj_list; /* pointers to the even edges */
118edge **odd_adj_list; /* pointers to the odd edges */
120
121#ifndef CGL_NEW_SHORT
122typedef struct {
123int nnodes; /* number of nodes */
124int narcs; /* number of arcs */
125node *nodes; /* array of the nodes - see "types_db.h" */
126arc *arcs; /* array of the arcs - see "types_db.h" */
128#else
129typedef struct {
130int nnodes; /* number of nodes */
131int narcs; /* number of arcs */
132cgl_node *nodes; /* array of the nodes - see "types_db.h" */
133cgl_arc *arcs; /* array of the arcs - see "types_db.h" */
135#endif
136
137typedef struct {
138long dist; /* distance from/to root */
139int pred; /* index of the predecessor */
141
142typedef struct {
143double weight; /* overall weight of the cycle */
144int length; /* number of edges in the cycle */
145edge **edge_list; /* list of edges in the cycle */
146} cycle;
147
148typedef struct {
149int cnum; /* overall number of cycles */
150cycle **list; /* pointers to the cycles in the list */
151} cycle_list;
152
153typedef struct {
154int n_of_constr; /* number of constraints combined to get the cut */
155int *constr_list; /* list of the constraints combined */
156short 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) */
159int cnzcnt; /* overall number of nonzero's in the cut */
160int *cind; /* column indices of the nonzero entries of the cut */
161int *cval; /* values of the nonzero entries of the cut */
162int crhs; /* right hand side of the cut */
163char csense; /* sense of the cut: 'L', 'G' or 'E' */
164double violation; /* violation of the cut w.r.t. the current LP solution */
165} cut;
166
167typedef struct {
168int cnum; /* overall number of cuts */
169cut **list; /* pointers to the cuts in the list */
170} cut_list;
171
172typedef struct {
173int n_of_constr; /* number of constraints combined to get the cut */
174int *constr_list; /* list of the constraints combined */
175int code; /* identifier of the cut */
176int 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 */
179int it_found; /* iteration in which the cut was separated */
180double score; /* score of the cut, used to choose wich cut should be
181 added to the current LP (if any) */
182} pool_cut;
183
184typedef struct {
185int cnum; /* overall number of cuts */
186pool_cut **list; /* pointers to the cuts in the list */
187int *ncod; /* number of cuts with a given code in the pool */
189
190typedef struct {
191int *ccoef; /* coefficients of the cut */
192int crhs; /* right hand side of the cut */
193int pool_index; /* index of the cut in the pool */
194double score; /* cut score (to be maximized) */
195} select_cut;
196
197typedef struct {
198int 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;
208
209public:
210
214/*
215 INPUT parameters:
216*/
217int mr, /* number of rows in the ILP matrix */
218int mc, /* number of columns in the ILP matrix */
219int mnz, /* number of nonzero's in the ILP matrix */
220int *mtbeg, /* starting position of each row in arrays mtind and mtval */
221int *mtcnt, /* number of entries of each row in arrays mtind and mtval */
222int *mtind, /* column indices of the nonzero entries of the ILP matrix */
223int *mtval, /* values of the nonzero entries of the ILP matrix */
224int *vlb, /* lower bounds on the variables */
225int *vub, /* upper bounds on the variables */
226int *mrhs, /* right hand sides of the constraints */
227char *msense, /* senses of the constraints: 'L', 'G' or 'E' */
228const double *xstar, /* current optimal solution of the LP relaxation */
229bool 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*/
235int *cnum, /* number of violated 0-1/2 cuts identified by the procedure */
236int *cnzcnt, /* overall number of nonzero's in the cuts */
237int **cbeg, /* starting position of each cut in arrays cind and cval */
238int **ccnt, /* number of entries of each cut in arrays cind and cval */
239int **cind, /* column indices of the nonzero entries of the cuts */
240int **cval, /* values of the nonzero entries of the cuts */
241int **crhs, /* right hand sides of the cuts */
242char **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 );
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 );
263void free_ilp();
264/* alloc_parity_ilp: allocate the memory for the parity ILP data structure */
265
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 );
273/* free_log_var */
275private:
276/* best_weakening: find the best upper/lower bound weakening of a set
277 of variables */
278
280 int n_to_weak, /* number of variables to weaken */
281int *vars_to_weak, /* indices of the variables to weaken */
282short int original_parity, /* original parity of the constraint to weaken */
283double original_slack, /* original slack of the constraint to weaken */
284double *best_even_slack, /* best possible slack of a weakened constraint
285 with even right-hand-side */
286double *best_odd_slack, /* best possible slack of a weakened constraint
287 with odd right-hand-side */
288info_weak **info_even_weak, /* weakening information about the best possible
289 even weakened constraint */
290info_weak **info_odd_weak, /* weakening information about the best possible
291 odd weakened constraint */
292short int only_odd, /* flag which tells whether only an odd weakening is of
293 interest (TRUE) or both weakenings are (FALSE) */
294short 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
303short 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
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 */
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
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
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
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
359/* initialize: initialize the data structures for local search */
360
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 */);
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
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
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
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
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
413/* print_cur_cut: display cur_cut on output */
414
418public:
423
426 const Cgl012Cut &);
427
429 Cgl012Cut &
431 const Cgl012Cut& rhs);
432
434 virtual ~Cgl012Cut ();
436
437private:
438
439 // Private member methods
440
444
445
448
449ilp *inp_ilp; /* input ILP data structure */
450parity_ilp *p_ilp; /* parity ILP data structure */
452double gap;
453double maxgap;
455int sep_iter; /* number of the current separation iteration */
456log_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 */
460bool aggr; /* flag saying whether as many cuts as possible are required
461 from the separation procedure (TRUE) or not (FALSE) */
463};
464#endif
012Cut Generator Class
void free_ilp()
separation_graph * initialize_sep_graph()
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)
log_var ** vlog
cut_list * tabu_012()
void alloc_parity_ilp(int mr, int mc, int mnz)
cut * get_cut(cycle *s_cyc)
double score_by_moving(int i, short int itype, double thresh)
short int get_ori_cut_coef(int n_of_constr, int *constr_list, int *ccoef, int *crhs, short int only_viol)
double gap
void print_cur_cut()
void free_log_var()
cut * get_current_cut()
void modify_current(int i, short int itype)
void initialize_log_var()
void print_constr(int i)
void print_cut_list(cut_list *cuts)
void print_parity_ilp()
void add_tight_constraint()
Cgl012Cut(const Cgl012Cut &)
Copy constructor.
double maxgap
Cgl012Cut()
Default constructor.
virtual ~Cgl012Cut()
Destructor.
double cut_score(int *ccoef, int crhs, double viol, short int only_viol)
short int best_neighbour(cut_list *out_cuts)
cut_list * basic_separation()
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)
cut * define_cut(int *ccoef, int crhs)
parity_ilp * p_ilp
void get_parity_ilp()
void print_cut(cut *v_cut)
Cgl012Cut & operator=(const Cgl012Cut &rhs)
Assignment operator.
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)
void free_parity_ilp()
short int best_cut(int *ccoef, int *crhs, double *violation, short int update, short int only_viol)
ilp * inp_ilp
void initialize()
void restart(short int failure)
void update_log_var()
cgl_node * nodes
int length
Definition Cgl012cut.hpp:37
cgl_node * nodes
Definition Cgl012cut.hpp:53
cgl_arc * arcs
Definition Cgl012cut.hpp:54
int distanceBack
Definition Cgl012cut.hpp:46
cgl_arc * firstArc
Definition Cgl012cut.hpp:43
int parentNode
Definition Cgl012cut.hpp:44
cut ** list
char csense
int * constr_list
int crhs
int cnzcnt
int * cind
int * cval
double violation
short int * in_constr_list
int n_of_constr
cycle ** list
int length
double weight
edge ** edge_list
int constr
short int parity
info_weak * weak
int endpoint1
double weight
int * mtcnt
Definition Cgl012cut.hpp:65
int * mtbeg
Definition Cgl012cut.hpp:64
int * mtval
Definition Cgl012cut.hpp:67
int * vlb
Definition Cgl012cut.hpp:68
int * mrhs
Definition Cgl012cut.hpp:70
int mr
Definition Cgl012cut.hpp:61
const double * xstar
Definition Cgl012cut.hpp:72
int mnz
Definition Cgl012cut.hpp:63
int * vub
Definition Cgl012cut.hpp:69
int mc
Definition Cgl012cut.hpp:62
int * mtind
Definition Cgl012cut.hpp:66
char * msense
Definition Cgl012cut.hpp:71
short int * type
int n_it_zero
double * loss_even_weak
Definition Cgl012cut.hpp:93
short int * col_to_delete
Definition Cgl012cut.hpp:86
short int * possible_weak
Definition Cgl012cut.hpp:88
double * min_loss_by_weak
Definition Cgl012cut.hpp:95
double * slack
Definition Cgl012cut.hpp:84
int * mtbeg
Definition Cgl012cut.hpp:79
short int * type_even_weak
Definition Cgl012cut.hpp:89
int * mtind
Definition Cgl012cut.hpp:81
double * xstar
Definition Cgl012cut.hpp:83
short int * mrhs
Definition Cgl012cut.hpp:82
int * mtcnt
Definition Cgl012cut.hpp:80
double * loss_odd_weak
Definition Cgl012cut.hpp:94
short int * row_to_delete
Definition Cgl012cut.hpp:85
short int * type_odd_weak
Definition Cgl012cut.hpp:91
pool_cut ** list
int * constr_list
int n_it_violated
int n_of_constr
double score
double score
edge ** even_adj_list