coin-Cgl
CglTwomir.hpp
Go to the documentation of this file.
1 // Copyright (C) 2002, International Business Machines
2 // Corporation and others. All Rights Reserved.
3 #ifndef CglTwomir_H
4 #define CglTwomir_H
5 #include <string>
6 
7 #include "CglCutGenerator.hpp"
8 #include "CoinFactorization.hpp"
9 
10 typedef struct
11 {
12 
13  int nz; /* current length of arrays index[] and coeff[] */
14  int max_nz; /* max length of arrays index[] and coeff[] */
15  double *coeff; /* coefficient of each variable in the constraint */
16  int *index; /* index of the variable (value in 0 ... nrow+ncol) */
17  double rhs; /* rhs of the constraint */
18  char sense; /* ?? is it necessary */
19 
21 
22 typedef struct{
23  int n;
25  int *ctype;
26  double *alpha;
27 } DGG_list_t;
28 
29 /******************** BASIS INFORMATION ADTs **********************************/
30 typedef struct{
31  int q_min;
32  int q_max;
33  int t_min;
34  int t_max;
35  int a_max;
37 } cutParams;
38 
39 typedef struct
40 {
41  double gomory_threshold; /* factional variable must be this away from int */
42  int ncol, /* number of columns in LP */
43  nrow, /* number of constaints in LP */
44  ninteger; /* number of integer variables in LP */
45 
46  int nbasic_col, /* number of basic columns in the LP */
47  nbasic_row; /* number of basic rows in the LP */
48 
49  /* the following arrays are all of size (ncol+nrow) */
50  int *info; /* description of each variable (see below) */
51  double *lb; /* specifies the lower bound (if any) of each variable */
52  double *ub; /* specifies the upper bound (if any) of each variable */
53  double *x; /* current solution */
54  double *rc; /* current reduced cost */
55  double *opt_x;
56 
58 } DGG_data_t;
59 
60 /* the following macros allow us to decode the info of the DGG_data
61  type. The encoding is as follows,
62  bit 1 : if the variable is basic or not (non-basic).
63  bit 2 : if the variable is integer or or not (rational).
64  bit 3 : if the variable is structural or not (artifical).
65  bit 4 : if the variable is non-basic and at its upper bound
66  (else if non-basic at lower bound). */
67 
68 #define DGG_isBasic(data,idx) ((data->info[idx])&1)
69 #define DGG_isInteger(data,idx) ((data->info[idx] >> 1)&1)
70 #define DGG_isStructural(data,idx) ((data->info[idx] >> 2)&1)
71 #define DGG_isEqualityConstraint(data,idx) ((data->info[idx] >> 3)&1)
72 #define DGG_isNonBasicAtUB(data,idx) ((data->info[idx] >> 4)&1)
73 #define DGG_isNonBasicAtLB(data,idx) ((data->info[idx] >> 5)&1)
74 #define DGG_isConstraintBoundedAbove(data,idx) ((data->info[idx] >> 6)&1)
75 #define DGG_isConstraintBoundedBelow(data,idx) ((data->info[idx] >> 7)&1)
76 
77 #define DGG_setIsBasic(data,idx) ((data->info[idx]) |= 1)
78 #define DGG_setIsInteger(data,idx) ((data->info[idx]) |= (1<<1))
79 #define DGG_setIsStructural(data,idx) ((data->info[idx]) |= (1<<2))
80 #define DGG_setEqualityConstraint(data,idx) ((data->info[idx]) |= (1<<3))
81 #define DGG_setIsNonBasicAtUB(data,idx) ((data->info[idx]) |= (1<<4))
82 #define DGG_setIsNonBasicAtLB(data,idx) ((data->info[idx]) |= (1<<5))
83 #define DGG_setIsConstraintBoundedAbove(data,idx) ((data->info[idx]) |= (1<<6))
84 #define DGG_setIsConstraintBoundedBelow(data,idx) ((data->info[idx]) |= (1<<7))
85 
86 class CoinWarmStartBasis;
88 class CglTwomir : public CglCutGenerator {
89 
90  friend void CglTwomirUnitTest(const OsiSolverInterface * siP,
91  const std::string mpdDir );
92 
93 
94 public:
95 
97  mutable std::string probname_;
98 
104  virtual void generateCuts( const OsiSolverInterface & si, OsiCuts & cs,
105  const CglTreeInfo info = CglTreeInfo()) const;
107  virtual bool needsOptimalBasis() const;
108 
111  void setMirScale (int tmin, int tmax) {t_min_ = tmin; t_max_ = tmax;}
113  void setTwomirScale (int qmin, int qmax) {q_min_ = qmin; q_max_ = qmax;}
114  void setAMax (int a) {a_max_ = a;}
115  void setMaxElements (int n) {max_elements_ = n;}
117  void setCutTypes (bool mir, bool twomir, bool tab, bool form)
118  { do_mir_ = mir; do_2mir_ = twomir; do_tab_ = tab; do_form_ = form;}
119  void setFormulationRows (int n) {form_nrows_ = n;}
120 
122  int getTmin() const {return t_min_;}
123  int getTmax() const {return t_max_;}
124  int getQmin() const {return q_min_;}
125  int getQmax() const {return q_max_;}
126  int getAmax() const {return a_max_;}
127  int getMaxElements() const {return max_elements_;}
129  int getIfMir() const { return do_mir_;}
130  int getIfTwomir() const { return do_2mir_;}
131  int getIfTableau() const { return do_tab_;}
132  int getIfFormulation() const { return do_form_;}
134 
139  void setAway(double value);
142  double getAway() const;
144  void setAwayAtRoot(double value);
146  double getAwayAtRoot() const;
148  virtual int maximumLengthOfCutInTree() const
149  { return max_elements_;}
151 
154  CglTwomir ();
156 
158  CglTwomir (const CglTwomir &);
159 
161  virtual CglCutGenerator * clone() const;
162 
164  CglTwomir & operator=(const CglTwomir& rhs);
165 
167  virtual ~CglTwomir ();
169  virtual std::string generateCpp( FILE * fp);
171 
172 private:
173  // Private member data
176  mutable CoinThreadRandom randomNumberGenerator_;
179  double away_;
181  double awayAtRoot_;
182  bool do_mir_;
183  bool do_2mir_;
184  bool do_tab_;
185  bool do_form_;
186 
187  int t_min_;
188  int t_max_;
189  int q_min_;
190  int q_max_;
191  int a_max_;
194  int form_nrows_; //number of rows on which formulation cuts will be generated
196 };
197 
198 //#############################################################################
199 
200 /*
201 #include <stdlib.h>
202 #include <stdio.h>
203 #include <stdarg.h>
204 #include <math.h>
205 #include <float.h>
206 #include <cassert>
207 #include <iostream.h>
208 */
209 
210 /******************** DEBUG DEFINITIONS ***************************************/
211 
212 #define DGG_DEBUG_DGG 1
213 #define DGG_TRACE_ERRORS 0
214 #define DGG_DISPLAY 0
215 #define DGG_AUTO_CHECK_CUT_OFF_OPTIMAL 1
216 
217 /******************** CONFIGURATION DEFAULTS **********************************/
218 
219 #define DGG_DEFAULT_METHOD 2
220 #define DGG_DEFAULT_TMIN 1
221 #define DGG_DEFAULT_TMAX 1
222 #define DGG_DEFAULT_TAUMIN 2
223 #define DGG_DEFAULT_TAUMAX 6
224 #define DGG_DEFAULT_MAX_CUTS 500
225 #define DGG_DEFAULT_IMPROVEMENT_THRESH 0.001
226 #define DGG_DEFAULT_NBELOW_THRESH INT_MAX
227 #define DGG_DEFAULT_NROOT_ROUNDS 2
228 #define DGG_DEFAULT_NEGATIVE_SCALED_TWOSTEPS 0
229 #define DGG_DEFAULT_ALPHA_RULE 0
230 #define DGG_DEFAULT_CUT_INC 250
231 #define DGG_DEFAULT_CUT_FORM 0
232 #define DGG_DEFAULT_NICEFY 0
233 #define DGG_DEFAULT_ONLY_DELAYED 0
234 #define DGG_DEFAULT_DELAYED_FREQ 9999999
235 #define DGG_DEFAULT_LPROWS_FREQ 9999999
236 #define DGG_DEFAULT_WHICH_FORMULATION_CUTS 2
237 
238 /******************** SOLVER CONFIGURATION DEFINITIONS ************************/
239 
240 #define DGG_OSI 0
241 #define DGG_CPX 1
242 #define DGG_QSO 2
243 
244 /* determines the solver to be used */
245 #define DGG_SOLVER DGG_OSI
246 
247 /* adds checking routines to make sure solver works as expected */
248 #define DGG_DEBUG_SOLVER 0
249 
250 /* turn off screen output from solver */
251 #define DGG_SOLVER_SCREEN_FLAG 0
252 
253 /******************** CUT DEFINITIONS *****************************************/
254 
255 /* internal names for cut types */
256 #define DGG_TMIR_CUT 1
257 #define DGG_2STEP_CUT 2
258 
259 /* internal names for alpha-selection rules */
260 #define DGG_ALPHA_MIN_SUM 0
261 #define DGG_ALPHA_RANDOM_01 1
262 #define DGG_ALPHA_RANDOM_COEFF 2
263 #define DGG_ALPHA_ALL 3
264 #define DGG_ALPHA_MAX_STEEP 5
265 
266 /******************** PRECISION & NUMERICAL ISSUES DEFINITIONS ****************/
267 
268 /* how steep a cut must be before adding it to the lp */
269 #define DGG_MIN_STEEPNESS 1.0e-4
270 #define DGG_MAX_L2NORM 1.0e7
271 
272 /* 0 = min steepness, 1 = max norm */
273 #define DGG_NORM_CRITERIA 1
274 
275 /* internal representations of +infinity and -infinity */
276 #define UB_MAX DBL_MAX
277 #define LB_MIN DBL_MIN
278 
279 /* used to define how fractional a basic-integer variable must be
280  before choosing to use it to generate a TMIR cut on.
281  OSI's default is 1.0e-7 */
282 #define DGG_GOMORY_THRESH 0.005
283 
284 #define DGG_RHS_THRESH 0.005
285 
286 /* used for comparing variables to their upper bounds.
287  OSI's default is 1.0e-7.
288  We set it to 1.0e6 because e-7 seems too sensitive.
289  In fact, with e-7 the problem dsbmip.mps complains. */
290 #define DGG_BOUND_THRESH 1.0e-6
291 
292 /* used for comparing the lhs (activity) value of a tableau row
293  with the rhs. This is only used for debugging purposes. */
294 #define DGG_EQUALITY_THRESH 1.0e-5
295 
296 /* used for comparing a variable's lower bound to 0.0
297  and determining if we need to shift the variable */
298 #define DGG_SHIFT_THRESH 1.0e-6
299 
300 /* used for determing how far from an integer is still an integer.
301  This value is used for comparing coefficients to integers.
302  OSI's default is 1.0e-10. */
303 #define DGG_INTEGRALITY_THRESH 1.0e-10
304 
305 /* the min value that a coeff can have in the tableau row
306  before being set to zero. */
307 #define CBC_CHECK_CUT
308 #ifndef CBC_CHECK_CUT
309 #define DGG_MIN_TABLEAU_COEFFICIENT 1.0e-8
310 #else
311 #define DGG_MIN_TABLEAU_COEFFICIENT 1.0e-12
312 #endif
313 
314 /* smallest value rho is allowed to have for a simple 2-step MIR
315  (ie: not an extended two-step MIR) */
316 #define DGG_MIN_RHO 1.0e-7
317 #define DGG_MIN_ALPHA 1.0e-7
318 
319 /* when a slack is null: used to check if a cut is satisfied or not. */
320 #define DGG_NULL_SLACK 1.0e-5
321 
322 /* nicefy constants */
323 #define DGG_NICEFY_MIN_ABSVALUE 1.0e-13
324 #define DGG_NICEFY_MIN_FIX 1.0e-7
325 #define DGG_NICEFY_MAX_PADDING 1.0e-6
326 #define DGG_NICEFY_MAX_RATIO 1.0e9
327 
328 
329 /******************** ERROR-CATCHING MACROS ***********************************/
330 #if DGG_TRACE_ERRORS > 0
331 
332 #define __DGG_PRINT_LOC__(F) fprintf(((F==0)?stdout:F), " in %s (%s:%d)\n", __func__, __FILE__, __LINE__)
333 
334 #define DGG_THROW(A,REST...) {\
335  fprintf(stdout, ##REST); \
336  __DGG_PRINT_LOC__(stdout); \
337  return (A);}
338 
339 #define DGG_IF_EXIT(A,B,REST...) {\
340  if(A) {\
341  fprintf(stdout, ##REST); \
342  __DGG_PRINT_LOC__(stdout); \
343  exit(B);}}
344 
345 #define DGG_CHECKRVAL(A,B) {\
346  if(A) {\
347  __DGG_PRINT_LOC__(stdout); \
348  return B; } }
349 
350 #define DGG_CHECKRVAL1(A,B) {\
351  if(A) {\
352  __DGG_PRINT_LOC__(stdout); \
353  rval = B; goto CLEANUP; } }
354 
355 #define DGG_WARNING(A, REST...) {\
356  if(A) {\
357  fprintf(stdout, ##REST); \
358  __DGG_PRINT_LOC__(stdout); \
359  }}
360 
361 #define DGG_TEST(A,B,REST...) {\
362  if(A) DGG_THROW(B,##REST) }
363 
364 #define DGG_TEST2(A,B,C,REST) {DGG_TEST(A,B,C,REST) }
365 #define DGG_TEST3(A,B,C,D,REST) {DGG_TEST(A,B,C,D,REST) }
366 
367 #else
368 
369 #define DGG_IF_EXIT(A,B,REST) {if(A) {fprintf(stdout, REST);exit(B);}}
370 
371 #define DGG_THROW(A,B) return(A)
372 
373 #define DGG_CHECKRVAL(A,B) { if(A) return(B); }
374 #define DGG_CHECKRVAL1(A,B){ if(A) { rval = B; goto CLEANUP; } }
375 
376 #define DGG_TEST(A,B,REST) { if(A) return(B);}
377 #define DGG_TEST2(A,B,REST,C) { DGG_TEST(A,B,REST) }
378 #define DGG_TEST3(A,B,REST,C,D) { DGG_TEST(A,B,REST) }
379 
380 #endif
381 
382 /******************** SIMPLE MACROS AND FUNCTIONS *****************************/
383 
384 #define DGG_MIN(a,b) ( (a<b)?a:b )
385 #define DGG_MAX(a,b) ( (a>b)?a:b )
386 #define KREM(vht,alpha,tau) (DGG_MIN( ceil(vht / alpha), tau ) - 1)
387 #define LMIN(vht, d, bht) (DGG_MIN( floor(d*bht/bht), d))
388 #define ABOV(v) (v - floor(v))
389 #define QINT(vht,bht,tau) ( (int)floor( (vht*(tau-1))/bht ) )
390 #define V2I(bht,tau,i) ( ((i+1)*bht / tau) )
391 
392 int DGG_is_even(double vht, double bht, int tau, int q);
393 double frac_part(double value);
394 int DGG_is_a_multiple_of_b(double a, double b);
395 
396 
397 /* free function for DGG_data_t. Frees internal arrays and data structure */
398 int DGG_freeData( DGG_data_t *data );
399 
400 /******************** CONSTRAINT ADTs *****************************************/
401 DGG_constraint_t* DGG_newConstraint(int max_arrays);
404 void DGG_scaleConstraint(DGG_constraint_t *c, int t);
405 
406 /******************** CONFIGURATION *******************************************/
407 void DGG_list_init (DGG_list_t *l);
408 int DGG_list_addcut (DGG_list_t *l, DGG_constraint_t *cut, int ctype, double alpha);
409 void DGG_list_delcut (DGG_list_t *l, int i);
410 void DGG_list_free(DGG_list_t *l);
411 
412 /******************* SOLVER SPECIFIC METHODS **********************************/
413 DGG_data_t *DGG_getData(const void *solver_ptr);
414 
415 /******************* CONSTRAINT MANIPULATION **********************************/
416 
417 /* DGG_transformConstraint: manipulates a constraint in the following way:
418 
419 packs everything in output
420 
421 1 - variables at their upper bounds are substituted for their
422 complements. This is done by adjusting the coefficients and
423 the right hand side (simple substitution).
424 
425 2 - variables with non-zero lower bounds are shifted. */
426 
428  double **x_out,
429  double **rc_out,
430  char **isint_out,
431  DGG_constraint_t *constraint );
432 
433 /* DGG_unTransformConstraint :
434 
435 1 - Undoes step (1) of DGG_transformConstraint
436 2 - Undoes step (2) of DGG_transformConstraint */
437 
439  DGG_constraint_t *constraint );
440 
441 /* substitutes each slack variable by the structural variables which
442  define it. This function, hence, changes the constraint 'cut'. */
443 
444 int DGG_substituteSlacks( const void *solver_ptr,
445  DGG_data_t *data,
446  DGG_constraint_t *cut );
447 
448 int DGG_nicefyConstraint( const void *solver_ptr,
449  DGG_data_t *data,
450  DGG_constraint_t *cut);
451 
452 /******************* CUT GENERATION *******************************************/
453 int DGG_getFormulaConstraint( int row_idx,
454  const void *solver_ptr,
455  DGG_data_t *data,
456  DGG_constraint_t* row );
457 
458 int DGG_getTableauConstraint( int index,
459  const void *solver_ptr,
460  DGG_data_t *data,
461  DGG_constraint_t* tabrow,
462  const int * colIsBasic,
463  const int * rowIsBasic,
464  CoinFactorization & factorization,
465  int mode );
466 
467 DGG_constraint_t* DGG_getSlackExpression(const void *solver_ptr, DGG_data_t* data, int row_index);
468 
470  DGG_data_t *data,
471  const void *solver_ptr );
472 
474  DGG_data_t *data,
475  const void *solver_ptr,
476  int nrows,
477  CoinThreadRandom & generator);
478 
479 
481  double slack,
482  DGG_list_t *list,
483  DGG_data_t *data,
484  const void *solver_ptr,
485  CoinThreadRandom & generator);
486 
488  DGG_list_t *list,
489  DGG_data_t *data,
490  const void *solver_ptr );
491 
492 int DGG_buildMir( char *isint,
493  DGG_constraint_t *base,
494  DGG_constraint_t **cut_out );
495 
496 int DGG_build2step( double alpha,
497  char *isint,
498  DGG_constraint_t *base,
499  DGG_constraint_t **cut_out );
500 
502  char *isint,
503  double *x,
504  DGG_list_t *list,
505  DGG_data_t *data,
506  DGG_constraint_t *orig_base );
507 
509  char *isint,
510  double *x,
511  double *rc,
512  DGG_list_t *list,
513  DGG_data_t *data,
514  DGG_constraint_t *orig_base );
515 
516 /******************* CUT INFORMATION ******************************************/
517 
518 double DGG_cutLHS(DGG_constraint_t *c, double *x);
520 
521 /******************* TEST / DEBUGGING ROUTINES ********************************/
522 
524 
526 int DGG_is2stepValid(double alpha, double bht);
527 
528 int DGG_cutsOffPoint(double *x, DGG_constraint_t *cut);
529 
530 //#############################################################################
536 void CglTwomirUnitTest(const OsiSolverInterface * siP,
537  const std::string mpdDir);
538 
539 
540 #endif
541 
542