- Main Page
- Related Pages
- Modules
- Namespaces
- Classes
- Files

- File List
- File Members

CglFlowCover.hpp
Go to the documentation of this file.
1 // $Id: CglFlowCover.hpp 1119 2013-04-06 20:24:18Z stefan $
2 //-----------------------------------------------------------------------------
3 // name: Cgl Lifted Simple Generalized Flow Cover Cut Generator
4 // author: Yan Xu email: yan.xu@sas.com
5 // Jeff Linderoth email: jtl3@lehigh.edu
6 // Martin Savelsberg email: martin.savelsbergh@isye.gatech.edu
7 // date: 05/01/2003
8 // comments: please scan this file for '???' and read the comments
9 //-----------------------------------------------------------------------------
10 // Copyright (C) 2003, Yan Xu, Jeff Linderoth, Martin Savelsberg and others.
11 // All Rights Reserved.
12 // This code is published under the Eclipse Public License.
13
14 #ifndef CglFlowCover_H
15 #define CglFlowCover_H
16
17 #include <iostream>
18
19 #include "CoinError.hpp"
20
21 #include "CglCutGenerator.hpp"
22
23 //=============================================================================
24
25 //=============================================================================
26
28 enum CglFlowColType {
30 CGLFLOW_COL_BINNEG = -2,
32 CGLFLOW_COL_CONTNEG,
34 CGLFLOW_COL_CONTPOS = 1,
36 CGLFLOW_COL_BINPOS
37 };
38
39 enum CglFlowColStatus{
40 };
41
44 enum CglFlowColCut{
46 CGLFLOW_COL_OUTCUT = 0,
48 CGLFLOW_COL_INCUT,
50 CGLFLOW_COL_INCUTDONE,
52 CGLFLOW_COL_INLMIN,
54 CGLFLOW_COL_INLMINDONE,
56 CGLFLOW_COL_INLMINMIN,
60 CGLFLOW_COL_PRIME,
62 CGLFLOW_COL_SECONDARY
63 };
64
66 enum CglFlowRowType {
68 CGLFLOW_ROW_UNDEFINED,
72 CGLFLOW_ROW_VARUB,
76 CGLFLOW_ROW_VARLB,
79 CGLFLOW_ROW_VAREQ,
82 CGLFLOW_ROW_MIXUB,
84 CGLFLOW_ROW_MIXEQ,
86 CGLFLOW_ROW_NOBINUB,
88 CGLFLOW_ROW_NOBINEQ,
91 CGLFLOW_ROW_SUMVARUB,
94 CGLFLOW_ROW_SUMVAREQ,
96 CGLFLOW_ROW_UNINTERSTED
97 };
98
99 //=============================================================================
100
102 class CglFlowVUB
103 {
104 protected:
105 int varInd_;
106 double upper_;
108 public:
109 CglFlowVUB() : varInd_(-1), upper_(-1) {}
110
111 CglFlowVUB(const CglFlowVUB& source) {
112 varInd_= source.varInd_;
113 upper_ = source.upper_;
114 }
115
116 CglFlowVUB& operator=(const CglFlowVUB& rhs) {
117 if (this == &rhs)
118 return *this;
119 varInd_= rhs.varInd_;
120 upper_ = rhs.upper_;
121 return *this;
122 }
123
128 inline int getVar() const { return varInd_; }
129 inline double getVal() const { return upper_; }
130 inline void setVar(const int v) { varInd_ = v; }
131 inline void setVal(const double v) { upper_ = v; }
133 };
134
135 //=============================================================================
136
138 typedef CglFlowVUB CglFlowVLB;
139
141 std::ostream& operator<<( std::ostream& os, const CglFlowVUB &v );
142
143 //=============================================================================
144
148 class CglFlowCover : public CglCutGenerator {
149 friend void CglFlowCoverUnitTest(const OsiSolverInterface * siP,
150 const std::string mpdDir );
151
152 public:
153
163 void flowPreprocess(const OsiSolverInterface& si);
164
171 virtual void generateCuts(const OsiSolverInterface & si, OsiCuts & cs,
172 const CglTreeInfo info = CglTreeInfo());
174
178 inline int getMaxNumCuts() const { return maxNumCuts_; }
179 inline void setMaxNumCuts(int mc) { maxNumCuts_ = mc; }
181
185 static int getNumFlowCuts() { return numFlowCuts_; }
186 static void setNumFlowCuts(int fc) { numFlowCuts_ = fc; }
187 static void incNumFlowCuts(int fc = 1) { numFlowCuts_ += fc; }
189
190 //-------------------------------------------------------------------------
193 CglFlowCover ();
195
197 CglFlowCover (
198 const CglFlowCover &);
199
201 virtual CglCutGenerator * clone() const;
202
204 CglFlowCover &
205 operator=(
206 const CglFlowCover& rhs);
207
209 virtual
210 ~CglFlowCover ();
212 virtual std::string generateCpp( FILE * fp);
214
215 private:
216 //-------------------------------------------------------------------------
217 // Private member functions
218
222 bool generateOneFlowCut( const OsiSolverInterface & si,
223 const int rowLen,
224 int* ind,
225 double* coef,
226 char sense,
227 double rhs,
228 OsiRowCut& flowCut,
229 double& violation );
230
231
233 void flipRow(int rowLen, double* coef, double& rhs) const;
234
236 void flipRow(int rowLen, double* coef, char& sen, double& rhs) const;
237
239 CglFlowRowType determineOneRowType(const OsiSolverInterface& si,
240 int rowLen, int* ind,
241 double* coef, char sen,
242 double rhs) const;
244 void liftMinus(double &movement, /* Output */
245 int t,
246 int r,
247 double z,
248 double dPrimePrime,
249 double lambda,
250 double ml,
251 double *M,
252 double *rho) const;
253
254 bool liftPlus(double &alpha,
255 double &beta,
256 int r,
257 double m_j,
258 double lambda,
259 double y_j,
260 double x_j,
261 double dPrimePrime,
262 double *M) const;
263
264
265 //-------------------------------------------------------------------------
266 //**@name Query and set the row type of a givne row. */
268 inline const CglFlowRowType* getRowTypes() const
269 { return rowTypes_; }
270 inline CglFlowRowType getRowType(const int i) const
271 { return rowTypes_[i]; }
273 inline void setRowTypes(CglFlowRowType* rt)
274 { rowTypes_ = rt; rt = 0; }
275 inline void setRowTypes(const CglFlowRowType rt, const int i) {
276 if (rowTypes_ != 0)
277 rowTypes_[i] = rt;
278 else {
279 std::cout << "ERROR: Should allocate memory for rowType_ before "
280 << "using it " << std::endl;
281 throw CoinError("Forgot to allocate memory for rowType_",
282 "setRowType", "CglFlowCover");
283 }
284 }
286
287 //-------------------------------------------------------------------------
288 //**@name Query and set vubs. */
290 inline const CglFlowVUB* getVubs() const { return vubs_; }
291 inline const CglFlowVUB& getVubs(int i) const { return vubs_[i]; }
293 inline void setVubs(CglFlowVUB* vubs) { vubs_ = vubs; vubs = 0; }
294 inline void setVubs(const CglFlowVUB& vub, int i) {
295 if (vubs_ != 0)
296 vubs_[i] = vub;
297 else {
298 std::cout << "ERROR: Should allocate memory for vubs_ before "
299 << "using it " << std::endl;
300 throw CoinError("Forgot to allocate memory for vubs_", "setVubs",
301 "CglFlowCover");
302 }
303 }
304 inline void printVubs(std::ostream& os) const {
305 for (int i = 0; i < numCols_; ++i) {
306 os << "ix: " << i << ", " << vubs_[i];
307 }
308 }
310
311 //-------------------------------------------------------------------------
312 //**@name Query and set vlbs. */
314 inline const CglFlowVLB* getVlbs() const { return vlbs_; }
315 inline const CglFlowVLB& getVlbs(int i) const { return vlbs_[i]; }
317 inline void setVlbs(CglFlowVLB* vlbs) { vlbs_ = vlbs; vlbs = 0; }
318 inline void setVlbs(const CglFlowVLB& vlb, int i) {
319 if (vlbs_ != 0)
320 vlbs_[i] = vlb;
321 else {
322 std::cout << "ERROR: Should allocate memory for vlbs_ before "
323 << "using it " << std::endl;
324 throw CoinError("Forgot to allocate memory for vlbs_", "setVlbs",
325 "CglFlowCover");
326 }
327 }
329
330 private:
331 //------------------------------------------------------------------------
332 // Private member data
333
335 int maxNumCuts_;
337 double EPSILON_;
339 int UNDEFINED_;
341 double INFTY_;
343 double TOLERANCE_;
345 bool firstProcess_;
347 int numRows_;
349 int numCols_;
351 static int numFlowCuts_;
353 bool doneInitPre_;
355 CglFlowVUB* vubs_;
357 CglFlowVLB* vlbs_;
359 CglFlowRowType* rowTypes_;
360 };
361
362 //#############################################################################
368 void CglFlowCoverUnitTest(const OsiSolverInterface * siP,
369 const std::string mpdDir );
370
371 #endif
CGLFLOW_ROW_NOBINUB
All variables are NOT binary and the row sense is NOT &#39;E&#39;.
Definition: CglFlowCover.hpp:86
CglFlowCover::TOLERANCE_
double TOLERANCE_
If violation of a cut is greater that this number, the cut is useful.
Definition: CglFlowCover.hpp:343
CGLFLOW_ROW_SUMVAREQ
The row has one binary and 2 or more other types of variables and the row sense is &#39;E&#39;...
Definition: CglFlowCover.hpp:94
CglFlowCover::firstProcess_
bool firstProcess_
First time preprocessing.
Definition: CglFlowCover.hpp:345
CglFlowCover::setVlbs
void setVlbs(const CglFlowVLB &vlb, int i)
Set CglFlowVLBs,take over the ownership.
Definition: CglFlowCover.hpp:318
CglFlowCover::flipRow
void flipRow(int rowLen, double *coef, double &rhs) const
Transform a row from &quot;&gt;=&quot; to &quot;&lt;=&quot;, and vice versa.
CGLFLOW_ROW_MIXEQ
Rows can not be classfied into other types and the row sense is &#39;E&#39;.
Definition: CglFlowCover.hpp:84
CGLFLOW_COL_PRIME
This enumerative constant describes the various stati of vars in determining the cover.
Definition: CglFlowCover.hpp:60
CglFlowCover::setVubs
void setVubs(const CglFlowVUB &vub, int i)
Set CglFlowVUBs,take over the ownership.
Definition: CglFlowCover.hpp:294
CglFlowCover::getVubs
const CglFlowVUB * getVubs() const
Set CglFlowVUBs,take over the ownership.
Definition: CglFlowCover.hpp:290
CglFlowCover::printVubs
void printVubs(std::ostream &os) const
Set CglFlowVUBs,take over the ownership.
Definition: CglFlowCover.hpp:304
CglFlowVUB::getVal
double getVal() const
Definition: CglFlowCover.hpp:129
CGLFLOW_COL_BINPOS
The column is a positive binary variable.
Definition: CglFlowCover.hpp:36
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...
OsiRowCut
Row Cut Class.
Definition: OsiRowCut.hpp:29
CGLFLOW_COL_SECONDARY
The column is a secondary candidate.
Definition: CglFlowCover.hpp:62
CglFlowVUB::upper_
double upper_
The index of the associated 0-1 variable.
Definition: CglFlowCover.hpp:106
CGLFLOW_COL_INLMINMIN
The column is in L–.
Definition: CglFlowCover.hpp:56
CGLFLOW_COL_INLMINDONE
The column is decided to be in L-.
Definition: CglFlowCover.hpp:54
CglFlowColStatus
CglFlowColStatus
Definition: CglFlowCover.hpp:39
CoinError.hpp
CglFlowVUB::setVal
void setVal(const double v)
Definition: CglFlowCover.hpp:131
CglFlowVUB::operator=
CglFlowVUB & operator=(const CglFlowVUB &rhs)
Definition: CglFlowCover.hpp:116
CglFlowColCut
CglFlowColCut
This enumerative constant describes the various stati of vars in a cut or not.
Definition: CglFlowCover.hpp:44
CglFlowCover::setMaxNumCuts
void setMaxNumCuts(int mc)
Definition: CglFlowCover.hpp:179
CGLFLOW_COL_INCUTDONE
The column is decided to be in cover.
Definition: CglFlowCover.hpp:50
CglFlowVUB::CglFlowVUB
CglFlowVUB(const CglFlowVUB &source)
Definition: CglFlowCover.hpp:111
CglFlowCoverUnitTest
void CglFlowCoverUnitTest(const OsiSolverInterface *siP, const std::string mpdDir)
A function that tests the methods in the CglFlowCover class.
CglFlowCover::CglFlowCoverUnitTest
friend void CglFlowCoverUnitTest(const OsiSolverInterface *siP, const std::string mpdDir)
A function that tests the methods in the CglFlowCover class.
CGLFLOW_ROW_UNDEFINED
The row type of this row is NOT defined yet.
Definition: CglFlowCover.hpp:68
CglFlowCover::setRowTypes
void setRowTypes(const CglFlowRowType rt, const int i)
Set rowtypes, take over the ownership.
Definition: CglFlowCover.hpp:275
CglFlowCover::INFTY_
double INFTY_
Very large number.
Definition: CglFlowCover.hpp:341
OsiCuts
Collections of row cuts and column cuts.
Definition: OsiCuts.hpp:19
CglFlowVUB::setVar
void setVar(const int v)
Definition: CglFlowCover.hpp:130
CglFlowCover
Lifed Simple Generalized Flow Cover Cut Generator Class.
Definition: CglFlowCover.hpp:148
CglFlowCover::setRowTypes
void setRowTypes(CglFlowRowType *rt)
Set rowtypes, take over the ownership.
Definition: CglFlowCover.hpp:273
CglFlowVUB::CglFlowVUB
CglFlowVUB()
The Value of the associated upper bound.
Definition: CglFlowCover.hpp:109
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::numFlowCuts_
static int numFlowCuts_
The number flow cuts found.
Definition: CglFlowCover.hpp:351
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...
CglFlowColType
CglFlowColType
This enumerative constant describes the various col types.
Definition: CglFlowCover.hpp:28
CglFlowCover::generateCpp
virtual std::string generateCpp(FILE *fp)
Create C++ lines to get to current state.
CglCutGenerator.hpp
CglFlowVUB::varInd_
int varInd_
Definition: CglFlowCover.hpp:105
CglFlowCover::rowTypes_
CglFlowRowType * rowTypes_
CglFlowRowType of the rows in model.
Definition: CglFlowCover.hpp:359
CglFlowCover::maxNumCuts_
int maxNumCuts_
The maximum number of flow cuts to be generated.
Definition: CglFlowCover.hpp:335
CglFlowCover::getMaxNumCuts
int getMaxNumCuts() const
Definition: CglFlowCover.hpp:178
CglFlowCover::operator=
CglFlowCover & operator=(const CglFlowCover &rhs)
Assignment operator.
CglFlowCover::getNumFlowCuts
static int getNumFlowCuts()
Definition: CglFlowCover.hpp:185
CGLFLOW_ROW_VARUB
After the row is flipped to &#39;L&#39;, the row has exactly two variables: one is negative binary and the ot...
Definition: CglFlowCover.hpp:72
CglFlowCover::vubs_
CglFlowVUB * vubs_
The array of CglFlowVUBs.
Definition: CglFlowCover.hpp:355
CglFlowCover::setVubs
void setVubs(CglFlowVUB *vubs)
Set CglFlowVUBs,take over the ownership.
Definition: CglFlowCover.hpp:293
OsiSolverInterface
Abstract Base Class for describing an interface to a solver.
Definition: OsiSolverInterface.hpp:62
CglFlowCover::UNDEFINED_
int UNDEFINED_
The variable upper bound of a flow is not indentified yet.
Definition: CglFlowCover.hpp:339
CglCutGenerator
Cut Generator Base Class.
Definition: CglCutGenerator.hpp:23
CglFlowCover::EPSILON_
double EPSILON_
Tolerance used for numerical purpose.
Definition: CglFlowCover.hpp:337
CglFlowCover::getVlbs
const CglFlowVLB * getVlbs() const
Set CglFlowVLBs,take over the ownership.
Definition: CglFlowCover.hpp:314
CGLFLOW_ROW_NOBINEQ
All variables are NOT binary and the row sense is &#39;E&#39;.
Definition: CglFlowCover.hpp:88
CglFlowRowType
CglFlowRowType
This enumerative constant describes the various row types.
Definition: CglFlowCover.hpp:66
CoinParam::operator<<
std::ostream & operator<<(std::ostream &s, const CoinParam &param)
A stream output function for a CoinParam object.
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
CGLFLOW_COL_INLMIN
The column is in L-.
Definition: CglFlowCover.hpp:52
CglFlowVLB
CglFlowVUB CglFlowVLB
Variable lower bound class, which is the same as vub.
Definition: CglFlowCover.hpp:138
CoinError
Error Class thrown by an exception.
Definition: CoinError.hpp:42
CGLFLOW_COL_CONTPOS
The column is a positive continous variable.
Definition: CglFlowCover.hpp:34
CglFlowCover::doneInitPre_
bool doneInitPre_
Indicate whether initial flow preprecessing has been done.
Definition: CglFlowCover.hpp:353
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::getVlbs
const CglFlowVLB & getVlbs(int i) const
Set CglFlowVLBs,take over the ownership.
Definition: CglFlowCover.hpp:315
CGLFLOW_ROW_VARLB
After the row is flipped to &#39;L&#39;, the row has exactlytwo variables: one is positive binary and the oth...
Definition: CglFlowCover.hpp:76
CglFlowCover::getRowTypes
const CglFlowRowType * getRowTypes() const
Set rowtypes, take over the ownership.
Definition: CglFlowCover.hpp:268
CGLFLOW_ROW_VAREQ
The row sense is &#39;E&#39;, the row has exactly two variables: one is binary and the other is a continous...
Definition: CglFlowCover.hpp:79
CglFlowCover::clone
virtual CglCutGenerator * clone() const
Clone.
CglFlowCover::getVubs
const CglFlowVUB & getVubs(int i) const
Set CglFlowVUBs,take over the ownership.
Definition: CglFlowCover.hpp:291
CglFlowCover::~CglFlowCover
virtual ~CglFlowCover()
Destructor.
CglFlowVUB
Variable upper bound class.
Definition: CglFlowCover.hpp:102
CglFlowCover::vlbs_
CglFlowVLB * vlbs_
The array of CglFlowVLBs.
Definition: CglFlowCover.hpp:357
CglFlowCover::numCols_
int numCols_
The number columns of the problem.
Definition: CglFlowCover.hpp:349
CGLFLOW_ROW_UNINTERSTED
All variables are binary.
Definition: CglFlowCover.hpp:96
CglFlowCover::setVlbs
void setVlbs(CglFlowVLB *vlbs)
Set CglFlowVLBs,take over the ownership.
Definition: CglFlowCover.hpp:317
CglFlowCover::setNumFlowCuts
static void setNumFlowCuts(int fc)
Definition: CglFlowCover.hpp:186
CglFlowVUB::getVar
int getVar() const
Definition: CglFlowCover.hpp:128
CglTreeInfo
Information about where the cut generator is invoked from.
Definition: CglTreeInfo.hpp:15
CGLFLOW_COL_INCUT
The column is in cover now.
Definition: CglFlowCover.hpp:48
CGLFLOW_COL_OUTCUT
The column is NOT in cover.
Definition: CglFlowCover.hpp:46
CGLFLOW_ROW_MIXUB
Rows can not be classfied into other types and the row sense is NOT &#39;E&#39;.
Definition: CglFlowCover.hpp:82
CglFlowCover::incNumFlowCuts
static void incNumFlowCuts(int fc=1)
Definition: CglFlowCover.hpp:187
CGLFLOW_ROW_SUMVARUB
The row has one binary and 2 or more other types of variables and the row sense is NOT &#39;E&#39;...
Definition: CglFlowCover.hpp:91
CglFlowCover::numRows_
int numRows_
The number rows of the problem.
Definition: CglFlowCover.hpp:347
CGLFLOW_COL_BINNEG
The column(variable) is a negative binary variable.
Definition: CglFlowCover.hpp:30
CglFlowCover::CglFlowCover
CglFlowCover()
Default constructor.
CglFlowCover::getRowType
CglFlowRowType getRowType(const int i) const
Set rowtypes, take over the ownership.
Definition: CglFlowCover.hpp:270
CglFlowCover::flowPreprocess
void flowPreprocess(const OsiSolverInterface &si)
Do the following tasks:
CGLFLOW_COL_CONTNEG
The column is a negative continous variable.
Definition: CglFlowCover.hpp:32