Cgl 0.60.9
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
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.
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.