Cgl 0.60.9
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_;
107
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
167
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]; }
272
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 }
285
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 }
309
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 }
328
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.
CglCutGenerator()
Default constructor.
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.