# 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]

List of all members.

## 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)
| Print the current simplex tableau.
CglGMIParam | getParam () const
| Print the current simplex tableau.
CglGMIParam & | getParam ()
| Print the current simplex tableau.
void | computeIsInteger ()
| Print the current simplex tableau.
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 ()
| Print the current simplex tableau.
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.
## Private Member Functions
Private member methods
void | generateCuts (OsiCuts &cs)
| Compute the fractional part of value, allowing for small error.
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 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.
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)
| Compute the fractional part of value, allowing for small error.
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
| Object with CglGMIParam members.
double | ratiof0compl
| Object with CglGMIParam members.
## Friends
void | CglGMIUnitTest (const OsiSolverInterface *siP, const std::string mpdDir)
| A function that tests the methods in the CglGMI class.

## 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

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::CglGMI | ( |  | ) |

Default constructor.

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

Constructor with specified parameters.

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

Copy constructor.

virtual CglGMI::~CglGMI | ( |  | ) | `[virtual]`

Destructor.

## Member Function Documentation

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.

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.

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

Definition at line 83 of file CglGMI.hpp.

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

Definition at line 91 of file CglGMI.hpp.

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

Definition at line 97 of file CglGMI.hpp.

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

Print the current simplex tableau.

CglGMIParam CglGMI::getParam | ( |  | ) | const`[inline]`

Print the current simplex tableau.

Definition at line 114 of file CglGMI.hpp.

CglGMIParam& CglGMI::getParam | ( |  | ) | `[inline]`

Print the current simplex tableau.

Definition at line 115 of file CglGMI.hpp.

void CglGMI::computeIsInteger | ( |  | ) |

Print the current simplex tableau.

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

Print the current simplex tableau.

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

bool CglGMI::getTrackRejection | ( |  | ) |

Print the current simplex tableau.

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

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

void CglGMI::resetRejectionCounters | ( |  | ) |

Reset counters for cut rejection tracking; see above.

int CglGMI::getNumberGeneratedCuts | ( |  | ) |

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

virtual CglCutGenerator* CglGMI::clone | ( |  | ) | const`[virtual]`

Clone.

Implements CglCutGenerator.

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

Assignment operator.

Reimplemented from CglCutGenerator.

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

Create C++ lines to get to current state.

Reimplemented from CglCutGenerator.

void CglGMI::generateCuts | ( | OsiCuts & | cs | ) | `[private]`

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

double CglGMI::aboveInteger | ( | double | value | ) | const`[inline, private]`

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

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

double CglGMI::computeCutCoefficient | ( | double | rowElem,
|  | int | index |
| ) |  |  | `[inline, private]`

Compute the cut coefficient on a given variable.

void CglGMI::eliminateSlack | ( | double | cutElem,
|  | int | cutIndex,
|  | double * | cut,
|  | double & | cutRhs,
|  | const double * | elements,
|  | const int * | 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.

void CglGMI::flip | ( | double & | rowElem,
|  | int | rowIndex |
| ) |  |  | `[inline, private]`

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

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.

void CglGMI::unflipSlack | ( | double & | rowElem,
|  | int | rowIndex,
|  | double & | rowRhs,
|  | const double * | slack_val |
| ) |  |  | `[inline, private]`

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

void CglGMI::packRow | ( | double * | row,
|  | double * | rowElem,
|  | int * | rowIndex,
|  | int & | rowNz |
| ) |  |  | `[inline, private]`

Pack a row of ncol elements.

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)

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

bool CglGMI::checkDynamism | ( | const double * | cutElem,
|  | const int * | cutIndex,
|  | int | cutNz |
| ) |  |  | `[private]`

Check the dynamism.

bool CglGMI::checkSupport | ( | int | cutNz | ) | `[private]`

Check the support.

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

Remove small coefficients and adjust the rhs accordingly.

void CglGMI::relaxRhs | ( | double & | rhs | ) | `[private]`

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

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.

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

Scale the cutting plane in order to generate integral coefficients.

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

Compute the nearest rational number; used by scale_row_integral.

long CglGMI::computeGcd | ( | long | a,
|  | long | b |
| ) |  |  | `[private]`

Compute the greatest common divisor.

void CglGMI::printvecINT | ( | const char * | vecstr,
|  | const int * | x,
|  | int | n |
| ) |  |  | const`[private]`

print a vector of integers

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

print a vector of doubles: dense form

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

print a vector of doubles: sparse form

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 Function Documentation

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

CglGMIParam CglGMI::param`[private]`

Object with CglGMIParam members.

Definition at line 282 of file CglGMI.hpp.

int CglGMI::nrow`[private]`

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

Definition at line 285 of file CglGMI.hpp.

int CglGMI::ncol`[private]`

Number of structural variables in the current LP.

Definition at line 288 of file CglGMI.hpp.

const double* CglGMI::colLower`[private]`

Lower bounds for structural variables.

Definition at line 291 of file CglGMI.hpp.

const double* CglGMI::colUpper`[private]`

Upper bounds for structural variables.

Definition at line 294 of file CglGMI.hpp.

const double* CglGMI::rowLower`[private]`

Lower bounds for constraints.

Definition at line 297 of file CglGMI.hpp.

const double* CglGMI::rowUpper`[private]`

Upper bounds for constraints.

Definition at line 300 of file CglGMI.hpp.

const double* CglGMI::rowRhs`[private]`

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

Definition at line 303 of file CglGMI.hpp.

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.

int* CglGMI::cstat`[private]`

Current basis status: columns.

Definition at line 310 of file CglGMI.hpp.

int* CglGMI::rstat`[private]`

Current basis status: rows.

Definition at line 313 of file CglGMI.hpp.

OsiSolverInterface* CglGMI::solver`[private]`

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

Definition at line 316 of file CglGMI.hpp.

const double* CglGMI::xlp`[private]`

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

Definition at line 319 of file CglGMI.hpp.

const double* CglGMI::rowActivity`[private]`

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

Definition at line 322 of file CglGMI.hpp.

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.

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.

double CglGMI::f0`[private]`

Fractionality of the cut and related quantities.

Definition at line 333 of file CglGMI.hpp.

double CglGMI::f0compl`[private]`

Object with CglGMIParam members.

Definition at line 334 of file CglGMI.hpp.

double CglGMI::ratiof0compl`[private]`

Object with CglGMIParam members.

Definition at line 335 of file CglGMI.hpp.

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

- /home/coin/svn-release/Alps-1.5.2/Cgl/src/CglGMI/CglGMI.hpp