Knapsack Cover Cut Generator Class. More...

#include <CglKnapsackCover.hpp>

Inheritance diagram for CglKnapsackCover:

Collaboration diagram for CglKnapsackCover:

Classes
struct	CliqueType
	Clique type. More...

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

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

Constructors and destructors
	CglKnapsackCover ()
	Default constructor. More...

	CglKnapsackCover (const CglKnapsackCover &)
	Copy constructor. More...

virtual CglCutGenerator *	clone () const
	Clone. More...

CglKnapsackCover &	operator= (const CglKnapsackCover &rhs)
	Assignment operator. More...

virtual	~CglKnapsackCover ()
	Destructor. More...

virtual std::string	generateCpp (FILE *fp)
	Create C++ lines to get to current state. More...

virtual void	refreshSolver (OsiSolverInterface *solver)
	This can be used to refresh any information. More...

Sets and gets
void	setMaxInKnapsack (int value)
	Set limit on number in knapsack. More...

int	getMaxInKnapsack () const
	get limit on number in knapsack More...

void	switchOffExpensive ()
	Switch off expensive cuts. More...

void	switchOnExpensive ()
	Switch on expensive cuts. 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...

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 bool	needsOptimalBasis () const
	Return true if needs optimal basis to do cuts. More...

virtual int	maximumLengthOfCutInTree () const
	Return maximum length of cut in tree. More...

Private Attributes
Private member data
double	epsilon_
	epsilon More...

double	epsilon2_
	Tolerance to use for violation - bigger than epsilon_. More...

double	onetol_
	1-epsilon More...

int	maxInKnapsack_
	Maximum in knapsack. More...

int	numRowsToCheck_
	which rows to look at. More...

int *	rowsToCheck_
	epsilon More...

bool	expensiveCuts_
	exactKnapsack can be expensive - this switches off some More...

const OsiSolverInterface *	solver_
	Cliques **** TEMP so can reference from listing. More...

int	whichRow_
	epsilon More...

int *	complement_
	epsilon More...

double *	elements_
	epsilon More...

int	numberCliques_
	Number of cliques. More...

CliqueType *	cliqueType_
	epsilon More...

int *	cliqueStart_
	Start of each clique. More...

CliqueEntry *	cliqueEntry_
	Entries for clique. More...

int *	oneFixStart_
	Start of oneFixes cliques for a column in matrix or -1 if not in any clique. More...

int *	zeroFixStart_
	Start of zeroFixes cliques for a column in matrix or -1 if not in any clique. More...

int *	endFixStart_
	End of fixes for a column. More...

int *	whichClique_
	Clique numbers for one or zero fixes. More...

int	numberColumns_
	Number of columns. More...

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

Private methods
int	createCliques (OsiSolverInterface &si, int minimumSize=2, int maximumSize=100, bool extendCliques=false)
	Creates cliques for use by probing. More...

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

int	deriveAKnapsack (const OsiSolverInterface &si, OsiCuts &cs, CoinPackedVector &krow, double &b, int complement, double xstar, int rowIndex, const CoinPackedVectorBase &matrixRow)
	Creates cliques for use by probing. More...

int	findExactMostViolatedMinCover (int nCols, int row, CoinPackedVector &krow, double b, double *xstar, CoinPackedVector &cover, CoinPackedVector &remainder)
	Find a violated minimal cover from a canonical form knapsack inequality by solving the -most- violated cover problem and postprocess to ensure minimality More...

int	findLPMostViolatedMinCover (int nCols, int row, CoinPackedVector &krow, double &b, double *xstar, CoinPackedVector &cover, CoinPackedVector &remainder)
	Find the most violate minimum cover by solving the lp-relaxation of the most-violate-min-cover problem. More...

int	findGreedyCover (int row, CoinPackedVector &krow, double &b, double *xstar, CoinPackedVector &cover, CoinPackedVector &remainder)
	find a minimum cover by a simple greedy approach More...

int	liftCoverCut (double &b, int nRowElem, CoinPackedVector &cover, CoinPackedVector &remainder, CoinPackedVector &cut)
	lift the cover inequality More...

int	liftAndUncomplementAndAdd (double rowub, CoinPackedVector &krow, double &b, int *complement, int row, CoinPackedVector &cover, CoinPackedVector &remainder, OsiCuts &cs)
	sequence-independent lift and uncomplement and add the resulting cut to the cut set More...

void	seqLiftAndUncomplementAndAdd (int nCols, double xstar, int complement, int row, int nRowElem, double &b, CoinPackedVector &cover, CoinPackedVector &remainder, OsiCuts &cs)
	sequence-dependent lift, uncomplement and add the resulting cut to the cut set More...

void	liftUpDownAndUncomplementAndAdd (int nCols, double xstar, int complement, int row, int nRowElem, double &b, CoinPackedVector &fracCover, CoinPackedVector &atOne, CoinPackedVector &remainder, OsiCuts &cs)
	sequence-dependent lift binary variables either up or down, uncomplement and add to the cut set More...

int	findPseudoJohnAndEllisCover (int row, CoinPackedVector &krow, double &b, double *xstar, CoinPackedVector &cover, CoinPackedVector &remainder)
	find a cover using a variation of the logic found in OSL (w/o SOS) More...

int	findJohnAndEllisCover (int row, CoinPackedVector &krow, double &b, double *xstar, CoinPackedVector &fracCover, CoinPackedVector &atOnes, CoinPackedVector &remainder)
	find a cover using the basic logic found in OSL (w/o SOS) More...

int	exactSolveKnapsack (int n, double c, double const pp, double const ww, double &z, int *x)
	A C-style implementation of the Horowitz-Sahni exact solution procedure for solving knapsack problem. More...

int	gubifyCut (CoinPackedVector &cut)
	For testing gub stuff. More...

void	deleteCliques ()
	Delete all clique information. 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

Knapsack Cover Cut Generator Class.

Definition at line 15 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()`
	)

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.

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

virtual

Create C++ lines to get to current state.

Reimplemented from CglCutGenerator.

virtual void CglKnapsackCover::refreshSolver ( OsiSolverInterface * solver )

virtual

This can be used to refresh any information.

Reimplemented from CglCutGenerator.

void CglKnapsackCover::setMaxInKnapsack ( int value )

inline

Set limit on number in knapsack.

Definition at line 62 of file CglKnapsackCover.hpp.

int CglKnapsackCover::getMaxInKnapsack ( ) const

inline

get limit on number in knapsack

Definition at line 65 of file CglKnapsackCover.hpp.

void CglKnapsackCover::switchOffExpensive ( )

inline

Switch off expensive cuts.

Definition at line 68 of file CglKnapsackCover.hpp.

void CglKnapsackCover::switchOnExpensive ( )

inline

Switch on expensive cuts.

Definition at line 71 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
	)

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
	)

private

Creates cliques for use by probing.

Only cliques >= minimumSize and < maximumSize created Can also try and extend cliques as a result of probing (root node). Returns number of cliques found.

int CglKnapsackCover::findExactMostViolatedMinCover	(	int	nCols,
		int	row,
		CoinPackedVector &	krow,
		double	b,
		double *	xstar,
		CoinPackedVector &	cover,
		CoinPackedVector &	remainder
	)

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
	)

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
	)

private

find a minimum cover by a simple greedy approach

int CglKnapsackCover::liftCoverCut	(	double &	b,
		int	nRowElem,
		CoinPackedVector &	cover,
		CoinPackedVector &	remainder,
		CoinPackedVector &	cut
	)

private

lift the cover inequality

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

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
	)

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
	)

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
	)

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
	)

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
	)

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

int CglKnapsackCover::gubifyCut ( CoinPackedVector & cut )

private

For testing gub stuff.

int CglKnapsackCover::createCliques	(	OsiSolverInterface &	si,
		int	minimumSize = `2`,
		int	maximumSize = `100`,
		bool	extendCliques = `false`
	)

Creates cliques for use by probing.

Only cliques >= minimumSize and < maximumSize created Can also try and extend cliques as a result of probing (root node). Returns number of cliques found.

void CglKnapsackCover::deleteCliques ( )

private

Delete all clique information.

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.

Member Data Documentation

double CglKnapsackCover::epsilon_

private

epsilon

Definition at line 249 of file CglKnapsackCover.hpp.

double CglKnapsackCover::epsilon2_

private

Tolerance to use for violation - bigger than epsilon_.

Definition at line 251 of file CglKnapsackCover.hpp.

double CglKnapsackCover::onetol_

private

1-epsilon

Definition at line 253 of file CglKnapsackCover.hpp.

int CglKnapsackCover::maxInKnapsack_

private

Maximum in knapsack.

Definition at line 255 of file CglKnapsackCover.hpp.

int CglKnapsackCover::numRowsToCheck_

private

which rows to look at.

If specified, only these rows will be considered for generating knapsack covers. Otherwise all rows will be tried

Definition at line 258 of file CglKnapsackCover.hpp.

int* CglKnapsackCover::rowsToCheck_

private

epsilon

Definition at line 259 of file CglKnapsackCover.hpp.

bool CglKnapsackCover::expensiveCuts_

private

exactKnapsack can be expensive - this switches off some

Definition at line 261 of file CglKnapsackCover.hpp.

const OsiSolverInterface* CglKnapsackCover::solver_

private

Cliques **** TEMP so can reference from listing.

Definition at line 264 of file CglKnapsackCover.hpp.

int CglKnapsackCover::whichRow_

private

epsilon

Definition at line 265 of file CglKnapsackCover.hpp.

int* CglKnapsackCover::complement_

private

epsilon

Definition at line 266 of file CglKnapsackCover.hpp.

double* CglKnapsackCover::elements_

private

epsilon

Definition at line 267 of file CglKnapsackCover.hpp.

int CglKnapsackCover::numberCliques_

private

Number of cliques.

Definition at line 269 of file CglKnapsackCover.hpp.

CliqueType* CglKnapsackCover::cliqueType_

private

epsilon

Definition at line 274 of file CglKnapsackCover.hpp.

int* CglKnapsackCover::cliqueStart_

private

Start of each clique.

Definition at line 276 of file CglKnapsackCover.hpp.

CliqueEntry* CglKnapsackCover::cliqueEntry_

private

Entries for clique.

Definition at line 278 of file CglKnapsackCover.hpp.

int* CglKnapsackCover::oneFixStart_

private

Start of oneFixes cliques for a column in matrix or -1 if not in any clique.

Definition at line 281 of file CglKnapsackCover.hpp.

int* CglKnapsackCover::zeroFixStart_

private

Start of zeroFixes cliques for a column in matrix or -1 if not in any clique.

Definition at line 284 of file CglKnapsackCover.hpp.

int* CglKnapsackCover::endFixStart_

private

End of fixes for a column.

Definition at line 286 of file CglKnapsackCover.hpp.

int* CglKnapsackCover::whichClique_

private

Clique numbers for one or zero fixes.

Definition at line 288 of file CglKnapsackCover.hpp.

int CglKnapsackCover::numberColumns_

private

Number of columns.

Definition at line 290 of file CglKnapsackCover.hpp.

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

/home/coin/svn-release/Blis-0.94.3/Cgl/src/CglKnapsackCover/CglKnapsackCover.hpp

Classes

Public Member Functions

Private Attributes

Friends

Private methods

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation

Friends And Related Function Documentation

Member Data Documentation