Cgl  0.60.3
CglFlowCover.hpp
Go to the documentation of this file.
1 // $Id: CglFlowCover.hpp 1370 2017-03-30 10:49:25Z forrest $
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 
37 };
38 
40 };
41 
63 };
64 
97 };
98 
99 //=============================================================================
100 
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 
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 
141 std::ostream& operator<<( std::ostream& os, const CglFlowVUB &v );
142 
143 //=============================================================================
144 
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  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  CglFlowCover ();
195 
198  const CglFlowCover &);
199 
201  virtual CglCutGenerator * clone() const;
202 
204  CglFlowCover &
206  const CglFlowCover& rhs);
207 
209  virtual
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 
337  double EPSILON_;
341  double INFTY_;
343  double TOLERANCE_;
347  int numRows_;
349  int numCols_;
360 };
361 
362 //#############################################################################
368 void 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.
std::ostream & operator<<(std::ostream &os, const CglFlowVUB &v)
Overloaded operator<< for printing VUB and VLB.
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.
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 CglFlowVLB & getVlbs(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.
int getMaxNumCuts() const
void setRowTypes(CglFlowRowType *rt)
Set rowtypes, take over the ownership.
void incNumFlowCuts(int fc=1)
void printVubs(std::ostream &os) const
const CglFlowRowType * getRowTypes() 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.
CglFlowCover & operator=(const CglFlowCover &rhs)
Assignment operator.
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...
int getNumFlowCuts()
virtual CglCutGenerator * clone() const
Clone.
const CglFlowVUB & getVubs(int i) 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.
const CglFlowVUB * getVubs() const
void flowPreprocess(const OsiSolverInterface &si)
Do the following tasks:
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.
const CglFlowVLB * getVlbs() const
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(const CglFlowVUB &source)
void setVal(const double v)
double upper_
The index of the associated 0-1 variable.
double getVal() const
CglFlowVUB & operator=(const CglFlowVUB &rhs)
int getVar() const
CglFlowVUB()
The Value of the associated upper bound.
Information about where the cut generator is invoked from.
Definition: CglTreeInfo.hpp:15