00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
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
00041 enum CglFlowColStatus{
00043 CGLFLOW_COL_PRIME,
00045 CGLFLOW_COL_SECONDARY
00046 };
00047
00050 enum CglFlowColCut{
00052 CGLFLOW_COL_OUTCUT = 0,
00054 CGLFLOW_COL_INCUT,
00056 CGLFLOW_COL_INCUTDONE,
00058 CGLFLOW_COL_INLMIN,
00060 CGLFLOW_COL_INLMINDONE,
00062 CGLFLOW_COL_INLMINMIN
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 int getVar() const { return varInd_; }
00129 double getVal() const { return upper_; }
00130 void setVar(const int v) { varInd_ = v; }
00131 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
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,
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 int 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
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
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
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
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