Cgl trunk
|
00001 // $Id$ 00002 // Copyright (C) 2002, International Business Machines 00003 // Corporation and others. All Rights Reserved. 00004 // This code is licensed under the terms of the Eclipse Public License (EPL). 00005 00006 #ifndef CglTwomir_H 00007 #define CglTwomir_H 00008 #include <string> 00009 00010 #include "CglCutGenerator.hpp" 00011 #include "CoinFactorization.hpp" 00012 00013 typedef struct 00014 { 00015 00016 int nz; /* current length of arrays index[] and coeff[] */ 00017 int max_nz; /* max length of arrays index[] and coeff[] */ 00018 double *coeff; /* coefficient of each variable in the constraint */ 00019 int *index; /* index of the variable (value in 0 ... nrow+ncol) */ 00020 double rhs; /* rhs of the constraint */ 00021 char sense; /* ?? is it necessary */ 00022 00023 } DGG_constraint_t; 00024 00025 typedef struct{ 00026 int n; 00027 DGG_constraint_t **c; 00028 int *ctype; 00029 double *alpha; 00030 } DGG_list_t; 00031 00032 /******************** BASIS INFORMATION ADTs **********************************/ 00033 typedef struct{ 00034 int q_min; 00035 int q_max; 00036 int t_min; 00037 int t_max; 00038 int a_max; 00039 int max_elements; 00040 } cutParams; 00041 00042 typedef struct 00043 { 00044 double gomory_threshold; /* factional variable must be this away from int */ 00045 int ncol, /* number of columns in LP */ 00046 nrow, /* number of constaints in LP */ 00047 ninteger; /* number of integer variables in LP */ 00048 00049 int nbasic_col, /* number of basic columns in the LP */ 00050 nbasic_row; /* number of basic rows in the LP */ 00051 00052 /* the following arrays are all of size (ncol+nrow) */ 00053 int *info; /* description of each variable (see below) */ 00054 double *lb; /* specifies the lower bound (if any) of each variable */ 00055 double *ub; /* specifies the upper bound (if any) of each variable */ 00056 double *x; /* current solution */ 00057 double *rc; /* current reduced cost */ 00058 double *opt_x; 00059 00060 cutParams cparams; 00061 } DGG_data_t; 00062 00063 /* the following macros allow us to decode the info of the DGG_data 00064 type. The encoding is as follows, 00065 bit 1 : if the variable is basic or not (non-basic). 00066 bit 2 : if the variable is integer or or not (rational). 00067 bit 3 : if the variable is structural or not (artifical). 00068 bit 4 : if the variable is non-basic and at its upper bound 00069 (else if non-basic at lower bound). */ 00070 00071 #define DGG_isBasic(data,idx) ((data->info[idx])&1) 00072 #define DGG_isInteger(data,idx) ((data->info[idx] >> 1)&1) 00073 #define DGG_isStructural(data,idx) ((data->info[idx] >> 2)&1) 00074 #define DGG_isEqualityConstraint(data,idx) ((data->info[idx] >> 3)&1) 00075 #define DGG_isNonBasicAtUB(data,idx) ((data->info[idx] >> 4)&1) 00076 #define DGG_isNonBasicAtLB(data,idx) ((data->info[idx] >> 5)&1) 00077 #define DGG_isConstraintBoundedAbove(data,idx) ((data->info[idx] >> 6)&1) 00078 #define DGG_isConstraintBoundedBelow(data,idx) ((data->info[idx] >> 7)&1) 00079 00080 #define DGG_setIsBasic(data,idx) ((data->info[idx]) |= 1) 00081 #define DGG_setIsInteger(data,idx) ((data->info[idx]) |= (1<<1)) 00082 #define DGG_setIsStructural(data,idx) ((data->info[idx]) |= (1<<2)) 00083 #define DGG_setEqualityConstraint(data,idx) ((data->info[idx]) |= (1<<3)) 00084 #define DGG_setIsNonBasicAtUB(data,idx) ((data->info[idx]) |= (1<<4)) 00085 #define DGG_setIsNonBasicAtLB(data,idx) ((data->info[idx]) |= (1<<5)) 00086 #define DGG_setIsConstraintBoundedAbove(data,idx) ((data->info[idx]) |= (1<<6)) 00087 #define DGG_setIsConstraintBoundedBelow(data,idx) ((data->info[idx]) |= (1<<7)) 00088 00089 class CoinWarmStartBasis; 00091 class CglTwomir : public CglCutGenerator { 00092 00093 friend void CglTwomirUnitTest(const OsiSolverInterface * siP, 00094 const std::string mpdDir ); 00095 00096 00097 public: 00098 00100 mutable std::string probname_; 00101 00107 virtual void generateCuts( const OsiSolverInterface & si, OsiCuts & cs, 00108 const CglTreeInfo info = CglTreeInfo()) const; 00110 virtual bool needsOptimalBasis() const; 00111 00114 00115 void setMirScale (int tmin, int tmax) {t_min_ = tmin; t_max_ = tmax;} 00116 void setTwomirScale (int qmin, int qmax) {q_min_ = qmin; q_max_ = qmax;} 00117 void setAMax (int a) {a_max_ = a;} 00118 void setMaxElements (int n) {max_elements_ = n;} 00119 void setMaxElementsRoot (int n) {max_elements_root_ = n;} 00120 void setCutTypes (bool mir, bool twomir, bool tab, bool form) 00121 { do_mir_ = mir; do_2mir_ = twomir; do_tab_ = tab; do_form_ = form;} 00122 void setFormulationRows (int n) {form_nrows_ = n;} 00123 00125 int getTmin() const {return t_min_;} 00126 int getTmax() const {return t_max_;} 00127 int getQmin() const {return q_min_;} 00128 int getQmax() const {return q_max_;} 00129 int getAmax() const {return a_max_;} 00130 int getMaxElements() const {return max_elements_;} 00131 int getMaxElementsRoot() const {return max_elements_root_;} 00132 int getIfMir() const { return do_mir_;} 00133 int getIfTwomir() const { return do_2mir_;} 00134 int getIfTableau() const { return do_tab_;} 00135 int getIfFormulation() const { return do_form_;} 00137 00142 00143 void setAway(double value); 00145 double getAway() const; 00147 void setAwayAtRoot(double value); 00149 double getAwayAtRoot() const; 00151 virtual int maximumLengthOfCutInTree() const 00152 { return max_elements_;} 00154 00157 00158 CglTwomir (); 00159 00161 CglTwomir (const CglTwomir &); 00162 00164 virtual CglCutGenerator * clone() const; 00165 00167 CglTwomir & operator=(const CglTwomir& rhs); 00168 00170 virtual ~CglTwomir (); 00172 virtual std::string generateCpp( FILE * fp); 00174 00175 private: 00176 // Private member data 00179 00180 mutable CoinThreadRandom randomNumberGenerator_; 00182 double away_; 00184 double awayAtRoot_; 00185 bool do_mir_; 00186 bool do_2mir_; 00187 bool do_tab_; 00188 bool do_form_; 00189 00190 int t_min_; 00191 int t_max_; 00192 int q_min_; 00193 int q_max_; 00194 int a_max_; 00195 int max_elements_; 00196 int max_elements_root_; 00197 int form_nrows_; //number of rows on which formulation cuts will be generated 00199 }; 00200 00201 //############################################################################# 00202 00203 /* 00204 #include <stdlib.h> 00205 #include <stdio.h> 00206 #include <stdarg.h> 00207 #include <math.h> 00208 #include <float.h> 00209 #include <cassert> 00210 #include <iostream.h> 00211 */ 00212 00213 /******************** DEBUG DEFINITIONS ***************************************/ 00214 00215 #define DGG_DEBUG_DGG 1 00216 #define DGG_TRACE_ERRORS 0 00217 #define DGG_DISPLAY 0 00218 #define DGG_AUTO_CHECK_CUT_OFF_OPTIMAL 1 00219 00220 /******************** CONFIGURATION DEFAULTS **********************************/ 00221 00222 #define DGG_DEFAULT_METHOD 2 00223 #define DGG_DEFAULT_TMIN 1 00224 #define DGG_DEFAULT_TMAX 1 00225 #define DGG_DEFAULT_TAUMIN 2 00226 #define DGG_DEFAULT_TAUMAX 6 00227 #define DGG_DEFAULT_MAX_CUTS 500 00228 #define DGG_DEFAULT_IMPROVEMENT_THRESH 0.001 00229 #define DGG_DEFAULT_NBELOW_THRESH INT_MAX 00230 #define DGG_DEFAULT_NROOT_ROUNDS 2 00231 #define DGG_DEFAULT_NEGATIVE_SCALED_TWOSTEPS 0 00232 #define DGG_DEFAULT_ALPHA_RULE 0 00233 #define DGG_DEFAULT_CUT_INC 250 00234 #define DGG_DEFAULT_CUT_FORM 0 00235 #define DGG_DEFAULT_NICEFY 0 00236 #define DGG_DEFAULT_ONLY_DELAYED 0 00237 #define DGG_DEFAULT_DELAYED_FREQ 9999999 00238 #define DGG_DEFAULT_LPROWS_FREQ 9999999 00239 #define DGG_DEFAULT_WHICH_FORMULATION_CUTS 2 00240 00241 /******************** SOLVER CONFIGURATION DEFINITIONS ************************/ 00242 00243 #define DGG_OSI 0 00244 #define DGG_CPX 1 00245 #define DGG_QSO 2 00246 00247 /* determines the solver to be used */ 00248 #define DGG_SOLVER DGG_OSI 00249 00250 /* adds checking routines to make sure solver works as expected */ 00251 #define DGG_DEBUG_SOLVER 0 00252 00253 /* turn off screen output from solver */ 00254 #define DGG_SOLVER_SCREEN_FLAG 0 00255 00256 /******************** CUT DEFINITIONS *****************************************/ 00257 00258 /* internal names for cut types */ 00259 #define DGG_TMIR_CUT 1 00260 #define DGG_2STEP_CUT 2 00261 00262 /* internal names for alpha-selection rules */ 00263 #define DGG_ALPHA_MIN_SUM 0 00264 #define DGG_ALPHA_RANDOM_01 1 00265 #define DGG_ALPHA_RANDOM_COEFF 2 00266 #define DGG_ALPHA_ALL 3 00267 #define DGG_ALPHA_MAX_STEEP 5 00268 00269 /******************** PRECISION & NUMERICAL ISSUES DEFINITIONS ****************/ 00270 00271 /* how steep a cut must be before adding it to the lp */ 00272 #define DGG_MIN_STEEPNESS 1.0e-4 00273 #define DGG_MAX_L2NORM 1.0e7 00274 00275 /* 0 = min steepness, 1 = max norm */ 00276 #define DGG_NORM_CRITERIA 1 00277 00278 /* internal representation of +infinity */ 00279 #define UB_MAX DBL_MAX 00280 00281 /* used to define how fractional a basic-integer variable must be 00282 before choosing to use it to generate a TMIR cut on. 00283 OSI's default is 1.0e-7 */ 00284 #define DGG_GOMORY_THRESH 0.005 00285 00286 #define DGG_RHS_THRESH 0.005 00287 00288 /* used for comparing variables to their upper bounds. 00289 OSI's default is 1.0e-7. 00290 We set it to 1.0e6 because e-7 seems too sensitive. 00291 In fact, with e-7 the problem dsbmip.mps complains. */ 00292 #define DGG_BOUND_THRESH 1.0e-6 00293 00294 /* used for comparing the lhs (activity) value of a tableau row 00295 with the rhs. This is only used for debugging purposes. */ 00296 #define DGG_EQUALITY_THRESH 1.0e-5 00297 00298 /* used for comparing a variable's lower bound to 0.0 00299 and determining if we need to shift the variable */ 00300 #define DGG_SHIFT_THRESH 1.0e-6 00301 00302 /* used for determing how far from an integer is still an integer. 00303 This value is used for comparing coefficients to integers. 00304 OSI's default is 1.0e-10. */ 00305 #define DGG_INTEGRALITY_THRESH 1.0e-10 00306 00307 /* the min value that a coeff can have in the tableau row 00308 before being set to zero. */ 00309 #define CBC_CHECK_CUT 00310 #ifndef CBC_CHECK_CUT 00311 #define DGG_MIN_TABLEAU_COEFFICIENT 1.0e-8 00312 #else 00313 #define DGG_MIN_TABLEAU_COEFFICIENT 1.0e-12 00314 #endif 00315 00316 /* smallest value rho is allowed to have for a simple 2-step MIR 00317 (ie: not an extended two-step MIR) */ 00318 #define DGG_MIN_RHO 1.0e-7 00319 #define DGG_MIN_ALPHA 1.0e-7 00320 00321 /* when a slack is null: used to check if a cut is satisfied or not. */ 00322 #define DGG_NULL_SLACK 1.0e-5 00323 00324 /* nicefy constants */ 00325 #define DGG_NICEFY_MIN_ABSVALUE 1.0e-13 00326 #define DGG_NICEFY_MIN_FIX 1.0e-7 00327 #define DGG_NICEFY_MAX_PADDING 1.0e-6 00328 #define DGG_NICEFY_MAX_RATIO 1.0e9 00329 00330 00331 /******************** ERROR-CATCHING MACROS ***********************************/ 00332 #if DGG_TRACE_ERRORS > 0 00333 00334 #define __DGG_PRINT_LOC__(F) fprintf(((F==0)?stdout:F), " in %s (%s:%d)\n", __func__, __FILE__, __LINE__) 00335 00336 #define DGG_THROW(A,REST...) {\ 00337 fprintf(stdout, ##REST); \ 00338 __DGG_PRINT_LOC__(stdout); \ 00339 return (A);} 00340 00341 #define DGG_IF_EXIT(A,B,REST...) {\ 00342 if(A) {\ 00343 fprintf(stdout, ##REST); \ 00344 __DGG_PRINT_LOC__(stdout); \ 00345 exit(B);}} 00346 00347 #define DGG_CHECKRVAL(A,B) {\ 00348 if(A) {\ 00349 __DGG_PRINT_LOC__(stdout); \ 00350 return B; } } 00351 00352 #define DGG_CHECKRVAL1(A,B) {\ 00353 if(A) {\ 00354 __DGG_PRINT_LOC__(stdout); \ 00355 rval = B; goto CLEANUP; } } 00356 00357 #define DGG_WARNING(A, REST...) {\ 00358 if(A) {\ 00359 fprintf(stdout, ##REST); \ 00360 __DGG_PRINT_LOC__(stdout); \ 00361 }} 00362 00363 #define DGG_TEST(A,B,REST...) {\ 00364 if(A) DGG_THROW(B,##REST) } 00365 00366 #define DGG_TEST2(A,B,C,REST) {DGG_TEST(A,B,C,REST) } 00367 #define DGG_TEST3(A,B,C,D,REST) {DGG_TEST(A,B,C,D,REST) } 00368 00369 #else 00370 00371 #define DGG_IF_EXIT(A,B,REST) {if(A) {fprintf(stdout, REST);exit(B);}} 00372 00373 #define DGG_THROW(A,B) return(A) 00374 00375 #define DGG_CHECKRVAL(A,B) { if(A) return(B); } 00376 #define DGG_CHECKRVAL1(A,B){ if(A) { rval = B; goto CLEANUP; } } 00377 00378 #define DGG_TEST(A,B,REST) { if(A) return(B);} 00379 #define DGG_TEST2(A,B,REST,C) { DGG_TEST(A,B,REST) } 00380 #define DGG_TEST3(A,B,REST,C,D) { DGG_TEST(A,B,REST) } 00381 00382 #endif 00383 00384 /******************** SIMPLE MACROS AND FUNCTIONS *****************************/ 00385 00386 #define DGG_MIN(a,b) ( (a<b)?a:b ) 00387 #define DGG_MAX(a,b) ( (a>b)?a:b ) 00388 #define KREM(vht,alpha,tau) (DGG_MIN( ceil(vht / alpha), tau ) - 1) 00389 #define LMIN(vht, d, bht) (DGG_MIN( floor(d*bht/bht), d)) 00390 #define ABOV(v) (v - floor(v)) 00391 #define QINT(vht,bht,tau) ( (int)floor( (vht*(tau-1))/bht ) ) 00392 #define V2I(bht,tau,i) ( ((i+1)*bht / tau) ) 00393 00394 int DGG_is_even(double vht, double bht, int tau, int q); 00395 double frac_part(double value); 00396 int DGG_is_a_multiple_of_b(double a, double b); 00397 00398 00399 /* free function for DGG_data_t. Frees internal arrays and data structure */ 00400 int DGG_freeData( DGG_data_t *data ); 00401 00402 /******************** CONSTRAINT ADTs *****************************************/ 00403 DGG_constraint_t* DGG_newConstraint(int max_arrays); 00404 void DGG_freeConstraint(DGG_constraint_t *c); 00405 DGG_constraint_t *DGG_copyConstraint(DGG_constraint_t *c); 00406 void DGG_scaleConstraint(DGG_constraint_t *c, int t); 00407 00408 /******************** CONFIGURATION *******************************************/ 00409 void DGG_list_init (DGG_list_t *l); 00410 int DGG_list_addcut (DGG_list_t *l, DGG_constraint_t *cut, int ctype, double alpha); 00411 void DGG_list_delcut (DGG_list_t *l, int i); 00412 void DGG_list_free(DGG_list_t *l); 00413 00414 /******************* SOLVER SPECIFIC METHODS **********************************/ 00415 DGG_data_t *DGG_getData(const void *solver_ptr); 00416 00417 /******************* CONSTRAINT MANIPULATION **********************************/ 00418 00419 /* DGG_transformConstraint: manipulates a constraint in the following way: 00420 00421 packs everything in output 00422 00423 1 - variables at their upper bounds are substituted for their 00424 complements. This is done by adjusting the coefficients and 00425 the right hand side (simple substitution). 00426 00427 2 - variables with non-zero lower bounds are shifted. */ 00428 00429 int DGG_transformConstraint( DGG_data_t *data, 00430 double **x_out, 00431 double **rc_out, 00432 char **isint_out, 00433 DGG_constraint_t *constraint ); 00434 00435 /* DGG_unTransformConstraint : 00436 00437 1 - Undoes step (1) of DGG_transformConstraint 00438 2 - Undoes step (2) of DGG_transformConstraint */ 00439 00440 int DGG_unTransformConstraint( DGG_data_t *data, 00441 DGG_constraint_t *constraint ); 00442 00443 /* substitutes each slack variable by the structural variables which 00444 define it. This function, hence, changes the constraint 'cut'. */ 00445 00446 int DGG_substituteSlacks( const void *solver_ptr, 00447 DGG_data_t *data, 00448 DGG_constraint_t *cut ); 00449 00450 int DGG_nicefyConstraint( const void *solver_ptr, 00451 DGG_data_t *data, 00452 DGG_constraint_t *cut); 00453 00454 /******************* CUT GENERATION *******************************************/ 00455 int DGG_getFormulaConstraint( int row_idx, 00456 const void *solver_ptr, 00457 DGG_data_t *data, 00458 DGG_constraint_t* row ); 00459 00460 int DGG_getTableauConstraint( int index, 00461 const void *solver_ptr, 00462 DGG_data_t *data, 00463 DGG_constraint_t* tabrow, 00464 const int * colIsBasic, 00465 const int * rowIsBasic, 00466 CoinFactorization & factorization, 00467 int mode ); 00468 00469 DGG_constraint_t* DGG_getSlackExpression(const void *solver_ptr, DGG_data_t* data, int row_index); 00470 00471 int DGG_generateTabRowCuts( DGG_list_t *list, 00472 DGG_data_t *data, 00473 const void *solver_ptr ); 00474 00475 int DGG_generateFormulationCuts( DGG_list_t *list, 00476 DGG_data_t *data, 00477 const void *solver_ptr, 00478 int nrows, 00479 CoinThreadRandom & generator); 00480 00481 00482 int DGG_generateFormulationCutsFromBase( DGG_constraint_t *base, 00483 double slack, 00484 DGG_list_t *list, 00485 DGG_data_t *data, 00486 const void *solver_ptr, 00487 CoinThreadRandom & generator); 00488 00489 int DGG_generateCutsFromBase( DGG_constraint_t *base, 00490 DGG_list_t *list, 00491 DGG_data_t *data, 00492 const void *solver_ptr ); 00493 00494 int DGG_buildMir( char *isint, 00495 DGG_constraint_t *base, 00496 DGG_constraint_t **cut_out ); 00497 00498 int DGG_build2step( double alpha, 00499 char *isint, 00500 DGG_constraint_t *base, 00501 DGG_constraint_t **cut_out ); 00502 00503 int DGG_addMirToList ( DGG_constraint_t *base, 00504 char *isint, 00505 double *x, 00506 DGG_list_t *list, 00507 DGG_data_t *data, 00508 DGG_constraint_t *orig_base ); 00509 00510 int DGG_add2stepToList ( DGG_constraint_t *base, 00511 char *isint, 00512 double *x, 00513 double *rc, 00514 DGG_list_t *list, 00515 DGG_data_t *data, 00516 DGG_constraint_t *orig_base ); 00517 00518 /******************* CUT INFORMATION ******************************************/ 00519 00520 double DGG_cutLHS(DGG_constraint_t *c, double *x); 00521 int DGG_isCutDesirable(DGG_constraint_t *c, DGG_data_t *d); 00522 00523 /******************* TEST / DEBUGGING ROUTINES ********************************/ 00524 00525 int DGG_isConstraintViolated(DGG_data_t *d, DGG_constraint_t *c); 00526 00527 int DGG_isBaseTrivial(DGG_data_t *d, DGG_constraint_t* c); 00528 int DGG_is2stepValid(double alpha, double bht); 00529 00530 int DGG_cutsOffPoint(double *x, DGG_constraint_t *cut); 00531 00532 //############################################################################# 00538 void CglTwomirUnitTest(const OsiSolverInterface * siP, 00539 const std::string mpdDir); 00540 00541 00542 #endif 00543 00544