Cgl 0.59.7

- Main Page
- Related Pages
- Modules
- Namespaces
- Classes
- Files

- File List
- File Members

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