coin-Cgl
|
00001 // LAST EDIT: 00002 //----------------------------------------------------------------------------- 00003 // name: Mixed Integer Rounding Cut Generator 00004 // authors: Joao Goncalves (jog7@lehigh.edu) 00005 // Laszlo Ladanyi (ladanyi@us.ibm.com) 00006 // date: August 11, 2004 00007 //----------------------------------------------------------------------------- 00008 // Copyright (C) 2004, International Business Machines Corporation and others. 00009 // All Rights Reserved. 00010 // This code is published under the Common Public License. 00011 00012 #ifndef CglMixedIntegerRounding2_H 00013 #define CglMixedIntegerRounding2_H 00014 00015 #include <iostream> 00016 #include <fstream> 00017 //#include <vector> 00018 00019 #include "CoinError.hpp" 00020 00021 #include "CglCutGenerator.hpp" 00022 #include "CoinIndexedVector.hpp" 00023 00024 //============================================================================= 00025 00026 #ifndef CGL_DEBUG 00027 #define CGL_DEBUG 0 00028 #endif 00029 00030 //============================================================================= 00031 00032 // Class to store variable upper bounds (VUB) 00033 class CglMixIntRoundVUB2 00034 { 00035 // Variable upper bounds have the form x_j <= a y_j, where x_j is 00036 // a continuous variable and y_j is an integer variable 00037 00038 protected: 00039 int var_; // The index of y_j 00040 double val_; // The value of a 00041 00042 public: 00043 // Default constructor 00044 CglMixIntRoundVUB2() : var_(-1), val_(-1) {} 00045 00046 // Copy constructor 00047 CglMixIntRoundVUB2(const CglMixIntRoundVUB2& source) { 00048 var_ = source.var_; 00049 val_ = source.val_; 00050 } 00051 00052 // Assignment operator 00053 CglMixIntRoundVUB2& operator=(const CglMixIntRoundVUB2& rhs) { 00054 if (this != &rhs) { 00055 var_ = rhs.var_; 00056 val_ = rhs.val_; 00057 } 00058 return *this; 00059 } 00060 00061 // Destructor 00062 ~CglMixIntRoundVUB2() {} 00063 00064 // Query and set functions 00065 int getVar() const { return var_; } 00066 double getVal() const { return val_; } 00067 void setVar(const int v) { var_ = v; } 00068 void setVal(const double v) { val_ = v; } 00069 }; 00070 00071 //============================================================================= 00072 00073 // Class to store variable lower bounds (VLB). 00074 // It is the same as the class to store variable upper bounds 00075 typedef CglMixIntRoundVUB2 CglMixIntRoundVLB2; 00076 00077 //============================================================================= 00078 00081 // Reference: 00082 // Hugues Marchand and Laurence A. Wolsey 00083 // Aggregation and Mixed Integer Rounding to Solve MIPs 00084 // Operations Research, 49(3), May-June 2001. 00085 // Also published as CORE Dicusion Paper 9839, June 1998. 00086 00087 class CglMixedIntegerRounding2 : public CglCutGenerator { 00088 00089 friend void CglMixedIntegerRounding2UnitTest(const OsiSolverInterface * siP, 00090 const std::string mpdDir); 00091 00092 00093 private: 00094 //--------------------------------------------------------------------------- 00095 // Enumeration constants that describe the various types of rows 00096 enum RowType { 00097 // The row type of this row is NOT defined yet. 00098 ROW_UNDEFINED, 00102 ROW_VARUB, 00106 ROW_VARLB, 00109 ROW_VAREQ, 00110 // The row contains continuous and integer variables; 00111 // the total number of variables is at least 2 00112 ROW_MIX, 00113 // The row contains only continuous variables 00114 ROW_CONT, 00115 // The row contains only integer variables 00116 ROW_INT, 00117 // The row contains other types of rows 00118 ROW_OTHER 00119 }; 00120 00121 00122 public: 00123 00130 virtual void generateCuts(const OsiSolverInterface & si, OsiCuts & cs, 00131 const CglTreeInfo info = CglTreeInfo()) const; 00133 00134 //--------------------------------------------------------------------------- 00137 00138 CglMixedIntegerRounding2 (); 00139 00141 CglMixedIntegerRounding2 (const int maxaggr, 00142 const bool multiply, 00143 const int criterion, 00144 const int preproc = -1); 00145 00147 CglMixedIntegerRounding2 ( 00148 const CglMixedIntegerRounding2 &); 00149 00151 virtual CglCutGenerator * clone() const; 00152 00154 CglMixedIntegerRounding2 & 00155 operator=( 00156 const CglMixedIntegerRounding2& rhs); 00157 00159 virtual 00160 ~CglMixedIntegerRounding2 (); 00162 virtual void refreshSolver(OsiSolverInterface * solver); 00164 virtual std::string generateCpp( FILE * fp); 00166 00167 //--------------------------------------------------------------------------- 00170 00171 inline void setMAXAGGR_ (int maxaggr) { 00172 if (maxaggr > 0) { 00173 MAXAGGR_ = maxaggr; 00174 } 00175 else { 00176 throw CoinError("Unallowable value. maxaggr must be > 0", 00177 "gutsOfConstruct","CglMixedIntegerRounding2"); 00178 } 00179 } 00180 00182 inline int getMAXAGGR_ () const { return MAXAGGR_; } 00183 00185 inline void setMULTIPLY_ (bool multiply) { MULTIPLY_ = multiply; } 00186 00188 inline bool getMULTIPLY_ () const { return MULTIPLY_; } 00189 00191 inline void setCRITERION_ (int criterion) { 00192 if ((criterion >= 1) && (criterion <= 3)) { 00193 CRITERION_ = criterion; 00194 } 00195 else { 00196 throw CoinError("Unallowable value. criterion must be 1, 2 or 3", 00197 "gutsOfConstruct","CglMixedIntegerRounding2"); 00198 } 00199 } 00200 00202 inline int getCRITERION_ () const { return CRITERION_; } 00203 00205 void setDoPreproc(int value); 00207 bool getDoPreproc() const; 00209 00210 private: 00211 //-------------------------------------------------------------------------- 00212 // Private member methods 00213 00214 // Construct 00215 void gutsOfConstruct ( const int maxaggr, 00216 const bool multiply, 00217 const int criterion, 00218 const int preproc); 00219 00220 // Delete 00221 void gutsOfDelete(); 00222 00223 // Copy 00224 void gutsOfCopy (const CglMixedIntegerRounding2& rhs); 00225 00226 // Do preprocessing. 00227 // It determines the type of each row. It also identifies the variable 00228 // upper bounds and variable lower bounds. 00229 // It may change sense and RHS for ranged rows 00230 void mixIntRoundPreprocess(const OsiSolverInterface& si) const; 00231 00232 // Determine the type of a given row. 00233 RowType determineRowType(//const OsiSolverInterface& si, 00234 const int rowLen, const int* ind, 00235 const double* coef, const char sense, 00236 const double rhs) const; 00237 00238 // Generate MIR cuts 00239 void generateMirCuts( const OsiSolverInterface& si, 00240 const double* xlp, 00241 const double* colUpperBound, 00242 const double* colLowerBound, 00243 const CoinPackedMatrix& matrixByRow, 00244 const double* LHS, 00245 //const double* coefByRow, 00246 //const int* colInds, 00247 //const int* rowStarts, 00248 //const CoinPackedMatrix& matrixByCol, 00249 const double* coefByCol, 00250 const int* rowInds, 00251 const int* colStarts, 00252 OsiCuts& cs ) const; 00253 00254 // Copy row selected to CoinIndexedVector 00255 void copyRowSelected( const int iAggregate, 00256 const int rowSelected, 00257 CoinIndexedVector& setRowsAggregated, 00258 int* listRowsAggregated, 00259 double* xlpExtra, 00260 const char sen, 00261 const double rhs, 00262 const double lhs, 00263 const CoinPackedMatrix& matrixByRow, 00264 CoinIndexedVector& rowToAggregate, 00265 double& rhsToAggregate) const; 00266 00267 // Select a row to aggregate 00268 bool selectRowToAggregate( //const OsiSolverInterface& si, 00269 const CoinIndexedVector& rowAggregated, 00270 const double* colUpperBound, 00271 const double* colLowerBound, 00272 const CoinIndexedVector& setRowsAggregated, 00273 const double* xlp, const double* coefByCol, 00274 const int* rowInds, const int* colStarts, 00275 int& rowSelected, 00276 int& colSelected ) const; 00277 00278 // Aggregation heuristic. 00279 // Combines one or more rows of the original matrix 00280 void aggregateRow( const int colSelected, 00281 CoinIndexedVector& rowToAggregate, double rhs, 00282 CoinIndexedVector& rowAggregated, 00283 double& rhsAggregated ) const; 00284 00285 // Choose the bound substitution based on the criteria defined by the user 00286 inline bool isLowerSubst(const double inf, 00287 const double aj, 00288 const double xlp, 00289 const double LB, 00290 const double UB) const; 00291 00292 // Bound substitution heuristic 00293 bool boundSubstitution( const OsiSolverInterface& si, 00294 const CoinIndexedVector& rowAggregated, 00295 const double* xlp, 00296 const double* xlpExtra, 00297 const double* colUpperBound, 00298 const double* colLowerBound, 00299 CoinIndexedVector& mixedKnapsack, 00300 double& rhsMixedKnapsack, double& sStar, 00301 CoinIndexedVector& contVariablesInS ) const; 00302 00303 // c-MIR separation heuristic 00304 bool cMirSeparation ( const OsiSolverInterface& si, 00305 const CoinPackedMatrix& matrixByRow, 00306 const CoinIndexedVector& rowAggregated, 00307 const int* listRowsAggregated, 00308 const char* sense, const double* RHS, 00309 //const double* coefByRow, 00310 //const int* colInds, const int* rowStarts, 00311 const double* xlp, const double sStar, 00312 const double* colUpperBound, 00313 const double* colLowerBound, 00314 const CoinIndexedVector& mixedKnapsack, 00315 const double& rhsMixedKnapsack, 00316 const CoinIndexedVector& contVariablesInS, 00317 CoinIndexedVector * workVector, 00318 OsiRowCut& flowCut ) const; 00319 00320 // function to create one c-MIR inequality 00321 void cMirInequality( const int numInt, 00322 const double delta, 00323 const double numeratorBeta, 00324 const int *knapsackIndices, 00325 const double* knapsackElements, 00326 const double* xlp, 00327 const double sStar, 00328 const double* colUpperBound, 00329 const CoinIndexedVector& setC, 00330 CoinIndexedVector& cMIR, 00331 double& rhscMIR, 00332 double& sCoef, 00333 double& violation) const; 00334 00335 // function to compute G 00336 inline double functionG( const double d, const double f ) const; 00337 00338 // function to print statistics (used only in debug mode) 00339 void printStats( 00340 std::ofstream & fout, 00341 const bool hasCut, 00342 const OsiSolverInterface& si, 00343 const CoinIndexedVector& rowAggregated, 00344 const double& rhsAggregated, const double* xlp, 00345 const double* xlpExtra, 00346 const int* listRowsAggregated, 00347 const int* listColsSelected, 00348 const int level, 00349 const double* colUpperBound, 00350 const double* colLowerBound ) const; 00351 00352 00353 private: 00354 //--------------------------------------------------------------------------- 00355 // Private member data 00356 00357 // Maximum number of rows to aggregate 00358 int MAXAGGR_; 00359 // Flag that indicates if an aggregated row is also multiplied by -1 00360 bool MULTIPLY_; 00361 // The criterion to use in the bound substitution 00362 int CRITERION_; 00363 // Tolerance used for numerical purposes 00364 double EPSILON_; 00366 int UNDEFINED_; 00367 // If violation of a cut is greater that this number, the cut is accepted 00368 double TOLERANCE_; 00376 int doPreproc_; 00377 // The number of rows of the problem. 00378 mutable int numRows_; 00379 // The number columns of the problem. 00380 mutable int numCols_; 00381 // Indicates whether preprocessing has been done. 00382 mutable bool doneInitPre_; 00383 // The array of CglMixIntRoundVUB2s. 00384 mutable CglMixIntRoundVUB2* vubs_; 00385 // The array of CglMixIntRoundVLB2s. 00386 mutable CglMixIntRoundVLB2* vlbs_; 00387 // Array with the row types of the rows in the model. 00388 mutable RowType* rowTypes_; 00389 // The indices of the rows of the initial matrix 00390 mutable int* indRows_; 00391 // The number of rows of type ROW_MIX 00392 mutable int numRowMix_; 00393 // The indices of the rows of type ROW_MIX 00394 mutable int* indRowMix_; 00395 // The number of rows of type ROW_CONT 00396 mutable int numRowCont_; 00397 // The indices of the rows of type ROW_CONT 00398 mutable int* indRowCont_; 00399 // The number of rows of type ROW_INT 00400 mutable int numRowInt_; 00401 // The indices of the rows of type ROW_INT 00402 mutable int* indRowInt_; 00403 // The number of rows of type ROW_CONT that have at least one variable 00404 // with variable upper or lower bound 00405 mutable int numRowContVB_; 00406 // The indices of the rows of type ROW_CONT that have at least one variable 00407 // with variable upper or lower bound 00408 mutable int* indRowContVB_; 00409 // If integer - for speed 00410 mutable char * integerType_; 00411 // Sense of rows (modified if ranges) 00412 mutable char * sense_; 00413 // RHS of rows (modified if ranges) 00414 mutable double * RHS_; 00415 00416 }; 00417 00418 //############################################################################# 00419 // A function that tests the methods in the CglMixedIntegerRounding2 class. The 00420 // only reason for it not to be a member method is that this way it doesn't 00421 // have to be compiled into the library. And that's a gain, because the 00422 // library should be compiled with optimization on, but this method should be 00423 // compiled with debugging. 00424 void CglMixedIntegerRounding2UnitTest(const OsiSolverInterface * siP, 00425 const std::string mpdDir); 00426 00427 #endif