Cgl  0.59.10
CglGMI.hpp
Go to the documentation of this file.
1 // Last edit: 02/05/2013
2 //
3 // Name: CglGMI.hpp
4 // Author: Giacomo Nannicini
5 // Singapore University of Technology and Design, Singapore
6 // email: nannicini@sutd.edu.sg
7 // Date: 11/17/09
8 //-----------------------------------------------------------------------------
9 // Copyright (C) 2009, Giacomo Nannicini. All Rights Reserved.
10 
11 #ifndef CglGMI_H
12 #define CglGMI_H
13 
14 #include "CglCutGenerator.hpp"
15 #include "CglGMIParam.hpp"
16 #include "CoinWarmStartBasis.hpp"
17 #include "CoinFactorization.hpp"
18 
19 /* Enable tracking of rejection of cutting planes. If this is disabled,
20  the cut generator is slightly faster. If defined, it enables proper use
21  of setTrackRejection and related functions. */
22 //#define TRACK_REJECT
23 
24 /* Debug output */
25 //#define GMI_TRACE
26 
27 /* Debug output: print optimal tableau */
28 //#define GMI_TRACETAB
29 
30 /* Print reason for cut rejection, whenever a cut is discarded */
31 //#define GMI_TRACE_CLEAN
32 
37 class CglGMI : public CglCutGenerator {
38 
39  friend void CglGMIUnitTest(const OsiSolverInterface * siP,
40  const std::string mpdDir);
41 public:
42 
50  };
51 
73  virtual void generateCuts(const OsiSolverInterface & si, OsiCuts & cs,
74  const CglTreeInfo info = CglTreeInfo());
75 
77  virtual bool needsOptimalBasis() const { return true; }
79 
82  // Function for checking equality with user tolerance
83  inline bool areEqual(double x, double y,
84  double epsAbs = 1e-12,
85  double epsRel = 1e-12) {
86  return (fabs((x) - (y)) <=
87  std::max(epsAbs, epsRel * std::max(fabs(x), fabs(y))));
88  }
89 
90  // Function for checking is a number is zero
91  inline bool isZero(double x, double epsZero = 1e-20) {
92  return (fabs(x) <= epsZero);
93  }
94 
95 
96  // Function for checking if a number is integer
97  inline bool isIntegerValue(double x,
98  double intEpsAbs = 1e-9,
99  double intEpsRel = 1e-15) {
100  return (fabs((x) - floor((x)+0.5)) <=
101  std::max(intEpsAbs, intEpsRel * fabs(x)));
102  }
103 
104 
106 
107 
110 
111  // Set the parameters to the values of the given CglGMIParam object.
112  void setParam(const CglGMIParam &source);
113  // Return the CglGMIParam object of the generator.
114  inline CglGMIParam getParam() const {return param;}
115  inline CglGMIParam & getParam() {return param;}
116 
117  // Compute entries of is_integer.
118  void computeIsInteger();
119 
121  void printOptTab(OsiSolverInterface *solver) const;
122 
126  void setTrackRejection(bool value);
127  bool getTrackRejection();
128 
131 
133  void resetRejectionCounters();
134 
137 
139 
142  CglGMI();
144 
146  CglGMI(const CglGMIParam &param);
147 
149  CglGMI(const CglGMI &);
150 
152  virtual CglCutGenerator * clone() const;
153 
155  CglGMI & operator=(const CglGMI& rhs);
156 
158  virtual ~CglGMI();
160  virtual std::string generateCpp( FILE * fp);
161 
163 
164 private:
165 
166  // Private member methods
167 
171 
172  // Method generating the cuts after all CglGMI members are properly set.
173  void generateCuts(OsiCuts & cs);
174 
176  inline double aboveInteger(double value) const;
177 
180  inline bool computeCutFractionality(double varRhs, double& cutRhs);
181 
183  inline double computeCutCoefficient(double rowElem, int index);
184 
187  inline void eliminateSlack(double cutElem, int cutIndex, double* cut,
188  double& cutRhs, const double *elements,
189  const int *rowStart, const int *indices,
190  const int *rowLength, const double *rhs);
191 
194  inline void flip(double& rowElem, int rowIndex);
195 
200  inline void unflipOrig(double& rowElem, int rowIndex, double& rowRhs);
201  inline void unflipSlack(double& rowElem, int rowIndex, double& rowRhs,
202  const double* slack_val);
203 
205  inline void packRow(double* row, double* rowElem, int* rowIndex,
206  int& rowNz);
207 
213  bool cleanCut(double* cutElem, int* cutIndex, int& cutNz,
214  double& cutRhs, const double* xbar);
215 
218 
220  bool checkViolation(const double* cutElem, const int* cutIndex,
221  int cutNz, double cutrhs, const double* xbar);
222 
224  bool checkDynamism(const double* cutElem, const int* cutIndex,
225  int cutNz);
226 
228  bool checkSupport(int cutNz);
229 
231  bool removeSmallCoefficients(double* cutElem, int* cutIndex,
232  int& cutNz, double& cutRhs);
233 
235  void relaxRhs(double& rhs);
236 
242  bool scaleCut(double* cutElem, int* cutIndex, int cutNz,
243  double& cutRhs, int scalingType);
244 
246  bool scaleCutIntegral(double* cutElem, int* cutIndex, int cutNz,
247  double& cutRhs);
248 
250  bool nearestRational(double val, double maxdelta, long maxdnom,
251  long& numerator, long& denominator);
252 
254  long computeGcd(long a, long b);
255 
257  void printvecINT(const char *vecstr, const int *x, int n) const;
259  void printvecDBL(const char *vecstr, const double *x, int n) const;
261  void printvecDBL(const char *vecstr, const double *elem, const int * index,
262  int nz) const;
263 
268  int factorize(CoinFactorization & factorization,
269  int* colBasisIndex, int* rowBasisIndex);
270 
271 
273 
274 
275  // Private member data
276 
280 
282  CglGMIParam param;
283 
285  int nrow;
286 
288  int ncol;
289 
291  const double *colLower;
292 
294  const double *colUpper;
295 
297  const double *rowLower;
298 
300  const double *rowUpper;
301 
303  const double *rowRhs;
304 
307  bool *isInteger;
308 
310  int *cstat;
311 
313  int *rstat;
314 
316  OsiSolverInterface *solver;
317 
319  const double *xlp;
320 
322  const double *rowActivity;
323 
326  const CoinPackedMatrix *byRow;
327 
330  const CoinPackedMatrix *byCol;
331 
333  double f0;
334  double f0compl;
335  double ratiof0compl;
336 
337 #if defined(TRACK_REJECT) || defined (TRACK_REJECT_SIMPLE)
338  bool trackRejection;
341  int fracFail;
342  int dynFail;
343  int violFail;
344  int suppFail;
345  int smallCoeffFail;
346  int scaleFail;
348  int numGeneratedCuts;
349 #endif
350 
352 };
353 
354 //#############################################################################
360 void CglGMIUnitTest(const OsiSolverInterface * siP,
361  const std::string mpdDir );
362 
363 
364 #endif
void setTrackRejection(bool value)
Set/get tracking of the rejection of cutting planes.
virtual bool needsOptimalBasis() const
Return true if needs optimal basis to do cuts (will return true)
Definition: CglGMI.hpp:77
CglGMI()
Default constructor.
CglGMI & operator=(const CglGMI &rhs)
Assignment operator.
CglGMIParam getParam() const
Definition: CglGMI.hpp:114
bool areEqual(double x, double y, double epsAbs=1e-12, double epsRel=1e-12)
Definition: CglGMI.hpp:83
Information about where the cut generator is invoked from.
Definition: CglTreeInfo.hpp:15
void resetRejectionCounters()
Reset counters for cut rejection tracking; see above.
Class collecting parameters for the GMI cut generator.
Definition: CglGMIParam.hpp:52
RejectionType
Public enum: all possible reasons for cut rejection.
Definition: CglGMI.hpp:44
void printOptTab(OsiSolverInterface *solver) const
Print the current simplex tableau.
void computeIsInteger()
Gomory cut generator with several cleaning procedures, used to test the numerical safety of the resul...
Definition: CglGMI.hpp:37
Cut Generator Base Class.
friend void CglGMIUnitTest(const OsiSolverInterface *siP, const std::string mpdDir)
A function that tests the methods in the CglGMI class.
CglGMIParam & getParam()
Definition: CglGMI.hpp:115
void setParam(const CglGMIParam &source)
bool isIntegerValue(double x, double intEpsAbs=1e-9, double intEpsRel=1e-15)
Definition: CglGMI.hpp:97
bool getTrackRejection()
virtual void generateCuts(const OsiSolverInterface &si, OsiCuts &cs, const CglTreeInfo info=CglTreeInfo())
Generate Gomory Mixed-Integer cuts for the model of the solver interface si.
bool isZero(double x, double epsZero=1e-20)
Definition: CglGMI.hpp:91
virtual ~CglGMI()
Destructor.
int getNumberGeneratedCuts()
Get total number of generated cuts since last resetRejectionCounters()
virtual std::string generateCpp(FILE *fp)
Create C++ lines to get to current state.
int getNumberRejectedCuts(RejectionType reason)
Get number of cuts rejected for given reason; see above.
virtual CglCutGenerator * clone() const
Clone.