CglFlowCover.hpp

Go to the documentation of this file.

// $Id: CglFlowCover.hpp 1119 2013-04-06 20:24:18Z stefan $
//-----------------------------------------------------------------------------
// 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; }
  
    static int getNumFlowCuts() { return numFlowCuts_; }
    static void setNumFlowCuts(int fc) { numFlowCuts_ = fc; }
    static 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_;
    static int numFlowCuts_;
    bool doneInitPre_;
    CglFlowVUB* vubs_;
    CglFlowVLB* vlbs_;
    CglFlowRowType* rowTypes_;
};

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

#endif