coin-Cgl
CglFlowCover.hpp
Go to the documentation of this file.
1 // $Id: CglFlowCover.hpp 741 2009-05-27 20:09:51Z rlh $
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 Common 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) const;
164 
171  virtual void generateCuts(const OsiSolverInterface & si, OsiCuts & cs,
172  const CglTreeInfo info = CglTreeInfo()) const;
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 ) const;
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  int 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_;
345  mutable bool firstProcess_;
347  mutable int numRows_;
349  mutable int numCols_;
351  static int numFlowCuts_;
353  mutable bool doneInitPre_;
355  mutable CglFlowVUB* vubs_;
357  mutable CglFlowVLB* vlbs_;
360 };
361 
362 //#############################################################################
368 void CglFlowCoverUnitTest(const OsiSolverInterface * siP,
369  const std::string mpdDir );
370 
371 #endif