Cgl 0.60.8
Loading...
Searching...
No Matches
CglFlowCover.hpp
Go to the documentation of this file.
1// $Id$
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
38
41
64
98
99//=============================================================================
100
103{
104protected:
106 double upper_;
108public:
109 CglFlowVUB() : varInd_(-1), upper_(-1) {}
110
111 CglFlowVUB(const CglFlowVUB& source) {
112 varInd_= source.varInd_;
113 upper_ = source.upper_;
114 }
115
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
139
141std::ostream& operator<<( std::ostream& os, const CglFlowVUB &v );
142
143//=============================================================================
144
149 friend void CglFlowCoverUnitTest(const OsiSolverInterface * siP,
150 const std::string mpdDir );
151
152public:
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 inline int getNumFlowCuts() { return numFlowCuts_; }
186 inline void setNumFlowCuts(int fc) { numFlowCuts_ = fc; }
187 inline void incNumFlowCuts(int fc = 1) { numFlowCuts_ += fc; }
189
190 //-------------------------------------------------------------------------
193
195
198 const CglFlowCover &);
199
201 virtual CglCutGenerator * clone() const;
202
206 const CglFlowCover& rhs);
207
209 virtual
212 virtual std::string generateCpp( FILE * fp);
214
215private:
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
330private:
331 //------------------------------------------------------------------------
332 // Private member data
333
337 double EPSILON_;
341 double INFTY_;
360};
361
362//#############################################################################
368void CglFlowCoverUnitTest(const OsiSolverInterface * siP,
369 const std::string mpdDir );
370
371#endif
CglFlowColType
This enumerative constant describes the various col types.
@ CGLFLOW_COL_BINPOS
The column is a positive binary variable.
@ CGLFLOW_COL_BINNEG
The column(variable) is a negative binary variable.
@ CGLFLOW_COL_CONTPOS
The column is a positive continous variable.
@ CGLFLOW_COL_CONTNEG
The column is a negative continous variable.
CglFlowColStatus
void CglFlowCoverUnitTest(const OsiSolverInterface *siP, const std::string mpdDir)
A function that tests the methods in the CglFlowCover class.
CglFlowRowType
This enumerative constant describes the various row types.
@ CGLFLOW_ROW_NOBINUB
All variables are NOT binary and the row sense is NOT 'E'.
@ CGLFLOW_ROW_UNINTERSTED
All variables are binary.
@ CGLFLOW_ROW_SUMVARUB
The row has one binary and 2 or more other types of variables and the row sense is NOT 'E'.
@ CGLFLOW_ROW_VARUB
After the row is flipped to 'L', the row has exactly two variables: one is negative binary and the ot...
@ CGLFLOW_ROW_VARLB
After the row is flipped to 'L', the row has exactlytwo variables: one is positive binary and the oth...
@ CGLFLOW_ROW_MIXEQ
Rows can not be classfied into other types and the row sense is 'E'.
@ CGLFLOW_ROW_VAREQ
The row sense is 'E', the row has exactly two variables: one is binary and the other is a continous,...
@ CGLFLOW_ROW_UNDEFINED
The row type of this row is NOT defined yet.
@ CGLFLOW_ROW_SUMVAREQ
The row has one binary and 2 or more other types of variables and the row sense is 'E'.
@ CGLFLOW_ROW_MIXUB
Rows can not be classfied into other types and the row sense is NOT 'E'.
@ CGLFLOW_ROW_NOBINEQ
All variables are NOT binary and the row sense is 'E'.
CglFlowColCut
This enumerative constant describes the various stati of vars in a cut or not.
@ CGLFLOW_COL_SECONDARY
The column is a secondary candidate.
@ CGLFLOW_COL_INLMINDONE
The column is decided to be in L-.
@ CGLFLOW_COL_INCUTDONE
The column is decided to be in cover.
@ CGLFLOW_COL_INLMIN
The column is in L-.
@ CGLFLOW_COL_INLMINMIN
The column is in L–.
@ CGLFLOW_COL_PRIME
This enumerative constant describes the various stati of vars in determining the cover.
@ CGLFLOW_COL_INCUT
The column is in cover now.
@ CGLFLOW_COL_OUTCUT
The column is NOT in cover.
std::ostream & operator<<(std::ostream &os, const CglFlowVUB &v)
Overloaded operator<< for printing VUB and VLB.
CglFlowVUB CglFlowVLB
Variable lower bound class, which is the same as vub.
Cut Generator Base Class.
Lifed Simple Generalized Flow Cover Cut Generator Class.
void setVlbs(const CglFlowVLB &vlb, int i)
int numFlowCuts_
The number flow cuts found.
bool firstProcess_
First time preprocessing.
const CglFlowVUB & getVubs(int i) const
double TOLERANCE_
If violation of a cut is greater that this number, the cut is useful.
void flipRow(int rowLen, double *coef, double &rhs) const
Transform a row from ">=" to "<=", and vice versa.
void setMaxNumCuts(int mc)
void setVlbs(CglFlowVLB *vlbs)
Set CglFlowVLBs,take over the ownership.
void setVubs(CglFlowVUB *vubs)
Set CglFlowVUBs,take over the ownership.
CglFlowRowType determineOneRowType(const OsiSolverInterface &si, int rowLen, int *ind, double *coef, char sen, double rhs) const
Determine the type of a given row.
void flipRow(int rowLen, double *coef, char &sen, double &rhs) const
Transform a row from ">=" to "<=", and vice versa.
CglFlowCover()
Default constructor.
int numRows_
The number rows of the problem.
const CglFlowVLB & getVlbs(int i) const
const CglFlowVLB * getVlbs() const
int getMaxNumCuts() const
const CglFlowRowType * getRowTypes() const
void setRowTypes(CglFlowRowType *rt)
Set rowtypes, take over the ownership.
void incNumFlowCuts(int fc=1)
CglFlowCover & operator=(const CglFlowCover &rhs)
Assignment operator.
void printVubs(std::ostream &os) const
int maxNumCuts_
The maximum number of flow cuts to be generated.
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.
void setNumFlowCuts(int fc)
double EPSILON_
Tolerance used for numerical purpose.
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...
const CglFlowVUB * getVubs() const
int numCols_
The number columns of the problem.
CglFlowRowType getRowType(const int i) const
virtual ~CglFlowCover()
Destructor.
virtual std::string generateCpp(FILE *fp)
Create C++ lines to get to current state.
void setRowTypes(const CglFlowRowType rt, const int i)
CglFlowVUB * vubs_
The array of CglFlowVUBs.
void setVubs(const CglFlowVUB &vub, int i)
friend void CglFlowCoverUnitTest(const OsiSolverInterface *siP, const std::string mpdDir)
A function that tests the methods in the CglFlowCover class.
CglFlowVLB * vlbs_
The array of CglFlowVLBs.
void flowPreprocess(const OsiSolverInterface &si)
Do the following tasks:
virtual CglCutGenerator * clone() const
Clone.
void liftMinus(double &movement, int t, int r, double z, double dPrimePrime, double lambda, double ml, double *M, double *rho) const
Lift functions.
CglFlowRowType * rowTypes_
CglFlowRowType of the rows in model.
CglFlowCover(const CglFlowCover &)
Copy constructor.
double INFTY_
Very large number.
bool liftPlus(double &alpha, double &beta, int r, double m_j, double lambda, double y_j, double x_j, double dPrimePrime, double *M) const
bool doneInitPre_
Indicate whether initial flow preprecessing has been done.
int UNDEFINED_
The variable upper bound of a flow is not indentified yet.
Variable upper bound class.
void setVar(const int v)
CglFlowVUB & operator=(const CglFlowVUB &rhs)
CglFlowVUB(const CglFlowVUB &source)
void setVal(const double v)
double upper_
The index of the associated 0-1 variable.
double getVal() const
int getVar() const
CglFlowVUB()
The Value of the associated upper bound.
Information about where the cut generator is invoked from.