1 // LAST EDIT: 2 //----------------------------------------------------------------------------- 3 // name: Mixed Integer Rounding Cut Generator 4 // authors: Joao Goncalves (jog7@lehigh.edu) 5 // Laszlo Ladanyi (ladanyi@us.ibm.com) 6 // date: August 11, 2004 7 //----------------------------------------------------------------------------- 8 // Copyright (C) 2004, International Business Machines Corporation and others. 9 // All Rights Reserved. 10 // This code is published under the Eclipse Public License. 11 12 #ifndef CglMixedIntegerRounding2_H 13 #define CglMixedIntegerRounding2_H 14 15 #include <iostream> 16 #include <fstream> 17 //#include <vector> 18 19 #include "CoinError.hpp" 20 21 #include "CglCutGenerator.hpp" 22 #include "CoinIndexedVector.hpp" 23 24 //============================================================================= 25 26 #ifndef CGL_DEBUG 27 #define CGL_DEBUG 0 28 #endif 29 30 //============================================================================= 31 32 // Class to store variable upper bounds (VUB) 33 class CglMixIntRoundVUB2 34 { 35 // Variable upper bounds have the form x_j <= a y_j, where x_j is 36 // a continuous variable and y_j is an integer variable 37 38 protected: 39 int var_; // The index of y_j 40 double val_; // The value of a 41 42 public: 43 // Default constructor CglMixIntRoundVUB2()44 CglMixIntRoundVUB2() : var_(-1), val_(-1) {} 45 46 // Copy constructor CglMixIntRoundVUB2(const CglMixIntRoundVUB2 & source)47 CglMixIntRoundVUB2(const CglMixIntRoundVUB2& source) { 48 var_ = source.var_; 49 val_ = source.val_; 50 } 51 52 // Assignment operator operator =(const CglMixIntRoundVUB2 & rhs)53 CglMixIntRoundVUB2& operator=(const CglMixIntRoundVUB2& rhs) { 54 if (this != &rhs) { 55 var_ = rhs.var_; 56 val_ = rhs.val_; 57 } 58 return *this; 59 } 60 61 // Destructor ~CglMixIntRoundVUB2()62 ~CglMixIntRoundVUB2() {} 63 64 // Query and set functions getVar() const65 int getVar() const { return var_; } getVal() const66 double getVal() const { return val_; } setVar(const int v)67 void setVar(const int v) { var_ = v; } setVal(const double v)68 void setVal(const double v) { val_ = v; } 69 }; 70 71 //============================================================================= 72 73 // Class to store variable lower bounds (VLB). 74 // It is the same as the class to store variable upper bounds 75 typedef CglMixIntRoundVUB2 CglMixIntRoundVLB2; 76 77 //============================================================================= 78 79 /** Mixed Integer Rounding Cut Generator Class */ 80 81 // Reference: 82 // Hugues Marchand and Laurence A. Wolsey 83 // Aggregation and Mixed Integer Rounding to Solve MIPs 84 // Operations Research, 49(3), May-June 2001. 85 // Also published as CORE Dicusion Paper 9839, June 1998. 86 87 class CglMixedIntegerRounding2 : public CglCutGenerator { 88 89 friend void CglMixedIntegerRounding2UnitTest(const OsiSolverInterface * siP, 90 const std::string mpdDir); 91 92 93 private: 94 //--------------------------------------------------------------------------- 95 // Enumeration constants that describe the various types of rows 96 enum RowType { 97 // The row type of this row is NOT defined yet. 98 ROW_UNDEFINED, 99 /** After the row is flipped to 'L', the row has exactly two variables: 100 one is negative binary and the other is a continous, 101 and the RHS is zero.*/ 102 ROW_VARUB, 103 /** After the row is flipped to 'L', the row has exactly two variables: 104 one is positive binary and the other is a continous, 105 and the RHS is zero.*/ 106 ROW_VARLB, 107 /** The row sense is 'E', the row has exactly two variables: 108 one is binary and the other is a continous, and the RHS is zero.*/ 109 ROW_VAREQ, 110 // The row contains continuous and integer variables; 111 // the total number of variables is at least 2 112 ROW_MIX, 113 // The row contains only continuous variables 114 ROW_CONT, 115 // The row contains only integer variables 116 ROW_INT, 117 // The row contains other types of rows 118 ROW_OTHER 119 }; 120 121 122 public: 123 124 /**@name Generate Cuts */ 125 //@{ 126 /** Generate Mixed Integer Rounding cuts for the model data 127 contained in si. The generated cuts are inserted 128 in the collection of cuts cs. 129 */ 130 virtual void generateCuts(const OsiSolverInterface & si, OsiCuts & cs, 131 const CglTreeInfo info = CglTreeInfo()); 132 //@} 133 134 //--------------------------------------------------------------------------- 135 /**@name Constructors and destructors */ 136 //@{ 137 /// Default constructor 138 CglMixedIntegerRounding2 (); 139 140 /// Alternate Constructor 141 CglMixedIntegerRounding2 (const int maxaggr, 142 const bool multiply, 143 const int criterion, 144 const int preproc = -1); 145 146 /// Copy constructor 147 CglMixedIntegerRounding2 ( 148 const CglMixedIntegerRounding2 &); 149 150 /// Clone 151 virtual CglCutGenerator * clone() const; 152 153 /// Assignment operator 154 CglMixedIntegerRounding2 & 155 operator=( 156 const CglMixedIntegerRounding2& rhs); 157 158 /// Destructor 159 virtual 160 ~CglMixedIntegerRounding2 (); 161 /// This can be used to refresh any inforamtion 162 virtual void refreshSolver(OsiSolverInterface * solver); 163 /// Create C++ lines to get to current state 164 virtual std::string generateCpp( FILE * fp); 165 //@} 166 167 //--------------------------------------------------------------------------- 168 /**@name Set and get methods */ 169 //@{ 170 /// Set MAXAGGR_ setMAXAGGR_(int maxaggr)171 inline void setMAXAGGR_ (int maxaggr) { 172 if (maxaggr > 0) { 173 MAXAGGR_ = maxaggr; 174 } 175 else { 176 throw CoinError("Unallowable value. maxaggr must be > 0", 177 "gutsOfConstruct","CglMixedIntegerRounding2"); 178 } 179 } 180 181 /// Get MAXAGGR_ getMAXAGGR_() const182 inline int getMAXAGGR_ () const { return MAXAGGR_; } 183 184 /// Set MULTIPLY_ setMULTIPLY_(bool multiply)185 inline void setMULTIPLY_ (bool multiply) { MULTIPLY_ = multiply; } 186 187 /// Get MULTIPLY_ getMULTIPLY_() const188 inline bool getMULTIPLY_ () const { return MULTIPLY_; } 189 190 /// Set CRITERION_ setCRITERION_(int criterion)191 inline void setCRITERION_ (int criterion) { 192 if ((criterion >= 1) && (criterion <= 3)) { 193 CRITERION_ = criterion; 194 } 195 else { 196 throw CoinError("Unallowable value. criterion must be 1, 2 or 3", 197 "gutsOfConstruct","CglMixedIntegerRounding2"); 198 } 199 } 200 201 /// Get CRITERION_ getCRITERION_() const202 inline int getCRITERION_ () const { return CRITERION_; } 203 204 /// Set doPreproc 205 void setDoPreproc(int value); 206 /// Get doPreproc 207 bool getDoPreproc() const; 208 //@} 209 210 private: 211 //-------------------------------------------------------------------------- 212 // Private member methods 213 214 // Construct 215 void gutsOfConstruct ( const int maxaggr, 216 const bool multiply, 217 const int criterion, 218 const int preproc); 219 220 // Delete 221 void gutsOfDelete(); 222 223 // Copy 224 void gutsOfCopy (const CglMixedIntegerRounding2& rhs); 225 226 // Do preprocessing. 227 // It determines the type of each row. It also identifies the variable 228 // upper bounds and variable lower bounds. 229 // It may change sense and RHS for ranged rows 230 void mixIntRoundPreprocess(const OsiSolverInterface& si); 231 232 // Determine the type of a given row. 233 RowType determineRowType(//const OsiSolverInterface& si, 234 const int rowLen, const int* ind, 235 const double* coef, const char sense, 236 const double rhs) const; 237 238 // Generate MIR cuts 239 void generateMirCuts( const OsiSolverInterface& si, 240 const double* xlp, 241 const double* colUpperBound, 242 const double* colLowerBound, 243 const CoinPackedMatrix& matrixByRow, 244 const double* LHS, 245 //const double* coefByRow, 246 //const int* colInds, 247 //const int* rowStarts, 248 //const CoinPackedMatrix& matrixByCol, 249 const double* coefByCol, 250 const int* rowInds, 251 const CoinBigIndex* colStarts, 252 OsiCuts& cs ) const; 253 254 // Copy row selected to CoinIndexedVector 255 void copyRowSelected( const int iAggregate, 256 const int rowSelected, 257 CoinIndexedVector& setRowsAggregated, 258 int* listRowsAggregated, 259 double* xlpExtra, 260 const char sen, 261 const double rhs, 262 const double lhs, 263 const CoinPackedMatrix& matrixByRow, 264 CoinIndexedVector& rowToAggregate, 265 double& rhsToAggregate) const; 266 267 // Select a row to aggregate 268 bool selectRowToAggregate( //const OsiSolverInterface& si, 269 const CoinIndexedVector& rowAggregated, 270 const double* colUpperBound, 271 const double* colLowerBound, 272 const CoinIndexedVector& setRowsAggregated, 273 const double* xlp, const double* coefByCol, 274 const int* rowInds, const CoinBigIndex* colStarts, 275 int& rowSelected, 276 int& colSelected ) const; 277 278 // Aggregation heuristic. 279 // Combines one or more rows of the original matrix 280 void aggregateRow( const int colSelected, 281 CoinIndexedVector& rowToAggregate, double rhs, 282 CoinIndexedVector& rowAggregated, 283 double& rhsAggregated ) const; 284 285 // Choose the bound substitution based on the criteria defined by the user 286 inline bool isLowerSubst(const double inf, 287 const double aj, 288 const double xlp, 289 const double LB, 290 const double UB) const; 291 292 // Bound substitution heuristic 293 bool boundSubstitution( const OsiSolverInterface& si, 294 const CoinIndexedVector& rowAggregated, 295 const double* xlp, 296 const double* xlpExtra, 297 const double* colUpperBound, 298 const double* colLowerBound, 299 CoinIndexedVector& mixedKnapsack, 300 double& rhsMixedKnapsack, double& sStar, 301 CoinIndexedVector& contVariablesInS ) const; 302 303 // c-MIR separation heuristic 304 bool cMirSeparation ( const OsiSolverInterface& si, 305 const CoinPackedMatrix& matrixByRow, 306 const CoinIndexedVector& rowAggregated, 307 const int* listRowsAggregated, 308 const char* sense, const double* RHS, 309 //const double* coefByRow, 310 //const int* colInds, const int* rowStarts, 311 const double* xlp, const double sStar, 312 const double* colUpperBound, 313 const double* colLowerBound, 314 const CoinIndexedVector& mixedKnapsack, 315 const double& rhsMixedKnapsack, 316 const CoinIndexedVector& contVariablesInS, 317 CoinIndexedVector * workVector, 318 OsiRowCut& flowCut ) const; 319 320 // function to create one c-MIR inequality 321 void cMirInequality( const int numInt, 322 const double delta, 323 const double numeratorBeta, 324 const int *knapsackIndices, 325 const double* knapsackElements, 326 const double* xlp, 327 const double sStar, 328 const double* colUpperBound, 329 const CoinIndexedVector& setC, 330 CoinIndexedVector& cMIR, 331 double& rhscMIR, 332 double& sCoef, 333 double& violation) const; 334 335 // function to compute G 336 inline double functionG( const double d, const double f ) const; 337 338 // function to print statistics (used only in debug mode) 339 void printStats( 340 std::ofstream & fout, 341 const bool hasCut, 342 const OsiSolverInterface& si, 343 const CoinIndexedVector& rowAggregated, 344 const double& rhsAggregated, const double* xlp, 345 const double* xlpExtra, 346 const int* listRowsAggregated, 347 const int* listColsSelected, 348 const int level, 349 const double* colUpperBound, 350 const double* colLowerBound ) const; 351 352 353 private: 354 //--------------------------------------------------------------------------- 355 // Private member data 356 357 // Maximum number of rows to aggregate 358 int MAXAGGR_; 359 // Flag that indicates if an aggregated row is also multiplied by -1 360 bool MULTIPLY_; 361 // The criterion to use in the bound substitution 362 int CRITERION_; 363 // Tolerance used for numerical purposes 364 double EPSILON_; 365 /// There is no variable upper bound or variable lower bound defined 366 int UNDEFINED_; 367 // If violation of a cut is greater that this number, the cut is accepted 368 double TOLERANCE_; 369 /** Controls the preprocessing of the matrix to identify rows suitable for 370 cut generation.<UL> 371 <LI> -1: preprocess according to solver settings; 372 <LI> 0: Do preprocessing only if it has not yet been done; 373 <LI> 1: Do preprocessing. 374 </UL> 375 Default value: -1 **/ 376 int doPreproc_; 377 // The number of rows of the problem. 378 int numRows_; 379 // The number columns of the problem. 380 int numCols_; 381 // Indicates whether preprocessing has been done. 382 bool doneInitPre_; 383 // The array of CglMixIntRoundVUB2s. 384 CglMixIntRoundVUB2* vubs_; 385 // The array of CglMixIntRoundVLB2s. 386 CglMixIntRoundVLB2* vlbs_; 387 // Array with the row types of the rows in the model. 388 RowType* rowTypes_; 389 // The indices of the rows of the initial matrix 390 int* indRows_; 391 // The number of rows of type ROW_MIX 392 int numRowMix_; 393 // The indices of the rows of type ROW_MIX 394 int* indRowMix_; 395 // The number of rows of type ROW_CONT 396 int numRowCont_; 397 // The indices of the rows of type ROW_CONT 398 int* indRowCont_; 399 // The number of rows of type ROW_INT 400 int numRowInt_; 401 // The indices of the rows of type ROW_INT 402 int* indRowInt_; 403 // The number of rows of type ROW_CONT that have at least one variable 404 // with variable upper or lower bound 405 int numRowContVB_; 406 // The indices of the rows of type ROW_CONT that have at least one variable 407 // with variable upper or lower bound 408 int* indRowContVB_; 409 // If integer - for speed 410 char * integerType_; 411 // Sense of rows (modified if ranges) 412 char * sense_; 413 // RHS of rows (modified if ranges) 414 double * RHS_; 415 416 }; 417 418 //############################################################################# 419 // A function that tests the methods in the CglMixedIntegerRounding2 class. The 420 // only reason for it not to be a member method is that this way it doesn't 421 // have to be compiled into the library. And that's a gain, because the 422 // library should be compiled with optimization on, but this method should be 423 // compiled with debugging. 424 void CglMixedIntegerRounding2UnitTest(const OsiSolverInterface * siP, 425 const std::string mpdDir); 426 427 #endif 428