CglRedSplit Class Reference

Gomory Reduce-and-Split Cut Generator Class; See method generateCuts(). More...

#include <CglRedSplit.hpp>

Inheritance diagram for CglRedSplit:

[legend]

Collaboration diagram for CglRedSplit:

[legend]

List of all members.

Public Member Functions
generateCuts

virtual void	generateCuts (const OsiSolverInterface &si, OsiCuts &cs, const CglTreeInfo info=CglTreeInfo())
	Generate Reduce-and-Split Mixed Integer Gomory cuts for the model of the solver interface si.
virtual void	generateCuts (const OsiSolverInterface &si, OsiCuts &cs, const CglTreeInfo info=CglTreeInfo()) const
	For compatibility with CglCutGenerator (const method).
virtual bool	needsOptimalBasis () const
	Return true if needs optimal basis to do cuts (will return true).
Public Methods

void	setParam (const CglRedSplitParam &source)
	Set given_optsol to the given optimal solution given_sol.
CglRedSplitParam	getParam () const
	Set given_optsol to the given optimal solution given_sol.
void	compute_is_lub ()
	Set given_optsol to the given optimal solution given_sol.
void	compute_is_integer ()
	Set given_optsol to the given optimal solution given_sol.
void	set_given_optsol (const double *given_sol, const int card_sol)
	Set given_optsol to the given optimal solution given_sol.
void	print () const
	Print some of the data members.
void	printOptTab (OsiSolverInterface *solver) const
	Print the current simplex tableau.
Public Methods (soon to be obsolete)

void	setLimit (int limit)
	Set limit, the maximum number of non zero coefficients in generated cut; Default: 50.
int	getLimit () const
	Get value of limit.
void	setAway (double value)
	Set away, the minimum distance from being integer used for selecting rows for cut generation; all rows whose pivot variable should be integer but is more than away from integrality will be selected; Default: 0.05.
double	getAway () const
	Get value of away.
void	setLUB (double value)
	Set the value of LUB, value considered large for the absolute value of a lower or upper bound on a variable; Default: 1000.
double	getLUB () const
	Get the value of LUB.
void	setEPS (double value)
	Set the value of EPS, epsilon for double computations; Default: 1e-7.
double	getEPS () const
	Get the value of EPS.
void	setEPS_COEFF (double value)
	Set the value of EPS_COEFF, epsilon for values of coefficients; Default: 1e-8.
double	getEPS_COEFF () const
	Get the value of EPS_COEFF.
void	setEPS_COEFF_LUB (double value)
	Set the value of EPS_COEFF_LUB, epsilon for values of coefficients for variables with absolute value of lower or upper bound larger than LUB; Default: 1e-13.
double	getEPS_COEFF_LUB () const
	Get the value of EPS_COEFF_LUB.
void	setEPS_RELAX (double value)
	Set the value of EPS_RELAX, value used for relaxing the right hand side of each generated cut; Default: 1e-8.
double	getEPS_RELAX () const
	Get the value of EPS_RELAX.
void	setNormIsZero (double value)
	Set the value of normIsZero, the threshold for considering a norm to be 0; Default: 1e-5.
double	getNormIsZero () const
	Get the value of normIsZero.
void	setMinReduc (double value)
	Set the value of minReduc, threshold for relative norm improvement for performing a reduction; Default: 0.05.
double	getMinReduc () const
	Get the value of minReduc.
void	setMaxTab (double value)
	Set the maximum allowed value for (mTab * mTab * max(mTab, nTab)) where mTab is the number of rows used in the combinations and nTab is the number of continuous non basic variables.
double	getMaxTab () const
	Get the value of maxTab.
Constructors and destructors

	CglRedSplit ()
	Default constructor.
	CglRedSplit (const CglRedSplitParam &RS_param)
	Constructor with specified parameters.
	CglRedSplit (const CglRedSplit &)
	Copy constructor.
virtual CglCutGenerator *	clone () const
	Clone.
CglRedSplit &	operator= (const CglRedSplit &rhs)
	Assignment operator.
virtual	~CglRedSplit ()
	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	rs_above_integer (double value)
	Compute the fractional part of value, allowing for small error.
void	update_pi_mat (int r1, int r2, int step)
	Perform row r1 of pi := row r1 of pi - step * row r2 of pi.
void	update_redTab (int r1, int r2, int step)
	Perform row r1 of tab := row r1 of tab - step * row r2 of tab.
void	find_step (int r1, int r2, int step, double reduc, double *norm)
	Find optimal integer step for changing row r1 by adding to it a multiple of another row r2.
int	test_pair (int r1, int r2, double *norm)
	Test if an ordered pair of rows yields a reduction.
void	reduce_contNonBasicTab ()
	Reduce rows of contNonBasicTab.
void	generate_row (int index_row, double *row)
	Generate a row of the current LP tableau.
int	generate_cgcut (double row, double rhs)
	Generate a mixed integer Chvatal-Gomory cut, when all non basic variables are non negative and at their lower bound.
int	generate_cgcut_2 (int basic_ind, double row, double rhs)
	Generate a mixed integer Chvatal-Gomory cut, when all non basic variables are non negative and at their lower bound (different formula).
void	eliminate_slacks (double row, const double elements, const int start, const int indices, const int rowLength, const double rhs, double *rowrhs)
	Use multiples of the initial inequalities to cancel out the coefficients of the slack variables.
void	flip (double *row)
	Change the sign of the coefficients of the continuous non basic variables at their upper bound.
void	unflip (double row, double rowrhs, double *slack_val)
	Change the sign of the coefficients of the continuous non basic variables at their upper bound and do the translations restoring the original bounds.
*double	row_scale_factor (double *row)
	Return the scale factor for the row.
int	generate_packed_row (const double xlp, double row, int rowind, double rowelem, int *card_row, double &rhs)
	Generate the packed cut from the row representation.
void	check_optsol (const int calling_place, const double xlp, const double slack_val, const int do_flip)
	Check that the generated cuts do not cut a given optimal solution.
void	check_optsol (const int calling_place, const double xlp, const double slack_val, const double *ck_row, const double ck_rhs, const int cut_number, const int do_flip)
	Check that the generated cuts do not cut a given optimal solution.
bool	rs_are_different_vectors (const int vect1, const int vect2, const int dim)
	Compute the fractional part of value, allowing for small error.
bool	rs_are_different_vectors (const double vect1, const double vect2, const int dim)
	Compute the fractional part of value, allowing for small error.
bool	rs_are_different_matrices (const CoinPackedMatrix mat1, const CoinPackedMatrix mat2, const int nmaj, const int nmin)
	Compute the fractional part of value, allowing for small error.
Private Attributes
Private member data

CglRedSplitParam	param
	Object with CglRedSplitParam 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).
int	card_intBasicVar_frac
	Number of integer basic structural variables that are fractional in the current lp solution (at least param.away_ from being integer).
int	card_intNonBasicVar
	Number of integer non basic structural variables in the current lp solution.
int	card_contNonBasicVar
	Number of continuous non basic variables (structural or slack) in the current lp solution.
int	card_nonBasicAtUpper
	Number of non basic variables (structural or slack) at their upper bound in the current lp solution.
int	card_nonBasicAtLower
	Number of non basic variables (structural or slack) at their lower bound in the current lp solution.
int *	cv_intBasicVar_frac
	Characteristic vector for integer basic structural variables with non integer value in the current lp solution.
int *	intBasicVar_frac
	List of integer structural basic variables (in order of pivot in selected rows for cut generation).
int *	intNonBasicVar
	List of integer structural non basic variables.
int *	contNonBasicVar
	List of continuous non basic variables (structural or slack).
int *	nonBasicAtUpper
	List of non basic variables (structural or slack) at their upper bound.
int *	nonBasicAtLower
	List of non basic variables (structural or slack) at their lower bound.
int	mTab
	Number of rows in the reduced tableau (= card_intBasicVar_frac).
int	nTab
	Number of columns in the reduced tableau (= card_contNonBasicVar).
int **	pi_mat
	Tableau of multipliers used to alter the rows used in generation.
double **	contNonBasicTab
	Current tableau for continuous non basic variables (structural or slack).
double **	intNonBasicTab
	Current tableau for integer non basic structural variables.
double *	rhsTab
	Right hand side of the tableau.
const double *	given_optsol
	Given optimal solution that should not be cut; only for debug.
int	card_given_optsol
	Number of entries in given_optsol.
int *	is_integer
	Characteristic vectors of structural integer variables or continuous variables currently fixed to integer values.
int *	low_is_lub
	Characteristic vector of the structural variables whose lower bound in absolute value is larger than LUB.
int *	up_is_lub
	Characteristic vector of the structural variables whose upper bound in absolute value is larger than LUB.
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 char *	colType
	Pointer on column type. Reset by each call to generateCuts().
const CoinPackedMatrix *	byRow
	Pointer on matrix of coefficient ordered by rows.
Friends
void	CglRedSplitUnitTest (const OsiSolverInterface *siP, const std::string mpdDir)
	A function that tests the methods in the CglRedSplit class.

Detailed Description

Gomory Reduce-and-Split Cut Generator Class; See method generateCuts().

Based on the paper by K. Anderson, G. Cornuejols, Yanjun Li, "Reduce-and-Split Cuts: Improving the Performance of Mixed Integer Gomory Cuts", Management Science 51 (2005).

Definition at line 23 of file CglRedSplit.hpp.

Constructor & Destructor Documentation

CglRedSplit::CglRedSplit ( )

Default constructor.

CglRedSplit::CglRedSplit ( const CglRedSplitParam & RS_param )

Constructor with specified parameters.

CglRedSplit::CglRedSplit ( const CglRedSplit & )

Copy constructor.

virtual CglRedSplit::~CglRedSplit ( ) [virtual]

Destructor.

Member Function Documentation

virtual void CglRedSplit::generateCuts	(	const OsiSolverInterface &	si,
		OsiCuts &	cs,
		const CglTreeInfo	info = `CglTreeInfo()`
	)			`[virtual]`

Generate Reduce-and-Split Mixed Integer Gomory 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).

Reduce-and-Split cuts are variants of Gomory cuts: Starting from the current optimal tableau, linear combinations of the rows of the current optimal simplex tableau are used for generating Gomory cuts. The choice of the linear combinations is driven by the objective of reducing the coefficients of the non basic continuous variables in the resulting row. Note that this generator might not be able to generate cuts for some solutions violating integrality constraints.

virtual void CglRedSplit::generateCuts	(	const OsiSolverInterface &	si,
		OsiCuts &	cs,
		const CglTreeInfo	info = `CglTreeInfo()`
	)			const `[virtual]`

For compatibility with CglCutGenerator (const method).

Implements CglCutGenerator.

virtual bool CglRedSplit::needsOptimalBasis ( ) const [virtual]

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

Reimplemented from CglCutGenerator.

void CglRedSplit::setParam ( const CglRedSplitParam & source )