CglKnapsackCover Class Reference

Knapsack Cover Cut Generator Class. More...

#include <CglKnapsackCover.hpp>

Inheritance diagram for CglKnapsackCover:

[legend]

Collaboration diagram for CglKnapsackCover:

[legend]

List of all members.

Public Member Functions
void	setTestedRowIndices (int num, const int *ind)
	A method to set which rows should be tested for knapsack covers.
Generate Cuts

virtual void	generateCuts (const OsiSolverInterface &si, OsiCuts &cs, const CglTreeInfo info=CglTreeInfo()) const
	Generate knapsack cover cuts for the model of the solver interface, si.
Constructors and destructors

	CglKnapsackCover ()
	Default constructor.
	CglKnapsackCover (const CglKnapsackCover &)
	Copy constructor.
virtual CglCutGenerator *	clone () const
	Clone.
CglKnapsackCover &	operator= (const CglKnapsackCover &rhs)
	Assignment operator.
virtual	~CglKnapsackCover ()
	Destructor.
virtual std::string	generateCpp (FILE *fp)
	Create C++ lines to get to current state.
Sets and gets

void	setMaxInKnapsack (int value)
	Set limit on number in knapsack.
int	getMaxInKnapsack () const
	get limit on number in knapsack
void	switchOffExpensive ()
	Switch off expensive cuts.
void	switchOnExpensive ()
	Switch on expensive cuts.
Private Member Functions
Private methods

int	deriveAKnapsack (const OsiSolverInterface &si, OsiCuts &cs, CoinPackedVector &krow, bool treatAsLRow, double &b, int complement, double xstar, int rowIndex, int numberElements, const int index, const double element) const
	deriveAKnapsack returns 1 if it is able to derive a (canonical) knapsack inequality in binary variables of the form ax<=b from the rowIndex-th row in the model, returns 0 otherwise.
int	deriveAKnapsack (const OsiSolverInterface &si, OsiCuts &cs, CoinPackedVector &krow, double &b, int complement, double xstar, int rowIndex, const CoinPackedVectorBase &matrixRow) const
	deriveAKnapsack returns 1 if it is able to derive a (canonical) knapsack inequality in binary variables of the form ax<=b from the rowIndex-th row in the model, returns 0 otherwise.
int	findExactMostViolatedMinCover (int nCols, int row, CoinPackedVector &krow, double b, double *xstar, CoinPackedVector &cover, CoinPackedVector &remainder) const
	Find a violated minimal cover from a canonical form knapsack inequality by solving the -most- violated cover problem and postprocess to ensure minimality.
int	findLPMostViolatedMinCover (int nCols, int row, CoinPackedVector &krow, double &b, double *xstar, CoinPackedVector &cover, CoinPackedVector &remainder) const
	Find the most violate minimum cover by solving the lp-relaxation of the most-violate-min-cover problem.
int	findGreedyCover (int row, CoinPackedVector &krow, double &b, double *xstar, CoinPackedVector &cover, CoinPackedVector &remainder) const
	find a minimum cover by a simple greedy approach
int	liftCoverCut (double &b, int nRowElem, CoinPackedVector &cover, CoinPackedVector &remainder, CoinPackedVector &cut) const
	lift the cover inequality
int	liftAndUncomplementAndAdd (double rowub, CoinPackedVector &krow, double &b, int *complement, int row, CoinPackedVector &cover, CoinPackedVector &remainder, OsiCuts &cs) const
	sequence-independent lift and uncomplement and add the resulting cut to the cut set
void	seqLiftAndUncomplementAndAdd (int nCols, double xstar, int complement, int row, int nRowElem, double &b, CoinPackedVector &cover, CoinPackedVector &remainder, OsiCuts &cs) const
	sequence-dependent lift, uncomplement and add the resulting cut to the cut set
void	liftUpDownAndUncomplementAndAdd (int nCols, double xstar, int complement, int row, int nRowElem, double &b, CoinPackedVector &fracCover, CoinPackedVector &atOne, CoinPackedVector &remainder, OsiCuts &cs) const
	sequence-dependent lift binary variables either up or down, uncomplement and add to the cut set
int	findPseudoJohnAndEllisCover (int row, CoinPackedVector &krow, double &b, double *xstar, CoinPackedVector &cover, CoinPackedVector &remainder) const
	find a cover using a variation of the logic found in OSL (w/o SOS)
int	findJohnAndEllisCover (int row, CoinPackedVector &krow, double &b, double *xstar, CoinPackedVector &fracCover, CoinPackedVector &atOnes, CoinPackedVector &remainder) const
	find a cover using the basic logic found in OSL (w/o SOS)
int	exactSolveKnapsack (int n, double c, double const pp, double const ww, double &z, int *x) const
	A C-style implementation of the Horowitz-Sahni exact solution procedure for solving knapsack problem.
Private Attributes
Private member data

double	epsilon_
	epsilon
double	epsilon2_
	Tolerance to use for violation - bigger than epsilon_.
double	onetol_
	1-epsilon
int	maxInKnapsack_
	Maximum in knapsack.
int	numRowsToCheck_
	which rows to look at.
int *	rowsToCheck_
	epsilon
bool	expensiveCuts_
	exactKnapsack can be expensive - this switches off some
Friends
void	CglKnapsackCoverUnitTest (const OsiSolverInterface *siP, const std::string mpdDir)
	A function that tests the methods in the CglKnapsackCover class.

Detailed Description

Knapsack Cover Cut Generator Class.

Definition at line 11 of file CglKnapsackCover.hpp.

Constructor & Destructor Documentation

CglKnapsackCover::CglKnapsackCover ( )

Default constructor.

CglKnapsackCover::CglKnapsackCover ( const CglKnapsackCover & )

Copy constructor.

virtual CglKnapsackCover::~CglKnapsackCover ( ) [virtual]

Destructor.

Member Function Documentation

void CglKnapsackCover::setTestedRowIndices	(	int	num,
		const int *	ind
	)

A method to set which rows should be tested for knapsack covers.

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

Generate knapsack cover cuts for the model of the solver interface, si.

Insert the generated cuts into OsiCut, cs.

Implements CglCutGenerator.

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

Clone.

Implements CglCutGenerator.

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

Assignment operator.

Reimplemented from CglCutGenerator.

virtual std::string CglKnapsackCover::generateCpp ( FILE * fp ) [virtual]

Create C++ lines to get to current state.

Reimplemented from CglCutGenerator.

void CglKnapsackCover::setMaxInKnapsack ( int value ) [inline]

Set limit on number in knapsack.

Definition at line 56 of file CglKnapsackCover.hpp.

int CglKnapsackCover::getMaxInKnapsack ( ) const [inline]

get limit on number in knapsack

Definition at line 59 of file CglKnapsackCover.hpp.

void CglKnapsackCover::switchOffExpensive ( ) [inline]

Switch off expensive cuts.

Definition at line 62 of file CglKnapsackCover.hpp.

void CglKnapsackCover::switchOnExpensive ( ) [inline]

Switch on expensive cuts.

Definition at line 65 of file CglKnapsackCover.hpp.

int CglKnapsackCover::deriveAKnapsack	(	const OsiSolverInterface &	si,
		OsiCuts &	cs,
		CoinPackedVector &	krow,
		bool	treatAsLRow,
		double &	b,
		int *	complement,
		double *	xstar,
		int	rowIndex,
		int	numberElements,
		const int *	index,
		const double *	element
	)			const `[private]`

deriveAKnapsack returns 1 if it is able to derive a (canonical) knapsack inequality in binary variables of the form ax<=b from the rowIndex-th row in the model, returns 0 otherwise.

int CglKnapsackCover::deriveAKnapsack	(	const OsiSolverInterface &	si,
		OsiCuts &	cs,
		CoinPackedVector &	krow,
		double &	b,
		int *	complement,
		double *	xstar,
		int	rowIndex,
		const CoinPackedVectorBase &	matrixRow
	)			const `[private]`

deriveAKnapsack returns 1 if it is able to derive a (canonical) knapsack inequality in binary variables of the form ax<=b from the rowIndex-th row in the model, returns 0 otherwise.

int CglKnapsackCover::findExactMostViolatedMinCover	(	int	nCols,
		int	row,
		CoinPackedVector &	krow,
		double	b,
		double *	xstar,
		CoinPackedVector &	cover,
		CoinPackedVector &	remainder
	)			const `[private]`

Find a violated minimal cover from a canonical form knapsack inequality by solving the -most- violated cover problem and postprocess to ensure minimality.

int CglKnapsackCover::findLPMostViolatedMinCover	(	int	nCols,
		int	row,
		CoinPackedVector &	krow,
		double &	b,
		double *	xstar,
		CoinPackedVector &	cover,
		CoinPackedVector &	remainder
	)			const `[private]`

Find the most violate minimum cover by solving the lp-relaxation of the most-violate-min-cover problem.

int CglKnapsackCover::findGreedyCover	(	int	row,
		CoinPackedVector &	krow,
		double &	b,
		double *	xstar,
		CoinPackedVector &	cover,
		CoinPackedVector &	remainder
	)			const `[private]`

find a minimum cover by a simple greedy approach

int CglKnapsackCover::liftCoverCut	(	double &	b,
		int	nRowElem,
		CoinPackedVector &	cover,
		CoinPackedVector &	remainder,
		CoinPackedVector &	cut
	)			const `[private]`

lift the cover inequality

int CglKnapsackCover::liftAndUncomplementAndAdd	(	double	rowub,
		CoinPackedVector &	krow,
		double &	b,
		int *	complement,
		int	row,
		CoinPackedVector &	cover,
		CoinPackedVector &	remainder,
		OsiCuts &	cs
	)			const `[private]`

sequence-independent lift and uncomplement and add the resulting cut to the cut set

void CglKnapsackCover::seqLiftAndUncomplementAndAdd	(	int	nCols,
		double *	xstar,
		int *	complement,
		int	row,
		int	nRowElem,
		double &	b,
		CoinPackedVector &	cover,
		CoinPackedVector &	remainder,
		OsiCuts &	cs
	)			const `[private]`

sequence-dependent lift, uncomplement and add the resulting cut to the cut set

void CglKnapsackCover::liftUpDownAndUncomplementAndAdd	(	int	nCols,
		double *	xstar,
		int *	complement,
		int	row,
		int	nRowElem,
		double &	b,
		CoinPackedVector &	fracCover,
		CoinPackedVector &	atOne,
		CoinPackedVector &	remainder,
		OsiCuts &	cs
	)			const `[private]`

sequence-dependent lift binary variables either up or down, uncomplement and add to the cut set

int CglKnapsackCover::findPseudoJohnAndEllisCover	(	int	row,
		CoinPackedVector &	krow,
		double &	b,
		double *	xstar,
		CoinPackedVector &	cover,
		CoinPackedVector &	remainder
	)			const `[private]`

find a cover using a variation of the logic found in OSL (w/o SOS)

int CglKnapsackCover::findJohnAndEllisCover	(	int	row,
		CoinPackedVector &	krow,
		double &	b,
		double *	xstar,
		CoinPackedVector &	fracCover,
		CoinPackedVector &	atOnes,
		CoinPackedVector &	remainder
	)			const `[private]`

find a cover using the basic logic found in OSL (w/o SOS)

int CglKnapsackCover::exactSolveKnapsack	(	int	n,
		double	c,
		double const *	pp,
		double const *	ww,
		double &	z,
		int *	x
	)			const `[private]`

A C-style implementation of the Horowitz-Sahni exact solution procedure for solving knapsack problem.

(ToDo: implement the more efficient dynamic programming approach)

(Reference: Martello and Toth, Knapsack Problems, Wiley, 1990, p30.)

Friends And Related Function Documentation

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

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