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