CglFlowCover.hpp

Go to the documentation of this file.

// $Id: CglFlowCover.hpp 1370 2017-03-30 10:49:25Z forrest $
//-----------------------------------------------------------------------------
// name:     Cgl Lifted Simple Generalized Flow Cover Cut Generator
// author:   Yan Xu                email: yan.xu@sas.com
//           Jeff Linderoth        email: jtl3@lehigh.edu
//           Martin Savelsberg     email: martin.savelsbergh@isye.gatech.edu
// date:     05/01/2003
// comments: please scan this file for '???' and read the comments
//-----------------------------------------------------------------------------
// Copyright (C) 2003, Yan Xu, Jeff Linderoth, Martin Savelsberg and others. 
// All Rights Reserved.
// This code is published under the Eclipse Public License.

#ifndef CglFlowCover_H
#define CglFlowCover_H

#include <iostream>

#include "CoinError.hpp"

#include "CglCutGenerator.hpp"

//=============================================================================

//=============================================================================

enum CglFlowColType {
    CGLFLOW_COL_BINNEG  = -2,
    CGLFLOW_COL_CONTNEG,
    CGLFLOW_COL_CONTPOS =  1,
    CGLFLOW_COL_BINPOS
};

enum CglFlowColStatus{
};

enum CglFlowColCut{
    CGLFLOW_COL_OUTCUT = 0,
    CGLFLOW_COL_INCUT,
    CGLFLOW_COL_INCUTDONE,
    CGLFLOW_COL_INLMIN,
    CGLFLOW_COL_INLMINDONE,
    CGLFLOW_COL_INLMINMIN,
    CGLFLOW_COL_PRIME,
    CGLFLOW_COL_SECONDARY
};

enum CglFlowRowType {
    CGLFLOW_ROW_UNDEFINED,
    CGLFLOW_ROW_VARUB,
    CGLFLOW_ROW_VARLB,
    CGLFLOW_ROW_VAREQ,
    CGLFLOW_ROW_MIXUB,
    CGLFLOW_ROW_MIXEQ,
    CGLFLOW_ROW_NOBINUB,
    CGLFLOW_ROW_NOBINEQ,
    CGLFLOW_ROW_SUMVARUB,
    CGLFLOW_ROW_SUMVAREQ,
    CGLFLOW_ROW_UNINTERSTED
};

//=============================================================================

class CglFlowVUB
{
protected:
    int    varInd_;            
    double upper_;             
public:
    CglFlowVUB() : varInd_(-1), upper_(-1) {}
    
    CglFlowVUB(const CglFlowVUB& source) { 
    varInd_= source.varInd_; 
    upper_ = source.upper_; 
    } 
    
    CglFlowVUB& operator=(const CglFlowVUB& rhs) { 
    if (this == &rhs) 
        return *this;
    varInd_= rhs.varInd_; 
    upper_ = rhs.upper_; 
    return *this; 
  }
    
    inline int    getVar() const          { return varInd_; }
    inline double getVal() const          { return upper_; }
    inline void   setVar(const int v)     { varInd_ = v; }
    inline void   setVal(const double v)  { upper_ = v; }
};

//=============================================================================

typedef CglFlowVUB CglFlowVLB;

std::ostream& operator<<( std::ostream& os, const CglFlowVUB &v );

//=============================================================================

class CglFlowCover : public CglCutGenerator {
    friend void CglFlowCoverUnitTest(const OsiSolverInterface * siP,
                     const std::string mpdDir );
    
public:
    
    void flowPreprocess(const OsiSolverInterface& si);

    virtual void generateCuts(const OsiSolverInterface & si, OsiCuts & cs,
                  const CglTreeInfo info = CglTreeInfo());

    inline int getMaxNumCuts() const { return maxNumCuts_; }
    inline void setMaxNumCuts(int mc) { maxNumCuts_ = mc; }
  
    inline int getNumFlowCuts() { return numFlowCuts_; }
    inline void setNumFlowCuts(int fc) { numFlowCuts_ = fc; }
    inline void incNumFlowCuts(int fc = 1) { numFlowCuts_ += fc; } 

    //-------------------------------------------------------------------------
    CglFlowCover ();

    CglFlowCover (
    const CglFlowCover &);

    virtual CglCutGenerator * clone() const;

    CglFlowCover &
    operator=(
    const CglFlowCover& rhs);
    
    virtual
    ~CglFlowCover ();
    virtual std::string generateCpp( FILE * fp);

private:
    //-------------------------------------------------------------------------
    // Private member functions

    bool generateOneFlowCut( const OsiSolverInterface & si, 
                 const int rowLen,
                 int* ind,
                 double* coef,
                 char sense,
                 double rhs,
                 OsiRowCut& flowCut,
                 double& violation );


    void flipRow(int rowLen, double* coef, double& rhs) const;

    void flipRow(int rowLen, double* coef, char& sen, double& rhs) const;

    CglFlowRowType determineOneRowType(const OsiSolverInterface& si,
                       int rowLen, int* ind, 
                       double* coef, char sen, 
                       double rhs) const;
    void liftMinus(double &movement, /* Output */ 
           int t,
           int r,
           double z,
           double dPrimePrime, 
           double lambda,
            double ml,
           double *M,
           double *rho) const;

    bool liftPlus(double &alpha, 
         double &beta,
         int r,
         double m_j, 
         double lambda,
         double y_j,
         double x_j,
         double dPrimePrime,
         double *M) const;
    

    //-------------------------------------------------------------------------
    //**@name Query and set the row type of a givne row. */
    inline const CglFlowRowType* getRowTypes() const 
    { return rowTypes_; }
    inline CglFlowRowType getRowType(const int i) const 
    { return rowTypes_[i]; }
    inline void setRowTypes(CglFlowRowType* rt) 
    { rowTypes_ = rt; rt = 0; }  
    inline void setRowTypes(const CglFlowRowType rt, const int i) {
    if (rowTypes_ != 0) 
        rowTypes_[i] = rt;
    else {
        std::cout << "ERROR: Should allocate memory for rowType_ before "
              << "using it " << std::endl;
        throw CoinError("Forgot to allocate memory for rowType_", 
                "setRowType", "CglFlowCover");
    }
    }
    
    //-------------------------------------------------------------------------
    //**@name Query and set vubs. */
    inline const CglFlowVUB* getVubs() const          { return vubs_; }
    inline const CglFlowVUB& getVubs(int i) const     { return vubs_[i]; }
    inline void setVubs(CglFlowVUB* vubs) { vubs_ = vubs; vubs = 0; }
    inline void setVubs(const CglFlowVUB& vub, int i) { 
    if (vubs_ != 0) 
        vubs_[i] = vub;
    else {
        std::cout << "ERROR: Should allocate memory for vubs_ before "
              << "using it " << std::endl;
        throw CoinError("Forgot to allocate memory for vubs_", "setVubs",
                "CglFlowCover");
    }
    }
    inline void printVubs(std::ostream& os) const {
    for (int i = 0; i < numCols_; ++i) {
        os << "ix: " << i << ", " << vubs_[i];
    }
    }

    //-------------------------------------------------------------------------
    //**@name Query and set vlbs. */
    inline const CglFlowVLB* getVlbs() const          { return vlbs_; }
    inline const CglFlowVLB& getVlbs(int i) const     { return vlbs_[i]; }
    inline void setVlbs(CglFlowVLB* vlbs)          { vlbs_ = vlbs; vlbs = 0; }
    inline void setVlbs(const CglFlowVLB& vlb, int i) { 
    if (vlbs_ != 0) 
        vlbs_[i] = vlb;
    else {
        std::cout << "ERROR: Should allocate memory for vlbs_ before "
              << "using it " << std::endl;
        throw CoinError("Forgot to allocate memory for vlbs_", "setVlbs",
                "CglFlowCover");
    }
    }

private:
    //------------------------------------------------------------------------
    // Private member data
    
    int maxNumCuts_;
    double EPSILON_;
    int UNDEFINED_;
    double INFTY_;
    double TOLERANCE_;
    bool firstProcess_;
    int numRows_;
    int numCols_;
    int numFlowCuts_;
    bool doneInitPre_;
    CglFlowVUB* vubs_;
    CglFlowVLB* vlbs_;
    CglFlowRowType* rowTypes_;
};

//#############################################################################
void CglFlowCoverUnitTest(const OsiSolverInterface * siP,
              const std::string mpdDir );

#endif