Cbc  2.9.9
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
Public Types | Friends | List of all members
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:
+ Collaboration diagram for CglGMI:

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

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. More...
 
bool computeCutFractionality (double varRhs, double &cutRhs)
 Compute the fractionalities involved in the cut, and the cut rhs. More...
 
double computeCutCoefficient (double rowElem, int index)
 Compute the cut coefficient on a given variable. More...
 
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. More...
 
void flip (double &rowElem, int rowIndex)
 Change the sign of the coefficients of the non basic variables at their upper bound. More...
 
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. More...
 
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. More...
 
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. More...
 
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. More...
 
bool checkDynamism (const double *cutElem, const int *cutIndex, int cutNz)
 Check the dynamism. More...
 
bool checkSupport (int cutNz)
 Check the support. More...
 
bool removeSmallCoefficients (double *cutElem, int *cutIndex, int &cutNz, double &cutRhs)
 Remove small coefficients and adjust the rhs accordingly. More...
 
void relaxRhs (double &rhs)
 Adjust the rhs by relaxing by a small amount (relative or absolute) More...
 
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. More...
 
bool scaleCutIntegral (double *cutElem, int *cutIndex, int cutNz, double &cutRhs)
 Scale the cutting plane in order to generate integral coefficients. More...
 
bool nearestRational (double val, double maxdelta, long maxdnom, long &numerator, long &denominator)
 Compute the nearest rational number; used by scale_row_integral. More...
 
long computeGcd (long a, long b)
 Compute the greatest common divisor. More...
 
void printvecINT (const char *vecstr, const int *x, int n) const
 print a vector of integers More...
 
void printvecDBL (const char *vecstr, const double *x, int n) const
 print a vector of doubles: dense form More...
 
void printvecDBL (const char *vecstr, const double *elem, const int *index, int nz) const
 print a vector of doubles: sparse form More...
 
int factorize (CoinFactorization &factorization, int *colBasisIndex, int *rowBasisIndex)
 Recompute the simplex tableau for want of a better accuracy. More...
 

Private Attributes

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

Friends

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

Additional Inherited Members

- Public Attributes inherited from CglCutGenerator
int aggressive_
 Aggressiveness - 0 = neutral, 100 is normal root node. More...
 
bool canDoGlobalCuts_
 True if can do global cuts i.e. no general integers. More...
 

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

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
inlinevirtual

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)
CglGMIParam CglGMI::getParam ( ) const
inline

Definition at line 114 of file CglGMI.hpp.

CglGMIParam& CglGMI::getParam ( )
inline

Definition at line 115 of file CglGMI.hpp.

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

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
double CglGMI::aboveInteger ( double  value) const
inlineprivate

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

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

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 
)
inlineprivate

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 
)
inlineprivate

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

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

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

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

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 
)
inlineprivate
void CglGMI::packRow ( double *  row,
double *  rowElem,
int *  rowIndex,
int &  rowNz 
)
inlineprivate

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

Definition at line 334 of file CglGMI.hpp.

double CglGMI::ratiof0compl
private

Definition at line 335 of file CglGMI.hpp.


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