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