Cgl trunk
|
00001 // $Id$ 00002 //----------------------------------------------------------------------------- 00003 // name: Cgl Lifted Simple Generalized Flow Cover Cut Generator 00004 // author: Yan Xu email: yan.xu@sas.com 00005 // Jeff Linderoth email: jtl3@lehigh.edu 00006 // Martin Savelsberg email: martin.savelsbergh@isye.gatech.edu 00007 // date: 05/01/2003 00008 // comments: please scan this file for '???' and read the comments 00009 //----------------------------------------------------------------------------- 00010 // Copyright (C) 2003, Yan Xu, Jeff Linderoth, Martin Savelsberg and others. 00011 // All Rights Reserved. 00012 // This code is published under the Eclipse Public License. 00013 00014 #ifndef CglFlowCover_H 00015 #define CglFlowCover_H 00016 00017 #include <iostream> 00018 00019 #include "CoinError.hpp" 00020 00021 #include "CglCutGenerator.hpp" 00022 00023 //============================================================================= 00024 00025 //============================================================================= 00026 00028 enum CglFlowColType { 00030 CGLFLOW_COL_BINNEG = -2, 00032 CGLFLOW_COL_CONTNEG, 00034 CGLFLOW_COL_CONTPOS = 1, 00036 CGLFLOW_COL_BINPOS 00037 }; 00038 00039 enum CglFlowColStatus{ 00040 }; 00041 00044 enum CglFlowColCut{ 00046 CGLFLOW_COL_OUTCUT = 0, 00048 CGLFLOW_COL_INCUT, 00050 CGLFLOW_COL_INCUTDONE, 00052 CGLFLOW_COL_INLMIN, 00054 CGLFLOW_COL_INLMINDONE, 00056 CGLFLOW_COL_INLMINMIN, 00060 CGLFLOW_COL_PRIME, 00062 CGLFLOW_COL_SECONDARY 00063 }; 00064 00066 enum CglFlowRowType { 00068 CGLFLOW_ROW_UNDEFINED, 00072 CGLFLOW_ROW_VARUB, 00076 CGLFLOW_ROW_VARLB, 00079 CGLFLOW_ROW_VAREQ, 00082 CGLFLOW_ROW_MIXUB, 00084 CGLFLOW_ROW_MIXEQ, 00086 CGLFLOW_ROW_NOBINUB, 00088 CGLFLOW_ROW_NOBINEQ, 00091 CGLFLOW_ROW_SUMVARUB, 00094 CGLFLOW_ROW_SUMVAREQ, 00096 CGLFLOW_ROW_UNINTERSTED 00097 }; 00098 00099 //============================================================================= 00100 00102 class CglFlowVUB 00103 { 00104 protected: 00105 int varInd_; 00106 double upper_; 00108 public: 00109 CglFlowVUB() : varInd_(-1), upper_(-1) {} 00110 00111 CglFlowVUB(const CglFlowVUB& source) { 00112 varInd_= source.varInd_; 00113 upper_ = source.upper_; 00114 } 00115 00116 CglFlowVUB& operator=(const CglFlowVUB& rhs) { 00117 if (this == &rhs) 00118 return *this; 00119 varInd_= rhs.varInd_; 00120 upper_ = rhs.upper_; 00121 return *this; 00122 } 00123 00128 inline int getVar() const { return varInd_; } 00129 inline double getVal() const { return upper_; } 00130 inline void setVar(const int v) { varInd_ = v; } 00131 inline void setVal(const double v) { upper_ = v; } 00133 }; 00134 00135 //============================================================================= 00136 00138 typedef CglFlowVUB CglFlowVLB; 00139 00141 std::ostream& operator<<( std::ostream& os, const CglFlowVUB &v ); 00142 00143 //============================================================================= 00144 00148 class CglFlowCover : public CglCutGenerator { 00149 friend void CglFlowCoverUnitTest(const OsiSolverInterface * siP, 00150 const std::string mpdDir ); 00151 00152 public: 00153 00163 void flowPreprocess(const OsiSolverInterface& si) const; 00164 00171 virtual void generateCuts(const OsiSolverInterface & si, OsiCuts & cs, 00172 const CglTreeInfo info = CglTreeInfo()) const; 00174 00178 inline int getMaxNumCuts() const { return maxNumCuts_; } 00179 inline void setMaxNumCuts(int mc) { maxNumCuts_ = mc; } 00181 00185 static int getNumFlowCuts() { return numFlowCuts_; } 00186 static void setNumFlowCuts(int fc) { numFlowCuts_ = fc; } 00187 static void incNumFlowCuts(int fc = 1) { numFlowCuts_ += fc; } 00189 00190 //------------------------------------------------------------------------- 00193 00194 CglFlowCover (); 00195 00197 CglFlowCover ( 00198 const CglFlowCover &); 00199 00201 virtual CglCutGenerator * clone() const; 00202 00204 CglFlowCover & 00205 operator=( 00206 const CglFlowCover& rhs); 00207 00209 virtual 00210 ~CglFlowCover (); 00212 virtual std::string generateCpp( FILE * fp); 00214 00215 private: 00216 //------------------------------------------------------------------------- 00217 // Private member functions 00218 00222 bool generateOneFlowCut( const OsiSolverInterface & si, 00223 const int rowLen, 00224 int* ind, 00225 double* coef, 00226 char sense, 00227 double rhs, 00228 OsiRowCut& flowCut, 00229 double& violation ) const; 00230 00231 00233 void flipRow(int rowLen, double* coef, double& rhs) const; 00234 00236 void flipRow(int rowLen, double* coef, char& sen, double& rhs) const; 00237 00239 CglFlowRowType determineOneRowType(const OsiSolverInterface& si, 00240 int rowLen, int* ind, 00241 double* coef, char sen, 00242 double rhs) const; 00244 void liftMinus(double &movement, /* Output */ 00245 int t, 00246 int r, 00247 double z, 00248 double dPrimePrime, 00249 double lambda, 00250 double ml, 00251 double *M, 00252 double *rho) const; 00253 00254 bool liftPlus(double &alpha, 00255 double &beta, 00256 int r, 00257 double m_j, 00258 double lambda, 00259 double y_j, 00260 double x_j, 00261 double dPrimePrime, 00262 double *M) const; 00263 00264 00265 //------------------------------------------------------------------------- 00266 //**@name Query and set the row type of a givne row. */ 00268 inline const CglFlowRowType* getRowTypes() const 00269 { return rowTypes_; } 00270 inline CglFlowRowType getRowType(const int i) const 00271 { return rowTypes_[i]; } 00273 inline void setRowTypes(CglFlowRowType* rt) 00274 { rowTypes_ = rt; rt = 0; } 00275 inline void setRowTypes(const CglFlowRowType rt, const int i) { 00276 if (rowTypes_ != 0) 00277 rowTypes_[i] = rt; 00278 else { 00279 std::cout << "ERROR: Should allocate memory for rowType_ before " 00280 << "using it " << std::endl; 00281 throw CoinError("Forgot to allocate memory for rowType_", 00282 "setRowType", "CglFlowCover"); 00283 } 00284 } 00286 00287 //------------------------------------------------------------------------- 00288 //**@name Query and set vubs. */ 00290 inline const CglFlowVUB* getVubs() const { return vubs_; } 00291 inline const CglFlowVUB& getVubs(int i) const { return vubs_[i]; } 00293 inline void setVubs(CglFlowVUB* vubs) { vubs_ = vubs; vubs = 0; } 00294 inline void setVubs(const CglFlowVUB& vub, int i) { 00295 if (vubs_ != 0) 00296 vubs_[i] = vub; 00297 else { 00298 std::cout << "ERROR: Should allocate memory for vubs_ before " 00299 << "using it " << std::endl; 00300 throw CoinError("Forgot to allocate memory for vubs_", "setVubs", 00301 "CglFlowCover"); 00302 } 00303 } 00304 inline void printVubs(std::ostream& os) const { 00305 for (int i = 0; i < numCols_; ++i) { 00306 os << "ix: " << i << ", " << vubs_[i]; 00307 } 00308 } 00310 00311 //------------------------------------------------------------------------- 00312 //**@name Query and set vlbs. */ 00314 inline const CglFlowVLB* getVlbs() const { return vlbs_; } 00315 inline const CglFlowVLB& getVlbs(int i) const { return vlbs_[i]; } 00317 inline void setVlbs(CglFlowVLB* vlbs) { vlbs_ = vlbs; vlbs = 0; } 00318 inline void setVlbs(const CglFlowVLB& vlb, int i) { 00319 if (vlbs_ != 0) 00320 vlbs_[i] = vlb; 00321 else { 00322 std::cout << "ERROR: Should allocate memory for vlbs_ before " 00323 << "using it " << std::endl; 00324 throw CoinError("Forgot to allocate memory for vlbs_", "setVlbs", 00325 "CglFlowCover"); 00326 } 00327 } 00329 00330 private: 00331 //------------------------------------------------------------------------ 00332 // Private member data 00333 00335 int maxNumCuts_; 00337 double EPSILON_; 00339 int UNDEFINED_; 00341 double INFTY_; 00343 double TOLERANCE_; 00345 mutable bool firstProcess_; 00347 mutable int numRows_; 00349 mutable int numCols_; 00351 static int numFlowCuts_; 00353 mutable bool doneInitPre_; 00355 mutable CglFlowVUB* vubs_; 00357 mutable CglFlowVLB* vlbs_; 00359 mutable CglFlowRowType* rowTypes_; 00360 }; 00361 00362 //############################################################################# 00368 void CglFlowCoverUnitTest(const OsiSolverInterface * siP, 00369 const std::string mpdDir ); 00370 00371 #endif