1 // $Id$ 2 //----------------------------------------------------------------------------- 3 // name: Cgl Lifted Simple Generalized Flow Cover Cut Generator 4 // author: Yan Xu email: yan.xu@sas.com 5 // Jeff Linderoth email: jtl3@lehigh.edu 6 // Martin Savelsberg email: martin.savelsbergh@isye.gatech.edu 7 // date: 05/01/2003 8 // comments: please scan this file for '???' and read the comments 9 //----------------------------------------------------------------------------- 10 // Copyright (C) 2003, Yan Xu, Jeff Linderoth, Martin Savelsberg and others. 11 // All Rights Reserved. 12 // This code is published under the Eclipse Public License. 13 14 #ifndef CglFlowCover_H 15 #define CglFlowCover_H 16 17 #include <iostream> 18 19 #include "CoinError.hpp" 20 21 #include "CglCutGenerator.hpp" 22 23 //============================================================================= 24 25 //============================================================================= 26 27 /** This enumerative constant describes the various col types.*/ 28 enum CglFlowColType { 29 /** The column(variable) is a negative binary variable.*/ 30 CGLFLOW_COL_BINNEG = -2, 31 /** The column is a negative continous variable.*/ 32 CGLFLOW_COL_CONTNEG, 33 /** The column is a positive continous variable.*/ 34 CGLFLOW_COL_CONTPOS = 1, 35 /** The column is a positive binary variable.*/ 36 CGLFLOW_COL_BINPOS 37 }; 38 39 enum CglFlowColStatus{ 40 }; 41 42 /** This enumerative constant describes the various stati of vars in 43 a cut or not.*/ 44 enum CglFlowColCut{ 45 /** The column is NOT in cover.*/ 46 CGLFLOW_COL_OUTCUT = 0, 47 /** The column is in cover now. */ 48 CGLFLOW_COL_INCUT, 49 /** The column is decided to be in cover. */ 50 CGLFLOW_COL_INCUTDONE, 51 /** The column is in L-. */ 52 CGLFLOW_COL_INLMIN, 53 /** The column is decided to be in L-. */ 54 CGLFLOW_COL_INLMINDONE, 55 /** The column is in L--.*/ 56 CGLFLOW_COL_INLMINMIN, 57 /** This enumerative constant describes the various stati of vars in 58 determining the cover.*/ 59 /** The column is a prime candidate. */ 60 CGLFLOW_COL_PRIME, 61 /** The column is a secondary candidate. */ 62 CGLFLOW_COL_SECONDARY 63 }; 64 65 /** This enumerative constant describes the various row types.*/ 66 enum CglFlowRowType { 67 /** The row type of this row is NOT defined yet.*/ 68 CGLFLOW_ROW_UNDEFINED, 69 /** After the row is flipped to 'L', the row has exactly two variables: 70 one is negative binary and the other is continous, and the RHS 71 is zero.*/ 72 CGLFLOW_ROW_VARUB, 73 /** After the row is flipped to 'L', the row has exactlytwo variables: 74 one is positive binary and the other is continous, and the RHS 75 is zero.*/ 76 CGLFLOW_ROW_VARLB, 77 /** The row sense is 'E', the row has exactly two variables: 78 one is binary and the other is a continous, and the RHS is zero.*/ 79 CGLFLOW_ROW_VAREQ, 80 /** Rows can not be classfied into other types and the row sense 81 is NOT 'E'.*/ 82 CGLFLOW_ROW_MIXUB, 83 /** Rows can not be classfied into other types and the row sense is 'E'.*/ 84 CGLFLOW_ROW_MIXEQ, 85 /** All variables are NOT binary and the row sense is NOT 'E'. */ 86 CGLFLOW_ROW_NOBINUB, 87 /** All variables are NOT binary and the row sense is 'E'. */ 88 CGLFLOW_ROW_NOBINEQ, 89 /** The row has one binary and 2 or more other types of variables and 90 the row sense is NOT 'E'. */ 91 CGLFLOW_ROW_SUMVARUB, 92 /** The row has one binary and 2 or more other types of variables and 93 the row sense is 'E'. */ 94 CGLFLOW_ROW_SUMVAREQ, 95 /** All variables are binary. */ 96 CGLFLOW_ROW_UNINTERSTED 97 }; 98 99 //============================================================================= 100 101 /** Variable upper bound class. */ 102 class CglFlowVUB 103 { 104 protected: 105 int varInd_; /** The index of the associated 0-1 variable.*/ 106 double upper_; /** The Value of the associated upper bound.*/ 107 108 public: CglFlowVUB()109 CglFlowVUB() : varInd_(-1), upper_(-1) {} 110 CglFlowVUB(const CglFlowVUB & source)111 CglFlowVUB(const CglFlowVUB& source) { 112 varInd_= source.varInd_; 113 upper_ = source.upper_; 114 } 115 operator =(const CglFlowVUB & rhs)116 CglFlowVUB& operator=(const CglFlowVUB& rhs) { 117 if (this == &rhs) 118 return *this; 119 varInd_= rhs.varInd_; 120 upper_ = rhs.upper_; 121 return *this; 122 } 123 124 /**@name Query and set functions for associated 0-1 variable index 125 and value. 126 */ 127 //@{ getVar() const128 inline int getVar() const { return varInd_; } getVal() const129 inline double getVal() const { return upper_; } setVar(const int v)130 inline void setVar(const int v) { varInd_ = v; } setVal(const double v)131 inline void setVal(const double v) { upper_ = v; } 132 //@} 133 }; 134 135 //============================================================================= 136 137 /** Variable lower bound class, which is the same as vub. */ 138 typedef CglFlowVUB CglFlowVLB; 139 140 /** Overloaded operator<< for printing VUB and VLB.*/ 141 std::ostream& operator<<( std::ostream& os, const CglFlowVUB &v ); 142 143 //============================================================================= 144 145 /** 146 * Lifed Simple Generalized Flow Cover Cut Generator Class. 147 */ 148 class CglFlowCover : public CglCutGenerator { 149 friend void CglFlowCoverUnitTest(const OsiSolverInterface * siP, 150 const std::string mpdDir ); 151 152 public: 153 154 /** 155 * Do the following tasks: 156 * <ul> 157 * <li> classify row types 158 * <li> indentify vubs and vlbs 159 * </ul> 160 * This function is called by 161 * <CODE>generateCuts(const OsiSolverInterface & si, OsiCuts & cs)</CODE>. 162 */ 163 void flowPreprocess(const OsiSolverInterface& si); 164 165 /**@name Generate Cuts */ 166 //@{ 167 /** Generate Lifed Simple Generalized flow cover cuts for the model data 168 contained in si. The generated cuts are inserted into and returned 169 in the collection of cuts cs. 170 */ 171 virtual void generateCuts(const OsiSolverInterface & si, OsiCuts & cs, 172 const CglTreeInfo info = CglTreeInfo()); 173 //@} 174 175 /**@name Functions to query and set maximum number of cuts can be 176 generated. */ 177 //@{ getMaxNumCuts() const178 inline int getMaxNumCuts() const { return maxNumCuts_; } setMaxNumCuts(int mc)179 inline void setMaxNumCuts(int mc) { maxNumCuts_ = mc; } 180 //@} 181 182 /**@name Functions to query and set the number of cuts have been 183 generated. */ 184 //@{ getNumFlowCuts()185 inline int getNumFlowCuts() { return numFlowCuts_; } setNumFlowCuts(int fc)186 inline void setNumFlowCuts(int fc) { numFlowCuts_ = fc; } incNumFlowCuts(int fc=1)187 inline void incNumFlowCuts(int fc = 1) { numFlowCuts_ += fc; } 188 //@} 189 190 //------------------------------------------------------------------------- 191 /**@name Constructors and destructors */ 192 //@{ 193 /// Default constructor 194 CglFlowCover (); 195 196 /// Copy constructor 197 CglFlowCover ( 198 const CglFlowCover &); 199 200 /// Clone 201 virtual CglCutGenerator * clone() const; 202 203 /// Assignment operator 204 CglFlowCover & 205 operator=( 206 const CglFlowCover& rhs); 207 208 /// Destructor 209 virtual 210 ~CglFlowCover (); 211 /// Create C++ lines to get to current state 212 virtual std::string generateCpp( FILE * fp); 213 //@} 214 215 private: 216 //------------------------------------------------------------------------- 217 // Private member functions 218 219 /** Based a given row, a LP solution and other model data, this function 220 tries to generate a violated lifted simple generalized flow cover. 221 */ 222 bool generateOneFlowCut( const OsiSolverInterface & si, 223 const int rowLen, 224 int* ind, 225 double* coef, 226 char sense, 227 double rhs, 228 OsiRowCut& flowCut, 229 double& violation ); 230 231 232 /** Transform a row from ">=" to "<=", and vice versa. */ 233 void flipRow(int rowLen, double* coef, double& rhs) const; 234 235 /** Transform a row from ">=" to "<=", and vice versa. Have 'sense'. */ 236 void flipRow(int rowLen, double* coef, char& sen, double& rhs) const; 237 238 /** Determine the type of a given row. */ 239 CglFlowRowType determineOneRowType(const OsiSolverInterface& si, 240 int rowLen, int* ind, 241 double* coef, char sen, 242 double rhs) const; 243 /** Lift functions */ 244 void liftMinus(double &movement, /* Output */ 245 int t, 246 int r, 247 double z, 248 double dPrimePrime, 249 double lambda, 250 double ml, 251 double *M, 252 double *rho) const; 253 254 bool liftPlus(double &alpha, 255 double &beta, 256 int r, 257 double m_j, 258 double lambda, 259 double y_j, 260 double x_j, 261 double dPrimePrime, 262 double *M) const; 263 264 265 //------------------------------------------------------------------------- 266 //**@name Query and set the row type of a givne row. */ 267 //@{ getRowTypes() const268 inline const CglFlowRowType* getRowTypes() const 269 { return rowTypes_; } getRowType(const int i) const270 inline CglFlowRowType getRowType(const int i) const 271 { return rowTypes_[i]; } 272 /** Set rowtypes, take over the ownership. */ setRowTypes(CglFlowRowType * rt)273 inline void setRowTypes(CglFlowRowType* rt) 274 { rowTypes_ = rt; rt = 0; } setRowTypes(const CglFlowRowType rt,const int i)275 inline void setRowTypes(const CglFlowRowType rt, const int i) { 276 if (rowTypes_ != 0) 277 rowTypes_[i] = rt; 278 else { 279 std::cout << "ERROR: Should allocate memory for rowType_ before " 280 << "using it " << std::endl; 281 throw CoinError("Forgot to allocate memory for rowType_", 282 "setRowType", "CglFlowCover"); 283 } 284 } 285 //@} 286 287 //------------------------------------------------------------------------- 288 //**@name Query and set vubs. */ 289 //@{ getVubs() const290 inline const CglFlowVUB* getVubs() const { return vubs_; } getVubs(int i) const291 inline const CglFlowVUB& getVubs(int i) const { return vubs_[i]; } 292 /** Set CglFlowVUBs,take over the ownership. */ setVubs(CglFlowVUB * vubs)293 inline void setVubs(CglFlowVUB* vubs) { vubs_ = vubs; vubs = 0; } setVubs(const CglFlowVUB & vub,int i)294 inline void setVubs(const CglFlowVUB& vub, int i) { 295 if (vubs_ != 0) 296 vubs_[i] = vub; 297 else { 298 std::cout << "ERROR: Should allocate memory for vubs_ before " 299 << "using it " << std::endl; 300 throw CoinError("Forgot to allocate memory for vubs_", "setVubs", 301 "CglFlowCover"); 302 } 303 } printVubs(std::ostream & os) const304 inline void printVubs(std::ostream& os) const { 305 for (int i = 0; i < numCols_; ++i) { 306 os << "ix: " << i << ", " << vubs_[i]; 307 } 308 } 309 //@} 310 311 //------------------------------------------------------------------------- 312 //**@name Query and set vlbs. */ 313 //@{ getVlbs() const314 inline const CglFlowVLB* getVlbs() const { return vlbs_; } getVlbs(int i) const315 inline const CglFlowVLB& getVlbs(int i) const { return vlbs_[i]; } 316 /** Set CglFlowVLBs,take over the ownership. */ setVlbs(CglFlowVLB * vlbs)317 inline void setVlbs(CglFlowVLB* vlbs) { vlbs_ = vlbs; vlbs = 0; } setVlbs(const CglFlowVLB & vlb,int i)318 inline void setVlbs(const CglFlowVLB& vlb, int i) { 319 if (vlbs_ != 0) 320 vlbs_[i] = vlb; 321 else { 322 std::cout << "ERROR: Should allocate memory for vlbs_ before " 323 << "using it " << std::endl; 324 throw CoinError("Forgot to allocate memory for vlbs_", "setVlbs", 325 "CglFlowCover"); 326 } 327 } 328 //@} 329 330 private: 331 //------------------------------------------------------------------------ 332 // Private member data 333 334 /** The maximum number of flow cuts to be generated. Default is 1000. */ 335 int maxNumCuts_; 336 /** Tolerance used for numerical purpose. */ 337 double EPSILON_; 338 /** The variable upper bound of a flow is not indentified yet.*/ 339 int UNDEFINED_; 340 /** Very large number. */ 341 double INFTY_; 342 /** If violation of a cut is greater that this number, the cut is useful.*/ 343 double TOLERANCE_; 344 /** First time preprocessing */ 345 bool firstProcess_; 346 /** The number rows of the problem.*/ 347 int numRows_; 348 /** The number columns of the problem.*/ 349 int numCols_; 350 /** The number flow cuts found.*/ 351 int numFlowCuts_; 352 /** Indicate whether initial flow preprecessing has been done. */ 353 bool doneInitPre_; 354 /** The array of CglFlowVUBs. */ 355 CglFlowVUB* vubs_; 356 /** The array of CglFlowVLBs. */ 357 CglFlowVLB* vlbs_; 358 /** CglFlowRowType of the rows in model. */ 359 CglFlowRowType* rowTypes_; 360 }; 361 362 //############################################################################# 363 /** A function that tests the methods in the CglFlowCover class. The 364 only reason for it not to be a member method is that this way it doesn't 365 have to be compiled into the library. And that's a gain, because the 366 library should be compiled with optimization on, but this method should be 367 compiled with debugging. */ 368 void CglFlowCoverUnitTest(const OsiSolverInterface * siP, 369 const std::string mpdDir ); 370 371 #endif 372