Cbc  2.9.9
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
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 
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 
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 
317 
319  const double *xlp;
320 
322  const double *rowActivity;
323 
327 
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
const CoinPackedMatrix * byCol
Pointer on matrix of coefficient ordered by columns.
Definition: CglGMI.hpp:330
bool checkDynamism(const double *cutElem, const int *cutIndex, int cutNz)
Check the dynamism.
void printOptTab(OsiSolverInterface *solver) const
Print the current simplex tableau.
void setTrackRejection(bool value)
Set/get tracking of the rejection of cutting planes.
CglGMI()
Default constructor.
OsiSolverInterface * solver
Pointer on solver. Reset by each call to generateCuts().
Definition: CglGMI.hpp:316
CglGMI & operator=(const CglGMI &rhs)
Assignment operator.
void printvecINT(const char *vecstr, const int *x, int n) const
print a vector of integers
int ncol
Number of structural variables in the current LP.
Definition: CglGMI.hpp:288
int * rstat
Current basis status: rows.
Definition: CglGMI.hpp:313
bool checkViolation(const double *cutElem, const int *cutIndex, int cutNz, double cutrhs, const double *xbar)
Cut cleaning procedures: return true if successfull, false if cut should be discarded by the caller o...
bool areEqual(double x, double y, double epsAbs=1e-12, double epsRel=1e-12)
Definition: CglGMI.hpp:83
int * cstat
Current basis status: columns.
Definition: CglGMI.hpp:310
Information about where the cut generator is invoked from.
Definition: CglTreeInfo.hpp:15
Collections of row cuts and column cuts.
Definition: OsiCuts.hpp:19
double ratiof0compl
Definition: CglGMI.hpp:335
void resetRejectionCounters()
Reset counters for cut rejection tracking; see above.
const double * rowUpper
Upper bounds for constraints.
Definition: CglGMI.hpp:300
void printvecDBL(const char *vecstr, const double *x, int n) const
print a vector of doubles: dense form
bool nearestRational(double val, double maxdelta, long maxdnom, long &numerator, long &denominator)
Compute the nearest rational number; used by scale_row_integral.
double f0
Fractionality of the cut and related quantities.
Definition: CglGMI.hpp:333
Abstract Base Class for describing an interface to a solver.
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
bool scaleCut(double *cutElem, int *cutIndex, int cutNz, double &cutRhs, int scalingType)
Scale the cutting plane in different ways; scaling_type possible values: 0 : scale to obtain integral...
void computeIsInteger()
const double * rowRhs
Righ hand side for constraints (upper bound for ranged constraints).
Definition: CglGMI.hpp:303
virtual bool needsOptimalBasis() const
Return true if needs optimal basis to do cuts (will return true)
Definition: CglGMI.hpp:77
Gomory cut generator with several cleaning procedures, used to test the numerical safety of the resul...
Definition: CglGMI.hpp:37
bool cleanCut(double *cutElem, int *cutIndex, int &cutNz, double &cutRhs, const double *xbar)
Clean the cutting plane; the cleaning procedure does several things like removing small coefficients...
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 packRow(double *row, double *rowElem, int *rowIndex, int &rowNz)
Pack a row of ncol elements.
void relaxRhs(double &rhs)
Adjust the rhs by relaxing by a small amount (relative or absolute)
void setParam(const CglGMIParam &source)
virtual CglCutGenerator * clone() const
Clone.
const CoinPackedMatrix * byRow
Pointer on matrix of coefficient ordered by rows.
Definition: CglGMI.hpp:326
double computeCutCoefficient(double rowElem, int index)
Compute the cut coefficient on a given variable.
const double * colLower
Lower bounds for structural variables.
Definition: CglGMI.hpp:291
Sparse Matrix Base Class.
bool isIntegerValue(double x, double intEpsAbs=1e-9, double intEpsRel=1e-15)
Definition: CglGMI.hpp:97
bool scaleCutIntegral(double *cutElem, int *cutIndex, int cutNz, double &cutRhs)
Scale the cutting plane in order to generate integral coefficients.
const double * rowLower
Lower bounds for constraints.
Definition: CglGMI.hpp:297
CglGMIParam getParam() const
Definition: CglGMI.hpp:114
bool checkSupport(int cutNz)
Check the support.
void unflipOrig(double &rowElem, int rowIndex, double &rowRhs)
Change the sign of the coefficients of the non basic variables at their upper bound and do the transl...
bool getTrackRejection()
This deals with Factorization and Updates.
long computeGcd(long a, long b)
Compute the greatest common divisor.
void CglGMIUnitTest(const OsiSolverInterface *siP, const std::string mpdDir)
A function that tests the methods in the CglGMI class.
const double * colUpper
Upper bounds for structural variables.
Definition: CglGMI.hpp:294
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.
void eliminateSlack(double cutElem, int cutIndex, double *cut, double &cutRhs, const double *elements, const int *rowStart, const int *indices, const int *rowLength, const double *rhs)
Use multiples of the initial inequalities to cancel out the coefficient on a slack variables...
bool isZero(double x, double epsZero=1e-20)
Definition: CglGMI.hpp:91
const double * xlp
Pointer on point to separate. Reset by each call to generateCuts().
Definition: CglGMI.hpp:319
virtual ~CglGMI()
Destructor.
bool computeCutFractionality(double varRhs, double &cutRhs)
Compute the fractionalities involved in the cut, and the cut rhs.
int getNumberGeneratedCuts()
Get total number of generated cuts since last resetRejectionCounters()
double aboveInteger(double value) const
Compute the fractional part of value, allowing for small error.
virtual std::string generateCpp(FILE *fp)
Create C++ lines to get to current state.
int nrow
Number of rows ( = number of slack variables) in the current LP.
Definition: CglGMI.hpp:285
CglGMIParam param
Object with CglGMIParam members.
Definition: CglGMI.hpp:282
int factorize(CoinFactorization &factorization, int *colBasisIndex, int *rowBasisIndex)
Recompute the simplex tableau for want of a better accuracy.
bool * isInteger
Characteristic vectors of structural integer variables or continuous variables currently fixed to int...
Definition: CglGMI.hpp:307
int getNumberRejectedCuts(RejectionType reason)
Get number of cuts rejected for given reason; see above.
void flip(double &rowElem, int rowIndex)
Change the sign of the coefficients of the non basic variables at their upper bound.
void unflipSlack(double &rowElem, int rowIndex, double &rowRhs, const double *slack_val)
const double * rowActivity
Pointer on row activity. Reset by each call to generateCuts().
Definition: CglGMI.hpp:322
bool removeSmallCoefficients(double *cutElem, int *cutIndex, int &cutNz, double &cutRhs)
Remove small coefficients and adjust the rhs accordingly.
double f0compl
Definition: CglGMI.hpp:334