Loading...
Searching...
No Matches
CglFlowCover.hpp
Go to the documentation of this file.
// $Id$
//-----------------------------------------------------------------------------
// 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
CglCutGenerator.hpp
CglFlowColType
CglFlowColType
This enumerative constant describes the various col types.
Definition CglFlowCover.hpp:28
CGLFLOW_COL_BINPOS
@ CGLFLOW_COL_BINPOS
The column is a positive binary variable.
Definition CglFlowCover.hpp:36
CGLFLOW_COL_BINNEG
@ CGLFLOW_COL_BINNEG
The column(variable) is a negative binary variable.
Definition CglFlowCover.hpp:30
CGLFLOW_COL_CONTPOS
@ CGLFLOW_COL_CONTPOS
The column is a positive continous variable.
Definition CglFlowCover.hpp:34
CGLFLOW_COL_CONTNEG
@ CGLFLOW_COL_CONTNEG
The column is a negative continous variable.
Definition CglFlowCover.hpp:32
CglFlowColStatus
CglFlowColStatus
Definition CglFlowCover.hpp:39
CglFlowCoverUnitTest
void CglFlowCoverUnitTest(const OsiSolverInterface *siP, const std::string mpdDir)
A function that tests the methods in the CglFlowCover class.
CglFlowRowType
CglFlowRowType
This enumerative constant describes the various row types.
Definition CglFlowCover.hpp:66
CGLFLOW_ROW_NOBINUB
@ CGLFLOW_ROW_NOBINUB
All variables are NOT binary and the row sense is NOT 'E'.
Definition CglFlowCover.hpp:86
CGLFLOW_ROW_UNINTERSTED
@ CGLFLOW_ROW_UNINTERSTED
All variables are binary.
Definition CglFlowCover.hpp:96
CGLFLOW_ROW_SUMVARUB
@ CGLFLOW_ROW_SUMVARUB
The row has one binary and 2 or more other types of variables and the row sense is NOT 'E'.
Definition CglFlowCover.hpp:91
CGLFLOW_ROW_VARUB
@ CGLFLOW_ROW_VARUB
After the row is flipped to 'L', the row has exactly two variables: one is negative binary and the ot...
Definition CglFlowCover.hpp:72
CGLFLOW_ROW_VARLB
@ CGLFLOW_ROW_VARLB
After the row is flipped to 'L', the row has exactlytwo variables: one is positive binary and the oth...
Definition CglFlowCover.hpp:76
CGLFLOW_ROW_MIXEQ
@ CGLFLOW_ROW_MIXEQ
Rows can not be classfied into other types and the row sense is 'E'.
Definition CglFlowCover.hpp:84
CGLFLOW_ROW_VAREQ
@ CGLFLOW_ROW_VAREQ
The row sense is 'E', the row has exactly two variables: one is binary and the other is a continous,...
Definition CglFlowCover.hpp:79
CGLFLOW_ROW_UNDEFINED
@ CGLFLOW_ROW_UNDEFINED
The row type of this row is NOT defined yet.
Definition CglFlowCover.hpp:68
CGLFLOW_ROW_SUMVAREQ
@ CGLFLOW_ROW_SUMVAREQ
The row has one binary and 2 or more other types of variables and the row sense is 'E'.
Definition CglFlowCover.hpp:94
CGLFLOW_ROW_MIXUB
@ CGLFLOW_ROW_MIXUB
Rows can not be classfied into other types and the row sense is NOT 'E'.
Definition CglFlowCover.hpp:82
CGLFLOW_ROW_NOBINEQ
@ CGLFLOW_ROW_NOBINEQ
All variables are NOT binary and the row sense is 'E'.
Definition CglFlowCover.hpp:88
CglFlowColCut
CglFlowColCut
This enumerative constant describes the various stati of vars in a cut or not.
Definition CglFlowCover.hpp:44
CGLFLOW_COL_SECONDARY
@ CGLFLOW_COL_SECONDARY
The column is a secondary candidate.
Definition CglFlowCover.hpp:62
CGLFLOW_COL_INLMINDONE
@ CGLFLOW_COL_INLMINDONE
The column is decided to be in L-.
Definition CglFlowCover.hpp:54
CGLFLOW_COL_INCUTDONE
@ CGLFLOW_COL_INCUTDONE
The column is decided to be in cover.
Definition CglFlowCover.hpp:50
CGLFLOW_COL_INLMIN
@ CGLFLOW_COL_INLMIN
The column is in L-.
Definition CglFlowCover.hpp:52
CGLFLOW_COL_INLMINMIN
@ CGLFLOW_COL_INLMINMIN
The column is in L–.
Definition CglFlowCover.hpp:56
CGLFLOW_COL_PRIME
@ CGLFLOW_COL_PRIME
This enumerative constant describes the various stati of vars in determining the cover.
Definition CglFlowCover.hpp:60
CGLFLOW_COL_INCUT
@ CGLFLOW_COL_INCUT
The column is in cover now.
Definition CglFlowCover.hpp:48
CGLFLOW_COL_OUTCUT
@ CGLFLOW_COL_OUTCUT
The column is NOT in cover.
Definition CglFlowCover.hpp:46
operator<<
std::ostream & operator<<(std::ostream &os, const CglFlowVUB &v)
Overloaded operator<< for printing VUB and VLB.
CglFlowVLB
CglFlowVUB CglFlowVLB
Variable lower bound class, which is the same as vub.
Definition CglFlowCover.hpp:138
CglCutGenerator::CglCutGenerator
CglCutGenerator()
Default constructor.
CglFlowCover::setVlbs
void setVlbs(const CglFlowVLB &vlb, int i)
Definition CglFlowCover.hpp:318
CglFlowCover::numFlowCuts_
int numFlowCuts_
The number flow cuts found.
Definition CglFlowCover.hpp:351
CglFlowCover::firstProcess_
bool firstProcess_
First time preprocessing.
Definition CglFlowCover.hpp:345
CglFlowCover::getVubs
const CglFlowVUB & getVubs(int i) const
Definition CglFlowCover.hpp:291
CglFlowCover::TOLERANCE_
double TOLERANCE_
If violation of a cut is greater that this number, the cut is useful.
Definition CglFlowCover.hpp:343
CglFlowCover::flipRow
void flipRow(int rowLen, double *coef, double &rhs) const
Transform a row from ">=" to "<=", and vice versa.
CglFlowCover::setMaxNumCuts
void setMaxNumCuts(int mc)
Definition CglFlowCover.hpp:179
CglFlowCover::setVlbs
void setVlbs(CglFlowVLB *vlbs)
Set CglFlowVLBs,take over the ownership.
Definition CglFlowCover.hpp:317
CglFlowCover::setVubs
void setVubs(CglFlowVUB *vubs)
Set CglFlowVUBs,take over the ownership.
Definition CglFlowCover.hpp:293
CglFlowCover::determineOneRowType
CglFlowRowType determineOneRowType(const OsiSolverInterface &si, int rowLen, int *ind, double *coef, char sen, double rhs) const
Determine the type of a given row.
CglFlowCover::flipRow
void flipRow(int rowLen, double *coef, char &sen, double &rhs) const
Transform a row from ">=" to "<=", and vice versa.
CglFlowCover::CglFlowCover
CglFlowCover()
Default constructor.
CglFlowCover::numRows_
int numRows_
The number rows of the problem.
Definition CglFlowCover.hpp:347
CglFlowCover::getVlbs
const CglFlowVLB & getVlbs(int i) const
Definition CglFlowCover.hpp:315
CglFlowCover::getVlbs
const CglFlowVLB * getVlbs() const
Definition CglFlowCover.hpp:314
CglFlowCover::getMaxNumCuts
int getMaxNumCuts() const
Definition CglFlowCover.hpp:178
CglFlowCover::getRowTypes
const CglFlowRowType * getRowTypes() const
Definition CglFlowCover.hpp:268
CglFlowCover::setRowTypes
void setRowTypes(CglFlowRowType *rt)
Set rowtypes, take over the ownership.
Definition CglFlowCover.hpp:273
CglFlowCover::incNumFlowCuts
void incNumFlowCuts(int fc=1)
Definition CglFlowCover.hpp:187
CglFlowCover::operator=
CglFlowCover & operator=(const CglFlowCover &rhs)
Assignment operator.
CglFlowCover::printVubs
void printVubs(std::ostream &os) const
Definition CglFlowCover.hpp:304
CglFlowCover::maxNumCuts_
int maxNumCuts_
The maximum number of flow cuts to be generated.
Definition CglFlowCover.hpp:335
CglFlowCover::generateCuts
virtual void generateCuts(const OsiSolverInterface &si, OsiCuts &cs, const CglTreeInfo info=CglTreeInfo())
Generate Lifed Simple Generalized flow cover cuts for the model data contained in si.
CglFlowCover::setNumFlowCuts
void setNumFlowCuts(int fc)
Definition CglFlowCover.hpp:186
CglFlowCover::EPSILON_
double EPSILON_
Tolerance used for numerical purpose.
Definition CglFlowCover.hpp:337
CglFlowCover::generateOneFlowCut
bool generateOneFlowCut(const OsiSolverInterface &si, const int rowLen, int *ind, double *coef, char sense, double rhs, OsiRowCut &flowCut, double &violation)
Based a given row, a LP solution and other model data, this function tries to generate a violated lif...
CglFlowCover::getNumFlowCuts
int getNumFlowCuts()
Definition CglFlowCover.hpp:185
CglFlowCover::getVubs
const CglFlowVUB * getVubs() const
Definition CglFlowCover.hpp:290
CglFlowCover::numCols_
int numCols_
The number columns of the problem.
Definition CglFlowCover.hpp:349
CglFlowCover::getRowType
CglFlowRowType getRowType(const int i) const
Definition CglFlowCover.hpp:270
CglFlowCover::~CglFlowCover
virtual ~CglFlowCover()
Destructor.
CglFlowCover::generateCpp
virtual std::string generateCpp(FILE *fp)
Create C++ lines to get to current state.
CglFlowCover::setRowTypes
void setRowTypes(const CglFlowRowType rt, const int i)
Definition CglFlowCover.hpp:275
CglFlowCover::vubs_
CglFlowVUB * vubs_
The array of CglFlowVUBs.
Definition CglFlowCover.hpp:355
CglFlowCover::setVubs
void setVubs(const CglFlowVUB &vub, int i)
Definition CglFlowCover.hpp:294
CglFlowCover::CglFlowCoverUnitTest
friend void CglFlowCoverUnitTest(const OsiSolverInterface *siP, const std::string mpdDir)
A function that tests the methods in the CglFlowCover class.
CglFlowCover::vlbs_
CglFlowVLB * vlbs_
The array of CglFlowVLBs.
Definition CglFlowCover.hpp:357
CglFlowCover::flowPreprocess
void flowPreprocess(const OsiSolverInterface &si)
Do the following tasks:
CglFlowCover::clone
virtual CglCutGenerator * clone() const
Clone.
CglFlowCover::liftMinus
void liftMinus(double &movement, int t, int r, double z, double dPrimePrime, double lambda, double ml, double *M, double *rho) const
Lift functions.
CglFlowCover::rowTypes_
CglFlowRowType * rowTypes_
CglFlowRowType of the rows in model.
Definition CglFlowCover.hpp:359
CglFlowCover::CglFlowCover
CglFlowCover(const CglFlowCover &)
Copy constructor.
CglFlowCover::INFTY_
double INFTY_
Very large number.
Definition CglFlowCover.hpp:341
CglFlowCover::liftPlus
bool liftPlus(double &alpha, double &beta, int r, double m_j, double lambda, double y_j, double x_j, double dPrimePrime, double *M) const
CglFlowCover::doneInitPre_
bool doneInitPre_
Indicate whether initial flow preprecessing has been done.
Definition CglFlowCover.hpp:353
CglFlowCover::UNDEFINED_
int UNDEFINED_
The variable upper bound of a flow is not indentified yet.
Definition CglFlowCover.hpp:339
CglFlowVUB
Variable upper bound class.
Definition CglFlowCover.hpp:103
CglFlowVUB::setVar
void setVar(const int v)
Definition CglFlowCover.hpp:130
CglFlowVUB::operator=
CglFlowVUB & operator=(const CglFlowVUB &rhs)
Definition CglFlowCover.hpp:116
CglFlowVUB::varInd_
int varInd_
Definition CglFlowCover.hpp:105
CglFlowVUB::CglFlowVUB
CglFlowVUB(const CglFlowVUB &source)
Definition CglFlowCover.hpp:111
CglFlowVUB::setVal
void setVal(const double v)
Definition CglFlowCover.hpp:131
CglFlowVUB::upper_
double upper_
The index of the associated 0-1 variable.
Definition CglFlowCover.hpp:106
CglFlowVUB::getVal
double getVal() const
Definition CglFlowCover.hpp:129
CglFlowVUB::getVar
int getVar() const
Definition CglFlowCover.hpp:128
CglFlowVUB::CglFlowVUB
CglFlowVUB()
The Value of the associated upper bound.
Definition CglFlowCover.hpp:109
CglTreeInfo
Information about where the cut generator is invoked from.
Definition CglTreeInfo.hpp:15