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

- File List
- File Members

# /home/coin/SVN-release/Cgl-0.52.0/Cgl/src/CglTwomir/CglTwomir.hpp

Go to the documentation of this file.

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