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)
	Print the current simplex tableau. More...

CglGMIParam	getParam () const
	Print the current simplex tableau. More...

CglGMIParam &	getParam ()
	Print the current simplex tableau. More...

void	computeIsInteger ()
	Print the current simplex tableau. More...

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 ()
	Print the current simplex tableau. More...

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 CglCutGenerator *	clone () const
	Clone. More...

CglGMI &	operator= (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...

CglCutGenerator &	operator= (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)
	Compute the fractional part of value, allowing for small error. More...

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)
	Compute the fractional part of value, allowing for small error. More...

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

OsiSolverInterface *	solver
	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 CoinPackedMatrix *	byRow
	Pointer on matrix of coefficient ordered by rows. More...

const CoinPackedMatrix *	byCol
	Pointer on matrix of coefficient ordered by columns. More...

double	f0
	Fractionality of the cut and related quantities. More...

double	f0compl
	Object with CglGMIParam members. More...

double	ratiof0compl
	Object with CglGMIParam members. More...

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

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

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 )