/home/coin/SVN-release/Cbc-1.1.1/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 public:
00091   char *probname_;
00092     
00098   virtual void generateCuts( const OsiSolverInterface & si, OsiCuts & cs, 
00099                              const CglTreeInfo info = CglTreeInfo()) const;
00101   virtual bool needsOptimalBasis() const;
00102 
00105 
00106   void setMirScale (int tmin, int tmax) {t_min_ = tmin; t_max_ = tmax;}
00107   void setTwomirScale (int qmin, int qmax) {q_min_ = qmin; q_max_ = qmax;}
00108   void setAMax (int a) {a_max_ = a;}
00109   void setMaxElements (int n) {max_elements_ = n;}
00110   void setCutTypes (bool mir, bool twomir, bool tab, bool form)
00111   { do_mir_ = mir; do_2mir_ = twomir; do_tab_ = tab; do_form_ = form;}
00112   void setFormulationRows (int n) {form_nrows_ = n;}
00113 
00115   int getTmin() const {return t_min_;}
00116   int getTmax() const {return t_max_;}
00117   int getQmin() const {return q_min_;}
00118   int getQmax() const {return q_max_;}
00119   int getAmax() const {return a_max_;}
00120   int getMaxElements() const {return max_elements_;}
00121   int getIfMir() const { return do_mir_;}
00122   int getIfTwomir() const { return do_2mir_;}
00123   int getIfTableau() const { return do_tab_;}
00124   int getIfFormulation() const { return do_form_;}
00126 
00129 
00130   CglTwomir ();
00131 
00133   CglTwomir (const CglTwomir &);
00134 
00136   virtual CglCutGenerator * clone() const;
00137 
00139   CglTwomir & operator=(const CglTwomir& rhs);
00140   
00142   virtual  ~CglTwomir ();
00144   virtual std::string generateCpp( FILE * fp);
00146       
00147 private:
00148   // Private member data
00151   bool do_mir_;
00152   bool do_2mir_;
00153   bool do_tab_;
00154   bool do_form_;
00155 
00156   int t_min_;  
00157   int t_max_;  
00158   int q_min_;  
00159   int q_max_;  
00160   int a_max_;  
00161   int max_elements_; 
00162 
00163   int form_nrows_; //number of rows on which formulation cuts will be generated
00165 };
00166 
00167 //#############################################################################
00168 
00169 /*
00170 #include <stdlib.h>
00171 #include <stdio.h>
00172 #include <stdarg.h>
00173 #include <math.h>
00174 #include <float.h>
00175 #include <assert.h>
00176 #include <iostream.h>
00177 */
00178 
00179 /******************** DEBUG DEFINITIONS ***************************************/
00180 
00181 #define DGG_DEBUG_DGG 1
00182 #define DGG_TRACE_ERRORS 0
00183 #define DGG_DISPLAY   0
00184 #define DGG_AUTO_CHECK_CUT_OFF_OPTIMAL 1
00185 
00186 /******************** CONFIGURATION DEFAULTS **********************************/
00187 
00188 #define DGG_DEFAULT_METHOD 2
00189 #define DGG_DEFAULT_TMIN 1
00190 #define DGG_DEFAULT_TMAX 1
00191 #define DGG_DEFAULT_TAUMIN 2
00192 #define DGG_DEFAULT_TAUMAX 6
00193 #define DGG_DEFAULT_MAX_CUTS 500
00194 #define DGG_DEFAULT_IMPROVEMENT_THRESH 0.001
00195 #define DGG_DEFAULT_NBELOW_THRESH INT_MAX 
00196 #define DGG_DEFAULT_NROOT_ROUNDS 2
00197 #define DGG_DEFAULT_NEGATIVE_SCALED_TWOSTEPS 0
00198 #define DGG_DEFAULT_ALPHA_RULE 0
00199 #define DGG_DEFAULT_CUT_INC 250
00200 #define DGG_DEFAULT_CUT_FORM 0
00201 #define DGG_DEFAULT_NICEFY 0
00202 #define DGG_DEFAULT_ONLY_DELAYED 0
00203 #define DGG_DEFAULT_DELAYED_FREQ 9999999 
00204 #define DGG_DEFAULT_LPROWS_FREQ 9999999
00205 #define DGG_DEFAULT_WHICH_FORMULATION_CUTS 2
00206 
00207 /******************** SOLVER CONFIGURATION DEFINITIONS ************************/
00208 
00209 #define DGG_OSI 0
00210 #define DGG_CPX 1
00211 #define DGG_QSO 2
00212 
00213 /* determines the solver to be used */
00214 #define DGG_SOLVER DGG_OSI
00215 
00216 /* adds checking routines to make sure solver works as expected */
00217 #define DGG_DEBUG_SOLVER 0
00218 
00219 /* turn off screen output from solver */
00220 #define DGG_SOLVER_SCREEN_FLAG 0
00221 
00222 /******************** CUT DEFINITIONS *****************************************/
00223 
00224 /* internal names for cut types */
00225 #define DGG_TMIR_CUT 1
00226 #define DGG_2STEP_CUT 2
00227 
00228 /* internal names for alpha-selection rules */
00229 #define DGG_ALPHA_MIN_SUM 0
00230 #define DGG_ALPHA_RANDOM_01 1
00231 #define DGG_ALPHA_RANDOM_COEFF 2
00232 #define DGG_ALPHA_ALL 3
00233 #define DGG_ALPHA_MAX_STEEP 5
00234 
00235 /******************** PRECISION & NUMERICAL ISSUES DEFINITIONS ****************/
00236 
00237 /* how steep a cut must be before adding it to the lp */
00238 #define DGG_MIN_STEEPNESS 1.0e-4
00239 #define DGG_MAX_L2NORM 1.0e7
00240 
00241 /* 0 = min steepness, 1 = max norm */
00242 #define DGG_NORM_CRITERIA 1
00243 
00244 /* internal representations of +infinity and -infinity */
00245 #define UB_MAX DBL_MAX
00246 #define LB_MIN DBL_MIN
00247 
00248 /* used to define how fractional a basic-integer variable must be
00249    before choosing to use it to generate a TMIR cut on.
00250    OSI's default is 1.0e-7 */
00251 #define DGG_GOMORY_THRESH 0.005
00252 
00253 #define DGG_RHS_THRESH 0.005
00254 
00255 /* used for comparing variables to their upper bounds.
00256    OSI's default is 1.0e-7.
00257    We set it to 1.0e6 because e-7 seems too sensitive. 
00258    In fact, with e-7 the problem dsbmip.mps complains. */
00259 #define DGG_BOUND_THRESH 1.0e-6
00260 
00261 /* used for comparing the lhs (activity) value of a tableau row
00262    with the rhs. This is only used for debugging purposes. */
00263 #define DGG_EQUALITY_THRESH 1.0e-5
00264 
00265 /* used for comparing a variable's lower bound to 0.0
00266    and determining if we need to shift the variable    */
00267 #define DGG_SHIFT_THRESH 1.0e-6
00268 
00269 /* used for determing how far from an integer is still an integer.
00270    This value is used for comparing coefficients to integers.
00271    OSI's default is 1.0e-10.                               */
00272 #define DGG_INTEGRALITY_THRESH 1.0e-10
00273 
00274 /* the min value that a coeff can have in the tableau row
00275    before being set to zero. */
00276 #define DGG_MIN_TABLEAU_COEFFICIENT 1.0e-8
00277 
00278 /* smallest value rho is allowed to have for a simple 2-step MIR
00279    (ie: not an extended two-step MIR) */
00280 #define DGG_MIN_RHO 1.0e-7
00281 #define DGG_MIN_ALPHA 1.0e-7
00282 
00283 /* when a slack is null: used to check if a cut is satisfied or not. */
00284 #define DGG_NULL_SLACK 1.0e-5
00285 
00286 /* nicefy constants */
00287 #define DGG_NICEFY_MIN_ABSVALUE 1.0e-13
00288 #define DGG_NICEFY_MIN_FIX 1.0e-7
00289 #define DGG_NICEFY_MAX_PADDING 1.0e-6
00290 #define DGG_NICEFY_MAX_RATIO 1.0e9
00291 
00292 
00293 /******************** ERROR-CATCHING MACROS ***********************************/
00294 #if DGG_TRACE_ERRORS > 0
00295 
00296 #define __DGG_PRINT_LOC__(F) fprintf(((F==0)?stdout:F), " in %s (%s:%d)\n", __func__, __FILE__, __LINE__)
00297 
00298 #define DGG_THROW(A,REST...) {\
00299  fprintf(stdout, ##REST); \
00300  __DGG_PRINT_LOC__(stdout); \
00301  return (A);}
00302 
00303 #define DGG_IF_EXIT(A,B,REST...) {\
00304  if(A) {\
00305  fprintf(stdout, ##REST); \
00306  __DGG_PRINT_LOC__(stdout); \
00307  exit(B);}}
00308 
00309 #define DGG_CHECKRVAL(A,B) {\
00310  if(A) {\
00311    __DGG_PRINT_LOC__(stdout); \
00312    return B; } }
00313 
00314 #define DGG_CHECKRVAL1(A,B) {\
00315  if(A) {\
00316    __DGG_PRINT_LOC__(stdout); \
00317    rval = B; goto CLEANUP; } }
00318 
00319 #define DGG_WARNING(A, REST...) {\
00320   if(A) {\
00321           fprintf(stdout, ##REST); \
00322                 __DGG_PRINT_LOC__(stdout); \
00323                 }}
00324 
00325 #define DGG_TEST(A,B,REST...) {\
00326  if(A) DGG_THROW(B,##REST) }
00327 
00328 #define DGG_TEST2(A,B,C,REST)   {DGG_TEST(A,B,C,REST) }
00329 #define DGG_TEST3(A,B,C,D,REST) {DGG_TEST(A,B,C,D,REST) }
00330 
00331 #else
00332 
00333 #define DGG_IF_EXIT(A,B,REST) {if(A) {fprintf(stdout, REST);exit(B);}}
00334 
00335 #define DGG_THROW(A,B) return(A)
00336 
00337 #define DGG_CHECKRVAL(A,B) {  if(A) return(B); }
00338 #define DGG_CHECKRVAL1(A,B){ if(A) { rval = B; goto CLEANUP; } }
00339 
00340 #define DGG_TEST(A,B,REST) { if(A) return(B);}
00341 #define DGG_TEST2(A,B,REST,C) { DGG_TEST(A,B,REST) }
00342 #define DGG_TEST3(A,B,REST,C,D) { DGG_TEST(A,B,REST) }
00343 
00344 #endif
00345 
00346 /******************** SIMPLE MACROS AND FUNCTIONS *****************************/
00347 
00348 #define DGG_MIN(a,b) ( (a<b)?a:b )
00349 #define DGG_MAX(a,b) ( (a>b)?a:b )
00350 #define KREM(vht,alpha,tau)  (DGG_MIN( ceil(vht / alpha), tau ) - 1)
00351 #define LMIN(vht, d, bht) (DGG_MIN( floor(d*bht/bht), d))
00352 #define ABOV(v) (v - floor(v))
00353 #define QINT(vht,bht,tau) ( (int)floor( (vht*(tau-1))/bht ) )
00354 #define V2I(bht,tau,i) ( ((i+1)*bht / tau) )
00355 
00356 int DGG_is_even(double vht, double bht, int tau, int q);
00357 double frac_part(double value);
00358 int DGG_is_a_multiple_of_b(double a, double b);
00359 
00360 
00361 /* free function for DGG_data_t. Frees internal arrays and data structure */
00362 int DGG_freeData( DGG_data_t *data );
00363 
00364 /******************** CONSTRAINT ADTs *****************************************/
00365 DGG_constraint_t* DGG_newConstraint(int max_arrays);
00366 void DGG_freeConstraint(DGG_constraint_t *c);
00367 DGG_constraint_t *DGG_copyConstraint(DGG_constraint_t *c);
00368 void DGG_scaleConstraint(DGG_constraint_t *c, int t);
00369 
00370 /******************** CONFIGURATION *******************************************/
00371 void DGG_list_init (DGG_list_t *l);
00372 int DGG_list_addcut (DGG_list_t *l, DGG_constraint_t *cut, int ctype, double alpha);
00373 void DGG_list_delcut (DGG_list_t *l, int i);
00374 void DGG_list_free(DGG_list_t *l);
00375 
00376 /******************* SOLVER SPECIFIC METHODS **********************************/
00377 DGG_data_t *DGG_getData(const void *solver_ptr);
00378 
00379 /******************* CONSTRAINT MANIPULATION **********************************/
00380 
00381 /* DGG_transformConstraint: manipulates a constraint in the following way: 
00382 
00383 packs everything in output
00384 
00385 1 - variables at their upper bounds are substituted for their 
00386 complements. This is done by adjusting the coefficients and 
00387 the right hand side (simple substitution). 
00388 
00389 2 - variables with non-zero lower bounds are shifted.            */
00390 
00391 int DGG_transformConstraint( DGG_data_t *data,
00392                              double **x_out, 
00393                              double **rc_out,
00394                              char **isint_out,
00395                              DGG_constraint_t *constraint );
00396 
00397 /* DGG_unTransformConstraint : 
00398 
00399 1 - Undoes step (1) of DGG_transformConstraint 
00400 2 - Undoes step (2) of DGG_transformConstraint                  */
00401  
00402 int DGG_unTransformConstraint( DGG_data_t *data, 
00403                                DGG_constraint_t *constraint );
00404 
00405 /* substitutes each slack variable by the structural variables which 
00406    define it. This function, hence, changes the constraint 'cut'.    */
00407 
00408 int DGG_substituteSlacks( const void *solver_ptr, 
00409                           DGG_data_t *data, 
00410                           DGG_constraint_t *cut );
00411 
00412 int DGG_nicefyConstraint( const void *solver_ptr, 
00413                           DGG_data_t *data,
00414                           DGG_constraint_t *cut);
00415 
00416 /******************* CUT GENERATION *******************************************/
00417 int DGG_getFormulaConstraint( int row_idx,  
00418                               const void *solver_ptr,   
00419                               DGG_data_t *data, 
00420                               DGG_constraint_t* row );
00421 
00422 int DGG_getTableauConstraint( int index, 
00423                               const void *solver_ptr, 
00424                               DGG_data_t *data, 
00425                               DGG_constraint_t* tabrow,
00426                               const int * colIsBasic,
00427                               const int * rowIsBasic,
00428                               CoinFactorization & factorization,
00429                               int mode );
00430 
00431 DGG_constraint_t* DGG_getSlackExpression(const void *solver_ptr, DGG_data_t* data, int row_index);
00432 
00433   int DGG_generateTabRowCuts( DGG_list_t *list,
00434                               DGG_data_t *data,
00435                               const void *solver_ptr );
00436 
00437   int DGG_generateFormulationCuts( DGG_list_t *list,
00438                                    DGG_data_t *data,
00439                                    const void *solver_ptr,
00440                                    int nrows);
00441 
00442 
00443   int DGG_generateFormulationCutsFromBase( DGG_constraint_t *base,
00444                                            double slack,
00445                                            DGG_list_t *list,
00446                                            DGG_data_t *data,
00447                                            const void *solver_ptr );
00448 
00449   int DGG_generateCutsFromBase( DGG_constraint_t *base,
00450                                 DGG_list_t *list,
00451                                 DGG_data_t *data,
00452                                 const void *solver_ptr );
00453 
00454 int DGG_buildMir( char *isint,
00455                   DGG_constraint_t *base,
00456                   DGG_constraint_t **cut_out );
00457 
00458 int DGG_build2step( double alpha,
00459                     char *isint,
00460                     DGG_constraint_t *base,
00461                     DGG_constraint_t **cut_out );
00462 
00463   int DGG_addMirToList   ( DGG_constraint_t *base,
00464                            char *isint,
00465                            double *x,
00466                            DGG_list_t *list,
00467                            DGG_data_t *data,
00468                            DGG_constraint_t *orig_base );
00469 
00470   int DGG_add2stepToList ( DGG_constraint_t *base,
00471                            char *isint,
00472                            double *x,
00473                            double *rc,
00474                            DGG_list_t *list,
00475                            DGG_data_t *data,
00476                            DGG_constraint_t *orig_base );
00477 
00478 /******************* CUT INFORMATION ******************************************/
00479 
00480 double DGG_cutLHS(DGG_constraint_t *c, double *x);
00481 int DGG_isCutDesirable(DGG_constraint_t *c, DGG_data_t *d);
00482 
00483 /******************* TEST / DEBUGGING ROUTINES ********************************/
00484 
00485 int DGG_isConstraintViolated(DGG_data_t *d, DGG_constraint_t *c);
00486 
00487 int DGG_isBaseTrivial(DGG_data_t *d, DGG_constraint_t* c);
00488 int DGG_is2stepValid(double alpha, double bht);
00489 
00490 int DGG_cutsOffPoint(double *x, DGG_constraint_t *cut);
00491 
00492 #endif
00493 
00494 

Generated on Thu May 15 21:59:05 2008 by  doxygen 1.4.7