Loading...
Searching...
No Matches
CglGMI Class Reference

Gomory cut generator with several cleaning procedures, used to test the numerical safety of the resulting cuts. More...

`#include <CglGMI.hpp>`

Inheritance diagram for CglGMI:
[legend]
Collaboration diagram for CglGMI:
[legend]

## Public Types

enum | RejectionType { failureFractionality , failureDynamism , failureViolation , failureSupport , failureScale }
| Public enum: all possible reasons for cut rejection. More...

## Public Member Functions

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.
virtual bool | needsOptimalBasis () const
| Return true if needs optimal basis to do cuts (will return true).
Common Methods
bool | areEqual (double x, double y, double epsAbs=1e-12, double epsRel=1e-12)
bool | isZero (double x, double epsZero=1e-20)
bool | isIntegerValue (double x, double intEpsAbs=1e-9, double intEpsRel=1e-15)
Public Methods
void | setParam (const CglGMIParam &source)
CglGMIParam | getParam () const
CglGMIParam & | getParam ()
void | computeIsInteger ()
void | printOptTab (OsiSolverInterface *solver) const
| Print the current simplex tableau.
void | setTrackRejection (bool value)
| Set/get tracking of the rejection of cutting planes.
bool | getTrackRejection ()
int | getNumberRejectedCuts (RejectionType reason)
| Get number of cuts rejected for given reason; see above.
void | resetRejectionCounters ()
| Reset counters for cut rejection tracking; see above.
int | getNumberGeneratedCuts ()
| Get total number of generated cuts since last resetRejectionCounters().
Constructors and destructors
| CglGMI ()
| Default constructor.
| CglGMI (const CglGMIParam &param)
| Constructor with specified parameters.
| CglGMI (const CglGMI &)
| Copy constructor.
virtual CglCutGenerator * | clone () const
| Clone.
CglGMI & | operator= (const CglGMI &rhs)
| Assignment operator.
virtual | ~CglGMI ()
| Destructor.
virtual std::string | generateCpp (FILE *fp)
| Create C++ lines to get to current state.
Public Member Functions inherited from CglCutGenerator
| CglCutGenerator ()
| Default constructor.
| CglCutGenerator (const CglCutGenerator &)
| Copy constructor.
CglCutGenerator & | operator= (const CglCutGenerator &rhs)
| Assignment operator.
virtual | ~CglCutGenerator ()
| Destructor.
virtual void | refreshSolver (OsiSolverInterface *)
| This can be used to refresh any information.
int | getAggressiveness () const
| Get Aggressiveness - 0 = neutral, 100 is normal root node.
void | setAggressiveness (int value)
| Set Aggressiveness - 0 = neutral, 100 is normal root node.
void | setGlobalCuts (bool trueOrFalse)
| Set whether can do global cuts.
bool | canDoGlobalCuts () const
| Say whether can do global cuts.
virtual bool | mayGenerateRowCutsInTree () const
| Returns true if may generate Row cuts in tree (rather than root node).
virtual int | maximumLengthOfCutInTree () const
| Return maximum length of cut in tree.

## Private Member Functions

Private member methods
void | generateCuts (OsiCuts &cs)
double | aboveInteger (double value) const
| Compute the fractional part of value, allowing for small error.
bool | computeCutFractionality (double varRhs, double &cutRhs)
| Compute the fractionalities involved in the cut, and the cut rhs.
double | computeCutCoefficient (double rowElem, int index)
| Compute the cut coefficient on a given variable.
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.
void | flip (double &rowElem, int rowIndex)
| Change the sign of the coefficients of the non basic variables at their upper bound.
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 translations restoring the original bounds.
void | unflipSlack (double &rowElem, int rowIndex, double &rowRhs, const double *slack_val)
void | packRow (double *row, double *rowElem, int *rowIndex, int &rowNz)
| Pack a row of ncol elements.
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, scaling, and checks several acceptance criteria.
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 of if problems encountered.
bool | checkDynamism (const double *cutElem, const int *cutIndex, int cutNz)
| Check the dynamism.
bool | checkSupport (int cutNz)
| Check the support.
bool | removeSmallCoefficients (double *cutElem, int *cutIndex, int &cutNz, double &cutRhs)
| Remove small coefficients and adjust the rhs accordingly.
void | relaxRhs (double &rhs)
| Adjust the rhs by relaxing by a small amount (relative or absolute).
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 cut 1 : scale based on norm, to obtain cut norm equal to ncol 2 : scale to obtain largest coefficient equal to 1.
bool | scaleCutIntegral (double *cutElem, int *cutIndex, int cutNz, double &cutRhs)
| Scale the cutting plane in order to generate integral coefficients.
bool | nearestRational (double val, double maxdelta, long maxdnom, long &numerator, long &denominator)
| Compute the nearest rational number; used by scale_row_integral.
long | computeGcd (long a, long b)
| Compute the greatest common divisor.
void | printvecINT (const char *vecstr, const int *x, int n) const
| print a vector of integers
void | printvecDBL (const char *vecstr, const double *x, int n) const
| print a vector of doubles: dense form
void | printvecDBL (const char *vecstr, const double *elem, const int *index, int nz) const
| print a vector of doubles: sparse form
int | factorize (CoinFactorization &factorization, int *colBasisIndex, int *rowBasisIndex)
| Recompute the simplex tableau for want of a better accuracy.

## Private Attributes

Private member data
CglGMIParam | param
| Object with CglGMIParam members.
int | nrow
| Number of rows ( = number of slack variables) in the current LP.
int | ncol
| Number of structural variables in the current LP.
const double * | colLower
| Lower bounds for structural variables.
const double * | colUpper
| Upper bounds for structural variables.
const double * | rowLower
| Lower bounds for constraints.
const double * | rowUpper
| Upper bounds for constraints.
const double * | rowRhs
| Righ hand side for constraints (upper bound for ranged constraints).
bool * | isInteger
| Characteristic vectors of structural integer variables or continuous variables currently fixed to integer values.
int * | cstat
| Current basis status: columns.
int * | rstat
| Current basis status: rows.
OsiSolverInterface * | solver
| Pointer on solver. Reset by each call to generateCuts().
const double * | xlp
| Pointer on point to separate. Reset by each call to generateCuts().
const double * | rowActivity
| Pointer on row activity. Reset by each call to generateCuts().
const CoinPackedMatrix * | byRow
| Pointer on matrix of coefficient ordered by rows.
const CoinPackedMatrix * | byCol
| Pointer on matrix of coefficient ordered by columns.
double | f0
| Fractionality of the cut and related quantities.
double | f0compl
double | ratiof0compl

## Friends

void | CglGMIUnitTest (const OsiSolverInterface *siP, const std::string mpdDir)
| A function that tests the methods in the CglGMI class.

## Additional Inherited Members

int | aggressive_
| Aggressiveness - 0 = neutral, 100 is normal root node.
bool | canDoGlobalCuts_
| True if can do global cuts i.e. no general integers.

## Detailed Description

Gomory cut generator with several cleaning procedures, used to test the numerical safety of the resulting cuts.

Definition at line 37 of file CglGMI.hpp.

## Member Enumeration Documentation

## RejectionType

enum CglGMI::RejectionType

Public enum: all possible reasons for cut rejection.

Enumerator
failureFractionality |
failureDynamism |
failureViolation |
failureSupport |
failureScale |

Definition at line 44 of file CglGMI.hpp.

## Constructor & Destructor Documentation

## CglGMI() [1/3]

CglGMI::CglGMI | ( |  | ) |

Default constructor.

## CglGMI() [2/3]

CglGMI::CglGMI | ( | const CglGMIParam & | param | ) |

Constructor with specified parameters.

## CglGMI() [3/3]

CglGMI::CglGMI | ( | const CglGMI & |  | ) |

Copy constructor.

## ~CglGMI()

virtual CglGMI::~CglGMI | ( |  | ) |

virtual

Destructor.

## Member Function Documentation

## generateCuts() [1/2]

virtual void CglGMI::generateCuts | ( | const OsiSolverInterface & | si,
|  | OsiCuts & | cs,
|  | const CglTreeInfo | info = CglTreeInfo() )

virtual

Generate Gomory Mixed-Integer cuts for the model of the solver interface si.

Insert the generated cuts into OsiCuts cs.

Warning: This generator currently works only with the Lp solvers Clp or Cplex9.0 or higher. It requires access to the optimal tableau and optimal basis inverse and makes assumptions on the way slack variables are added by the solver. The Osi implementations for Clp and Cplex verify these assumptions.

When calling the generator, the solver interface si must contain an optimized problem and information related to the optimal basis must be available through the OsiSolverInterface methods (si->optimalBasisIsAvailable() must return 'true'). It is also essential that the integrality of structural variable i can be obtained using si->isInteger(i).

Implements CglCutGenerator.

## needsOptimalBasis()

virtual bool CglGMI::needsOptimalBasis | ( |  | ) | const

inline virtual

Return true if needs optimal basis to do cuts (will return true).

Reimplemented from CglCutGenerator.

Definition at line 77 of file CglGMI.hpp.

## areEqual()

bool CglGMI::areEqual | ( | double | x,
|  | double | y,
|  | double | epsAbs = 1e-12,
|  | double | epsRel = 1e-12 )

inline

Definition at line 83 of file CglGMI.hpp.

## isZero()

bool CglGMI::isZero | ( | double | x,
|  | double | epsZero = 1e-20 )

inline

Definition at line 91 of file CglGMI.hpp.

## isIntegerValue()

bool CglGMI::isIntegerValue | ( | double | x,
|  | double | intEpsAbs = 1e-9,
|  | double | intEpsRel = 1e-15 )

inline

Definition at line 97 of file CglGMI.hpp.

## setParam()

void CglGMI::setParam | ( | const CglGMIParam & | source | ) |

## getParam() [1/2]

CglGMIParam CglGMI::getParam | ( |  | ) | const

inline

Definition at line 114 of file CglGMI.hpp.

## getParam() [2/2]

CglGMIParam & CglGMI::getParam | ( |  | ) |

inline

Definition at line 115 of file CglGMI.hpp.

## computeIsInteger()

void CglGMI::computeIsInteger | ( |  | ) |

## printOptTab()

void CglGMI::printOptTab | ( | OsiSolverInterface * | solver | ) | const

Print the current simplex tableau.

## setTrackRejection()

void CglGMI::setTrackRejection | ( | bool | value | ) |

Set/get tracking of the rejection of cutting planes.

Note that all rejection related functions will not do anything unless the generator is compiled with the define GMI_TRACK_REJECTION

## getTrackRejection()

bool CglGMI::getTrackRejection | ( |  | ) |

## getNumberRejectedCuts()

int CglGMI::getNumberRejectedCuts | ( | RejectionType | reason | ) |

Get number of cuts rejected for given reason; see above.

## resetRejectionCounters()

void CglGMI::resetRejectionCounters | ( |  | ) |

Reset counters for cut rejection tracking; see above.

## getNumberGeneratedCuts()

int CglGMI::getNumberGeneratedCuts | ( |  | ) |

Get total number of generated cuts since last resetRejectionCounters().

## clone()

virtual CglCutGenerator * CglGMI::clone | ( |  | ) | const

virtual

Clone.

Implements CglCutGenerator.

## operator=()

CglGMI & CglGMI::operator= | ( | const CglGMI & | rhs | ) |

Assignment operator.

## generateCpp()

virtual std::string CglGMI::generateCpp | ( | FILE * | fp | ) |

virtual

Create C++ lines to get to current state.

Reimplemented from CglCutGenerator.

## generateCuts() [2/2]

void CglGMI::generateCuts | ( | OsiCuts & | cs | ) |

private

## aboveInteger()

double CglGMI::aboveInteger | ( | double | value | ) | const

inline private

Compute the fractional part of value, allowing for small error.

## computeCutFractionality()

bool CglGMI::computeCutFractionality | ( | double | varRhs,
|  | double & | cutRhs )

inline private

Compute the fractionalities involved in the cut, and the cut rhs.

Returns true if cut is accepted, false if discarded

## computeCutCoefficient()

double CglGMI::computeCutCoefficient | ( | double | rowElem,
|  | int | index )

inline private

Compute the cut coefficient on a given variable.

## eliminateSlack()

void CglGMI::eliminateSlack | ( | double | cutElem,
|  | int | cutIndex,
|  | double * | cut,
|  | double & | cutRhs,
|  | const double * | elements,
|  | const CoinBigIndex * | rowStart,
|  | const int * | indices,
|  | const int * | rowLength,
|  | const double * | rhs )

inline private

Use multiples of the initial inequalities to cancel out the coefficient on a slack variables.

## flip()

void CglGMI::flip | ( | double & | rowElem,
|  | int | rowIndex )

inline private

Change the sign of the coefficients of the non basic variables at their upper bound.

## unflipOrig()

void CglGMI::unflipOrig | ( | double & | rowElem,
|  | int | rowIndex,
|  | double & | rowRhs )

inline private

Change the sign of the coefficients of the non basic variables at their upper bound and do the translations restoring the original bounds.

Modify the right hand side accordingly. Two functions: one for original variables, one for slacks.

## unflipSlack()

void CglGMI::unflipSlack | ( | double & | rowElem,
|  | int | rowIndex,
|  | double & | rowRhs,
|  | const double * | slack_val )

inline private

## packRow()

void CglGMI::packRow | ( | double * | row,
|  | double * | rowElem,
|  | int * | rowIndex,
|  | int & | rowNz )

inline private

Pack a row of ncol elements.

## cleanCut()

bool CglGMI::cleanCut | ( | double * | cutElem,
|  | int * | cutIndex,
|  | int & | cutNz,
|  | double & | cutRhs,
|  | const double * | xbar )

private

Clean the cutting plane; the cleaning procedure does several things like removing small coefficients, scaling, and checks several acceptance criteria.

If this returns false, the cut should be discarded. There are several cleaning procedures available, that can be selected via the parameter param.setCLEANING_PROCEDURE(int value)

## checkViolation()

bool CglGMI::checkViolation | ( | const double * | cutElem,
|  | const int * | cutIndex,
|  | int | cutNz,
|  | double | cutrhs,
|  | const double * | xbar )

private

Cut cleaning procedures: return true if successfull, false if cut should be discarded by the caller of if problems encountered.

Check the violation

## checkDynamism()

bool CglGMI::checkDynamism | ( | const double * | cutElem,
|  | const int * | cutIndex,
|  | int | cutNz )

private

Check the dynamism.

## checkSupport()

bool CglGMI::checkSupport | ( | int | cutNz | ) |

private

Check the support.

## removeSmallCoefficients()

bool CglGMI::removeSmallCoefficients | ( | double * | cutElem,
|  | int * | cutIndex,
|  | int & | cutNz,
|  | double & | cutRhs )

private

Remove small coefficients and adjust the rhs accordingly.

## relaxRhs()

void CglGMI::relaxRhs | ( | double & | rhs | ) |

private

Adjust the rhs by relaxing by a small amount (relative or absolute).

## scaleCut()

bool CglGMI::scaleCut | ( | double * | cutElem,
|  | int * | cutIndex,
|  | int | cutNz,
|  | double & | cutRhs,
|  | int | scalingType )

private

Scale the cutting plane in different ways; scaling_type possible values: 0 : scale to obtain integral cut 1 : scale based on norm, to obtain cut norm equal to ncol 2 : scale to obtain largest coefficient equal to 1.

## scaleCutIntegral()

bool CglGMI::scaleCutIntegral | ( | double * | cutElem,
|  | int * | cutIndex,
|  | int | cutNz,
|  | double & | cutRhs )

private

Scale the cutting plane in order to generate integral coefficients.

## nearestRational()

bool CglGMI::nearestRational | ( | double | val,
|  | double | maxdelta,
|  | long | maxdnom,
|  | long & | numerator,
|  | long & | denominator )

private

Compute the nearest rational number; used by scale_row_integral.

## computeGcd()

long CglGMI::computeGcd | ( | long | a,
|  | long | b )

private

Compute the greatest common divisor.

## printvecINT()

void CglGMI::printvecINT | ( | const char * | vecstr,
|  | const int * | x,
|  | int | n ) const

private

print a vector of integers

## printvecDBL() [1/2]

void CglGMI::printvecDBL | ( | const char * | vecstr,
|  | const double * | x,
|  | int | n ) const

private

print a vector of doubles: dense form

## printvecDBL() [2/2]

void CglGMI::printvecDBL | ( | const char * | vecstr,
|  | const double * | elem,
|  | const int * | index,
|  | int | nz ) const

private

print a vector of doubles: sparse form

## factorize()

int CglGMI::factorize | ( | CoinFactorization & | factorization,
|  | int * | colBasisIndex,
|  | int * | rowBasisIndex )

private

Recompute the simplex tableau for want of a better accuracy.

Requires an empty CoinFactorization object to do the computations, and two empty (already allocated) arrays which will contain the basis indices on exit. Returns 0 if successfull.

## Friends And Related Symbol Documentation

## CglGMIUnitTest

void CglGMIUnitTest | ( | const OsiSolverInterface * | siP,
|  | const std::string | mpdDir )

friend

A function that tests the methods in the CglGMI class.

The only reason for it not to be a member method is that this way it doesn't have to be compiled into the library. And that's a gain, because the library should be compiled with optimization on, but this method should be compiled with debugging.

## Member Data Documentation

## param

CglGMIParam CglGMI::param

private

Object with CglGMIParam members.

Definition at line 282 of file CglGMI.hpp.

## nrow

int CglGMI::nrow

private

Number of rows ( = number of slack variables) in the current LP.

Definition at line 285 of file CglGMI.hpp.

## ncol

int CglGMI::ncol

private

Number of structural variables in the current LP.

Definition at line 288 of file CglGMI.hpp.

## colLower

const double* CglGMI::colLower

private

Lower bounds for structural variables.

Definition at line 291 of file CglGMI.hpp.

## colUpper

const double* CglGMI::colUpper

private

Upper bounds for structural variables.

Definition at line 294 of file CglGMI.hpp.

## rowLower

const double* CglGMI::rowLower

private

Lower bounds for constraints.

Definition at line 297 of file CglGMI.hpp.

## rowUpper

const double* CglGMI::rowUpper

private

Upper bounds for constraints.

Definition at line 300 of file CglGMI.hpp.

## rowRhs

const double* CglGMI::rowRhs

private

Righ hand side for constraints (upper bound for ranged constraints).

Definition at line 303 of file CglGMI.hpp.

## isInteger

bool* CglGMI::isInteger

private

Characteristic vectors of structural integer variables or continuous variables currently fixed to integer values.

Definition at line 307 of file CglGMI.hpp.

## cstat

int* CglGMI::cstat

private

Current basis status: columns.

Definition at line 310 of file CglGMI.hpp.

## rstat

int* CglGMI::rstat

private

Current basis status: rows.

Definition at line 313 of file CglGMI.hpp.

## solver

OsiSolverInterface* CglGMI::solver

private

Pointer on solver. Reset by each call to generateCuts().

Definition at line 316 of file CglGMI.hpp.

## xlp

const double* CglGMI::xlp

private

Pointer on point to separate. Reset by each call to generateCuts().

Definition at line 319 of file CglGMI.hpp.

## rowActivity

const double* CglGMI::rowActivity

private

Pointer on row activity. Reset by each call to generateCuts().

Definition at line 322 of file CglGMI.hpp.

## byRow

const CoinPackedMatrix* CglGMI::byRow

private

Pointer on matrix of coefficient ordered by rows.

Reset by each call to generateCuts().

Definition at line 326 of file CglGMI.hpp.

## byCol

const CoinPackedMatrix* CglGMI::byCol

private

Pointer on matrix of coefficient ordered by columns.

Reset by each call to generateCuts().

Definition at line 330 of file CglGMI.hpp.

## f0

double CglGMI::f0

private

Fractionality of the cut and related quantities.

Definition at line 333 of file CglGMI.hpp.

## f0compl

double CglGMI::f0compl

private

Definition at line 334 of file CglGMI.hpp.

## ratiof0compl

double CglGMI::ratiof0compl

private

Definition at line 335 of file CglGMI.hpp.

The documentation for this class was generated from the following file:

- Cgl/src/CglGMI/CglGMI.hpp