CglOddHole Class Reference

Odd Hole Cut Generator Class. More...

#include <CglOddHole.hpp>

Inheritance diagram for CglOddHole:

[legend]

Collaboration diagram for CglOddHole:

[legend]

List of all members.

Public Member Functions
Generate Cuts

virtual void	generateCuts (const OsiSolverInterface &si, OsiCuts &cs, const CglTreeInfo info=CglTreeInfo()) const
	Generate odd hole cuts for the model of the solver interface, si.
Create Row List

void	createRowList (const OsiSolverInterface &si, const int *possible=NULL)
	Create a list of rows which might yield cuts this is to speed up process The possible parameter is a list to cut down search.
void	createRowList (int numberRows, const int *whichRow)
	This version passes in a list - 1 marks possible.
Create Clique List

void	createCliqueList (int numberCliques, const int cliqueStart, const int cliqueMember)
	Create a list of extra row cliques which may not be in matrix At present these are classical cliques.
Number Possibilities

int	numberPossible ()
	Returns how many rows might give odd hole cuts.
Gets and Sets

double	getMinimumViolation () const
	Minimum violation.
void	setMinimumViolation (double value)
	Minimum violation.
double	getMinimumViolationPer () const
	Minimum violation per entry.
void	setMinimumViolationPer (double value)
	Minimum violation.
int	getMaximumEntries () const
	Maximum number of entries in a cut.
void	setMaximumEntries (int value)
	Minimum violation.
Constructors and destructors

	CglOddHole ()
	Default constructor.
	CglOddHole (const CglOddHole &)
	Copy constructor.
virtual CglCutGenerator *	clone () const
	Clone.
CglOddHole &	operator= (const CglOddHole &rhs)
	Assignment operator.
virtual	~CglOddHole ()
	Destructor.
virtual void	refreshSolver (OsiSolverInterface *solver)
	This can be used to refresh any inforamtion.
Private Member Functions
Private methods

void	generateCuts (const OsiRowCutDebugger debugger, const CoinPackedMatrix &rowCopy, const double solution, const double dj, OsiCuts &cs, const int suitableRow, const int *fixedColumn, const CglTreeInfo info, bool packed)
	Generate cuts from matrix copy and solution If packed true then <=1 rows, otherwise >=1 rows.
Private Attributes
Private member data

int *	suitableRows_
	list of suitableRows
int *	startClique_
	start of each clique
int *	member_
	clique members
double	epsilon_
	epsilon
double	onetol_
	1-epsilon
double	minimumViolation_
	Minimum violation.
double	minimumViolationPer_
	Minimum violation per entry.
int	maximumEntries_
	Maximum number of entries in a cut.
int	numberRows_
	number of rows when suitability tested
int	numberCliques_
	number of cliques
Friends
void	CglOddHoleUnitTest (const OsiSolverInterface *siP, const std::string mpdDir)
	A function that tests the methods in the CglOddHole class.

Detailed Description

Odd Hole Cut Generator Class.

Definition at line 11 of file CglOddHole.hpp.

Constructor & Destructor Documentation

CglOddHole::CglOddHole ( )

Default constructor.

CglOddHole::CglOddHole ( const CglOddHole & )

Copy constructor.

virtual CglOddHole::~CglOddHole ( ) [virtual]

Destructor.

Member Function Documentation

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

Generate odd hole cuts for the model of the solver interface, si.

This looks at all rows of type sum x(i) <= 1 (or == 1) (x 0-1) and sees if there is an odd cycle cut. See Grotschel, Lovasz and Schrijver (1988) for method. This is then lifted by using the corresponding Chvatal cut i.e. Take all rows in cycle and add them together. RHS will be odd so weaken all odd coefficients so 1.0 goes to 0.0 etc - then constraint is sum even(j)*x(j) <= odd which can be replaced by sum (even(j)/2)*x(j) <= (odd-1.0)/2. A similar cut can be generated for sum x(i) >= 1.

Insert the generated cuts into OsiCut, cs.

This is only done for rows with unsatisfied 0-1 variables. If there are many of these it will be slow. Improvements would do a randomized subset and also speed up shortest path algorithm used.

Implements CglCutGenerator.

void CglOddHole::createRowList	(	const OsiSolverInterface &	si,
		const int *	possible = `NULL`
	)

Create a list of rows which might yield cuts this is to speed up process The possible parameter is a list to cut down search.

void CglOddHole::createRowList	(	int	numberRows,
		const int *	whichRow
	)

This version passes in a list - 1 marks possible.

void CglOddHole::createCliqueList	(	int	numberCliques,
		const int *	cliqueStart,
		const int *	cliqueMember
	)

Create a list of extra row cliques which may not be in matrix At present these are classical cliques.

int CglOddHole::numberPossible ( )

Returns how many rows might give odd hole cuts.

double CglOddHole::getMinimumViolation ( ) const

Minimum violation.

void CglOddHole::setMinimumViolation ( double value )

Minimum violation.

double CglOddHole::getMinimumViolationPer ( ) const

Minimum violation per entry.

void CglOddHole::setMinimumViolationPer ( double value )

Minimum violation.

int CglOddHole::getMaximumEntries ( ) const

Maximum number of entries in a cut.

void CglOddHole::setMaximumEntries ( int value )

Minimum violation.

virtual CglCutGenerator* CglOddHole::clone ( ) const [virtual]

Clone.

Implements CglCutGenerator.

CglOddHole& CglOddHole::operator= ( const CglOddHole & rhs )

Assignment operator.

Reimplemented from CglCutGenerator.

virtual void CglOddHole::refreshSolver ( OsiSolverInterface * solver ) [virtual]

This can be used to refresh any inforamtion.

Reimplemented from CglCutGenerator.

void CglOddHole::generateCuts	(	const OsiRowCutDebugger *	debugger,
		const CoinPackedMatrix &	rowCopy,
		const double *	solution,
		const double *	dj,
		OsiCuts &	cs,
		const int *	suitableRow,
		const int *	fixedColumn,
		const CglTreeInfo	info,
		bool	packed
	)			`[private]`

Generate cuts from matrix copy and solution If packed true then <=1 rows, otherwise >=1 rows.

Friends And Related Function Documentation

void CglOddHoleUnitTest	(	const OsiSolverInterface *	siP,
		const std::string	mpdDir
	)			`[friend]`

A function that tests the methods in the CglOddHole 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.