- Main Page
- Namespaces
- Classes
- Files
- Directories

- Search for |

- File List
- File Members

# CglFlowCover.hpp

Go to the documentation of this file.

    00001 // $Id: CglFlowCover.hpp 908 2010-12-30 21:54:29Z mjs $
    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