00001
00002
00003 #ifndef CglTwomir_H
00004 #define CglTwomir_H
00005 #include <string>
00006
00007 #include "CglCutGenerator.hpp"
00008 #include "CoinFactorization.hpp"
00009
00010 typedef struct
00011 {
00012
00013 int nz;
00014 int max_nz;
00015 double *coeff;
00016 int *index;
00017 double rhs;
00018 char sense;
00019
00020 } DGG_constraint_t;
00021
00022 typedef struct{
00023 int n;
00024 DGG_constraint_t **c;
00025 int *ctype;
00026 double *alpha;
00027 } DGG_list_t;
00028
00029
00030 typedef struct{
00031 int q_min;
00032 int q_max;
00033 int t_min;
00034 int t_max;
00035 int a_max;
00036 int max_elements;
00037 } cutParams;
00038
00039 typedef struct
00040 {
00041 int ncol,
00042 nrow,
00043 ninteger;
00044
00045 int nbasic_col,
00046 nbasic_row;
00047
00048
00049 int *info;
00050 double *lb;
00051 double *ub;
00052 double *x;
00053 double *rc;
00054 double *opt_x;
00055
00056 cutParams cparams;
00057 } DGG_data_t;
00058
00059
00060
00061
00062
00063
00064
00065
00066
00067 #define DGG_isBasic(data,idx) ((data->info[idx])&1)
00068 #define DGG_isInteger(data,idx) ((data->info[idx] >> 1)&1)
00069 #define DGG_isStructural(data,idx) ((data->info[idx] >> 2)&1)
00070 #define DGG_isEqualityConstraint(data,idx) ((data->info[idx] >> 3)&1)
00071 #define DGG_isNonBasicAtUB(data,idx) ((data->info[idx] >> 4)&1)
00072 #define DGG_isNonBasicAtLB(data,idx) ((data->info[idx] >> 5)&1)
00073 #define DGG_isConstraintBoundedAbove(data,idx) ((data->info[idx] >> 6)&1)
00074 #define DGG_isConstraintBoundedBelow(data,idx) ((data->info[idx] >> 7)&1)
00075
00076 #define DGG_setIsBasic(data,idx) ((data->info[idx]) |= 1)
00077 #define DGG_setIsInteger(data,idx) ((data->info[idx]) |= (1<<1))
00078 #define DGG_setIsStructural(data,idx) ((data->info[idx]) |= (1<<2))
00079 #define DGG_setEqualityConstraint(data,idx) ((data->info[idx]) |= (1<<3))
00080 #define DGG_setIsNonBasicAtUB(data,idx) ((data->info[idx]) |= (1<<4))
00081 #define DGG_setIsNonBasicAtLB(data,idx) ((data->info[idx]) |= (1<<5))
00082 #define DGG_setIsConstraintBoundedAbove(data,idx) ((data->info[idx]) |= (1<<6))
00083 #define DGG_setIsConstraintBoundedBelow(data,idx) ((data->info[idx]) |= (1<<7))
00084
00085 class CoinWarmStartBasis;
00087 class CglTwomir : public CglCutGenerator {
00088
00089 friend void CglTwomirUnitTest(const OsiSolverInterface * siP,
00090 const std::string mpdDir );
00091
00092
00093 public:
00094
00096 mutable std::string probname_;
00097
00103 virtual void generateCuts( const OsiSolverInterface & si, OsiCuts & cs,
00104 const CglTreeInfo info = CglTreeInfo()) const;
00106 virtual bool needsOptimalBasis() const;
00107
00110
00111 void setMirScale (int tmin, int tmax) {t_min_ = tmin; t_max_ = tmax;}
00112 void setTwomirScale (int qmin, int qmax) {q_min_ = qmin; q_max_ = qmax;}
00113 void setAMax (int a) {a_max_ = a;}
00114 void setMaxElements (int n) {max_elements_ = n;}
00115 void setMaxElementsRoot (int n) {max_elements_root_ = n;}
00116 void setCutTypes (bool mir, bool twomir, bool tab, bool form)
00117 { do_mir_ = mir; do_2mir_ = twomir; do_tab_ = tab; do_form_ = form;}
00118 void setFormulationRows (int n) {form_nrows_ = n;}
00119
00121 int getTmin() const {return t_min_;}
00122 int getTmax() const {return t_max_;}
00123 int getQmin() const {return q_min_;}
00124 int getQmax() const {return q_max_;}
00125 int getAmax() const {return a_max_;}
00126 int getMaxElements() const {return max_elements_;}
00127 int getMaxElementsRoot() const {return max_elements_root_;}
00128 int getIfMir() const { return do_mir_;}
00129 int getIfTwomir() const { return do_2mir_;}
00130 int getIfTableau() const { return do_tab_;}
00131 int getIfFormulation() const { return do_form_;}
00133
00136
00137 CglTwomir ();
00138
00140 CglTwomir (const CglTwomir &);
00141
00143 virtual CglCutGenerator * clone() const;
00144
00146 CglTwomir & operator=(const CglTwomir& rhs);
00147
00149 virtual ~CglTwomir ();
00151 virtual std::string generateCpp( FILE * fp);
00153
00154 private:
00155
00158 bool do_mir_;
00159 bool do_2mir_;
00160 bool do_tab_;
00161 bool do_form_;
00162
00163 int t_min_;
00164 int t_max_;
00165 int q_min_;
00166 int q_max_;
00167 int a_max_;
00168 int max_elements_;
00169 int max_elements_root_;
00170 int form_nrows_;
00172 };
00173
00174
00175
00176
00177
00178
00179
00180
00181
00182
00183
00184
00185
00186
00187
00188 #define DGG_DEBUG_DGG 1
00189 #define DGG_TRACE_ERRORS 0
00190 #define DGG_DISPLAY 0
00191 #define DGG_AUTO_CHECK_CUT_OFF_OPTIMAL 1
00192
00193
00194
00195 #define DGG_DEFAULT_METHOD 2
00196 #define DGG_DEFAULT_TMIN 1
00197 #define DGG_DEFAULT_TMAX 1
00198 #define DGG_DEFAULT_TAUMIN 2
00199 #define DGG_DEFAULT_TAUMAX 6
00200 #define DGG_DEFAULT_MAX_CUTS 500
00201 #define DGG_DEFAULT_IMPROVEMENT_THRESH 0.001
00202 #define DGG_DEFAULT_NBELOW_THRESH INT_MAX
00203 #define DGG_DEFAULT_NROOT_ROUNDS 2
00204 #define DGG_DEFAULT_NEGATIVE_SCALED_TWOSTEPS 0
00205 #define DGG_DEFAULT_ALPHA_RULE 0
00206 #define DGG_DEFAULT_CUT_INC 250
00207 #define DGG_DEFAULT_CUT_FORM 0
00208 #define DGG_DEFAULT_NICEFY 0
00209 #define DGG_DEFAULT_ONLY_DELAYED 0
00210 #define DGG_DEFAULT_DELAYED_FREQ 9999999
00211 #define DGG_DEFAULT_LPROWS_FREQ 9999999
00212 #define DGG_DEFAULT_WHICH_FORMULATION_CUTS 2
00213
00214
00215
00216 #define DGG_OSI 0
00217 #define DGG_CPX 1
00218 #define DGG_QSO 2
00219
00220
00221 #define DGG_SOLVER DGG_OSI
00222
00223
00224 #define DGG_DEBUG_SOLVER 0
00225
00226
00227 #define DGG_SOLVER_SCREEN_FLAG 0
00228
00229
00230
00231
00232 #define DGG_TMIR_CUT 1
00233 #define DGG_2STEP_CUT 2
00234
00235
00236 #define DGG_ALPHA_MIN_SUM 0
00237 #define DGG_ALPHA_RANDOM_01 1
00238 #define DGG_ALPHA_RANDOM_COEFF 2
00239 #define DGG_ALPHA_ALL 3
00240 #define DGG_ALPHA_MAX_STEEP 5
00241
00242
00243
00244
00245 #define DGG_MIN_STEEPNESS 1.0e-4
00246 #define DGG_MAX_L2NORM 1.0e7
00247
00248
00249 #define DGG_NORM_CRITERIA 1
00250
00251
00252 #define UB_MAX DBL_MAX
00253 #define LB_MIN DBL_MIN
00254
00255
00256
00257
00258 #define DGG_GOMORY_THRESH 0.005
00259
00260 #define DGG_RHS_THRESH 0.005
00261
00262
00263
00264
00265
00266 #define DGG_BOUND_THRESH 1.0e-6
00267
00268
00269
00270 #define DGG_EQUALITY_THRESH 1.0e-5
00271
00272
00273
00274 #define DGG_SHIFT_THRESH 1.0e-6
00275
00276
00277
00278
00279 #define DGG_INTEGRALITY_THRESH 1.0e-10
00280
00281
00282
00283 #define CBC_CHECK_CUT
00284 #ifndef CBC_CHECK_CUT
00285 #define DGG_MIN_TABLEAU_COEFFICIENT 1.0e-8
00286 #else
00287 #define DGG_MIN_TABLEAU_COEFFICIENT 1.0e-12
00288 #endif
00289
00290
00291
00292 #define DGG_MIN_RHO 1.0e-7
00293 #define DGG_MIN_ALPHA 1.0e-7
00294
00295
00296 #define DGG_NULL_SLACK 1.0e-5
00297
00298
00299 #define DGG_NICEFY_MIN_ABSVALUE 1.0e-13
00300 #define DGG_NICEFY_MIN_FIX 1.0e-7
00301 #define DGG_NICEFY_MAX_PADDING 1.0e-6
00302 #define DGG_NICEFY_MAX_RATIO 1.0e9
00303
00304
00305
00306 #if DGG_TRACE_ERRORS > 0
00307
00308 #define __DGG_PRINT_LOC__(F) fprintf(((F==0)?stdout:F), " in %s (%s:%d)\n", __func__, __FILE__, __LINE__)
00309
00310 #define DGG_THROW(A,REST...) {\
00311 fprintf(stdout, ##REST); \
00312 __DGG_PRINT_LOC__(stdout); \
00313 return (A);}
00314
00315 #define DGG_IF_EXIT(A,B,REST...) {\
00316 if(A) {\
00317 fprintf(stdout, ##REST); \
00318 __DGG_PRINT_LOC__(stdout); \
00319 exit(B);}}
00320
00321 #define DGG_CHECKRVAL(A,B) {\
00322 if(A) {\
00323 __DGG_PRINT_LOC__(stdout); \
00324 return B; } }
00325
00326 #define DGG_CHECKRVAL1(A,B) {\
00327 if(A) {\
00328 __DGG_PRINT_LOC__(stdout); \
00329 rval = B; goto CLEANUP; } }
00330
00331 #define DGG_WARNING(A, REST...) {\
00332 if(A) {\
00333 fprintf(stdout, ##REST); \
00334 __DGG_PRINT_LOC__(stdout); \
00335 }}
00336
00337 #define DGG_TEST(A,B,REST...) {\
00338 if(A) DGG_THROW(B,##REST) }
00339
00340 #define DGG_TEST2(A,B,C,REST) {DGG_TEST(A,B,C,REST) }
00341 #define DGG_TEST3(A,B,C,D,REST) {DGG_TEST(A,B,C,D,REST) }
00342
00343 #else
00344
00345 #define DGG_IF_EXIT(A,B,REST) {if(A) {fprintf(stdout, REST);exit(B);}}
00346
00347 #define DGG_THROW(A,B) return(A)
00348
00349 #define DGG_CHECKRVAL(A,B) { if(A) return(B); }
00350 #define DGG_CHECKRVAL1(A,B){ if(A) { rval = B; goto CLEANUP; } }
00351
00352 #define DGG_TEST(A,B,REST) { if(A) return(B);}
00353 #define DGG_TEST2(A,B,REST,C) { DGG_TEST(A,B,REST) }
00354 #define DGG_TEST3(A,B,REST,C,D) { DGG_TEST(A,B,REST) }
00355
00356 #endif
00357
00358
00359
00360 #define DGG_MIN(a,b) ( (a<b)?a:b )
00361 #define DGG_MAX(a,b) ( (a>b)?a:b )
00362 #define KREM(vht,alpha,tau) (DGG_MIN( ceil(vht / alpha), tau ) - 1)
00363 #define LMIN(vht, d, bht) (DGG_MIN( floor(d*bht/bht), d))
00364 #define ABOV(v) (v - floor(v))
00365 #define QINT(vht,bht,tau) ( (int)floor( (vht*(tau-1))/bht ) )
00366 #define V2I(bht,tau,i) ( ((i+1)*bht / tau) )
00367
00368 int DGG_is_even(double vht, double bht, int tau, int q);
00369 double frac_part(double value);
00370 int DGG_is_a_multiple_of_b(double a, double b);
00371
00372
00373
00374 int DGG_freeData( DGG_data_t *data );
00375
00376
00377 DGG_constraint_t* DGG_newConstraint(int max_arrays);
00378 void DGG_freeConstraint(DGG_constraint_t *c);
00379 DGG_constraint_t *DGG_copyConstraint(DGG_constraint_t *c);
00380 void DGG_scaleConstraint(DGG_constraint_t *c, int t);
00381
00382
00383 void DGG_list_init (DGG_list_t *l);
00384 int DGG_list_addcut (DGG_list_t *l, DGG_constraint_t *cut, int ctype, double alpha);
00385 void DGG_list_delcut (DGG_list_t *l, int i);
00386 void DGG_list_free(DGG_list_t *l);
00387
00388
00389 DGG_data_t *DGG_getData(const void *solver_ptr);
00390
00391
00392
00393
00394
00395
00396
00397
00398
00399
00400
00401
00402
00403 int DGG_transformConstraint( DGG_data_t *data,
00404 double **x_out,
00405 double **rc_out,
00406 char **isint_out,
00407 DGG_constraint_t *constraint );
00408
00409
00410
00411
00412
00413
00414 int DGG_unTransformConstraint( DGG_data_t *data,
00415 DGG_constraint_t *constraint );
00416
00417
00418
00419
00420 int DGG_substituteSlacks( const void *solver_ptr,
00421 DGG_data_t *data,
00422 DGG_constraint_t *cut );
00423
00424 int DGG_nicefyConstraint( const void *solver_ptr,
00425 DGG_data_t *data,
00426 DGG_constraint_t *cut);
00427
00428
00429 int DGG_getFormulaConstraint( int row_idx,
00430 const void *solver_ptr,
00431 DGG_data_t *data,
00432 DGG_constraint_t* row );
00433
00434 int DGG_getTableauConstraint( int index,
00435 const void *solver_ptr,
00436 DGG_data_t *data,
00437 DGG_constraint_t* tabrow,
00438 const int * colIsBasic,
00439 const int * rowIsBasic,
00440 CoinFactorization & factorization,
00441 int mode );
00442
00443 DGG_constraint_t* DGG_getSlackExpression(const void *solver_ptr, DGG_data_t* data, int row_index);
00444
00445 int DGG_generateTabRowCuts( DGG_list_t *list,
00446 DGG_data_t *data,
00447 const void *solver_ptr );
00448
00449 int DGG_generateFormulationCuts( DGG_list_t *list,
00450 DGG_data_t *data,
00451 const void *solver_ptr,
00452 int nrows);
00453
00454
00455 int DGG_generateFormulationCutsFromBase( DGG_constraint_t *base,
00456 double slack,
00457 DGG_list_t *list,
00458 DGG_data_t *data,
00459 const void *solver_ptr );
00460
00461 int DGG_generateCutsFromBase( DGG_constraint_t *base,
00462 DGG_list_t *list,
00463 DGG_data_t *data,
00464 const void *solver_ptr );
00465
00466 int DGG_buildMir( char *isint,
00467 DGG_constraint_t *base,
00468 DGG_constraint_t **cut_out );
00469
00470 int DGG_build2step( double alpha,
00471 char *isint,
00472 DGG_constraint_t *base,
00473 DGG_constraint_t **cut_out );
00474
00475 int DGG_addMirToList ( DGG_constraint_t *base,
00476 char *isint,
00477 double *x,
00478 DGG_list_t *list,
00479 DGG_data_t *data,
00480 DGG_constraint_t *orig_base );
00481
00482 int DGG_add2stepToList ( DGG_constraint_t *base,
00483 char *isint,
00484 double *x,
00485 double *rc,
00486 DGG_list_t *list,
00487 DGG_data_t *data,
00488 DGG_constraint_t *orig_base );
00489
00490
00491
00492 double DGG_cutLHS(DGG_constraint_t *c, double *x);
00493 int DGG_isCutDesirable(DGG_constraint_t *c, DGG_data_t *d);
00494
00495
00496
00497 int DGG_isConstraintViolated(DGG_data_t *d, DGG_constraint_t *c);
00498
00499 int DGG_isBaseTrivial(DGG_data_t *d, DGG_constraint_t* c);
00500 int DGG_is2stepValid(double alpha, double bht);
00501
00502 int DGG_cutsOffPoint(double *x, DGG_constraint_t *cut);
00503
00504
00510 void CglTwomirUnitTest(const OsiSolverInterface * siP,
00511 const std::string mpdDir);
00512
00513
00514 #endif
00515
00516