CglProbing Class Reference

Probing Cut Generator Class. More...

#include <CglProbing.hpp>

Inheritance diagram for CglProbing:

[legend]

Collaboration diagram for CglProbing:

[legend]

List of all members.

Classes
struct	cliqueEntry
	Entries for clique. More...
struct	cliqueType
	Clique type. More...
struct	disaggregation_struct_tag
	Disaggregation cuts and for building cliques. More...
struct	disaggregationAction
	Only useful type of disaggregation is most normal For now just done for 0-1 variables Can be used for building cliques. More...
Public Member Functions
Generate Cuts

virtual void	generateCuts (const OsiSolverInterface &si, OsiCuts &cs, const CglTreeInfo info=CglTreeInfo()) const
	Generate probing/disaggregation cuts for the model of the solver interface, si.
int	generateCutsAndModify (const OsiSolverInterface &si, OsiCuts &cs, CglTreeInfo *info)
	Generate probing/disaggregation cuts for the model of the solver interface, si.
snapshot etc

int	snapshot (const OsiSolverInterface &si, char *possible=NULL, bool withObjective=true)
	Create a copy of matrix which is to be used this is to speed up process and to give global cuts Can give an array with 1 set to select, 0 to ignore column bounds are tightened If array given then values of 1 will be set to 0 if redundant.
void	deleteSnapshot ()
	Deletes snapshot.
int	createCliques (OsiSolverInterface &si, int minimumSize=2, int maximumSize=100, bool extendCliques=false)
	Creates cliques for use by probing.
void	deleteCliques ()
	Delete all clique information.
Get tighter column bounds

const double *	tightLower () const
	Lower.
const double *	tightUpper () const
	Upper.
const char *	tightenBounds () const
	Array which says tighten continuous.
Get possible freed up row bounds - only valid after mode==3

const double *	relaxedRowLower () const
	Lower.
const double *	relaxedRowUpper () const
	Upper.
Change mode

void	setMode (int mode)
	Set.
int	getMode () const
	Get.
Change maxima

void	setMaxPass (int value)
	Set maximum number of passes per node.
int	getMaxPass () const
	Get maximum number of passes per node.
void	setLogLevel (int value)
	Set log level - 0 none, 1 - a bit, 2 - more details.
int	getLogLevel () const
	Get log level.
void	setMaxProbe (int value)
	Set maximum number of unsatisfied variables to look at.
int	getMaxProbe () const
	Get maximum number of unsatisfied variables to look at.
void	setMaxLook (int value)
	Set maximum number of variables to look at in one probe.
int	getMaxLook () const
	Get maximum number of variables to look at in one probe.
void	setMaxElements (int value)
	Set maximum number of elements in row for it to be considered.
int	getMaxElements () const
	Get maximum number of elements in row for it to be considered.
void	setMaxPassRoot (int value)
	Set maximum number of passes per node (root node).
int	getMaxPassRoot () const
	Get maximum number of passes per node (root node).
void	setMaxProbeRoot (int value)
	Set maximum number of unsatisfied variables to look at (root node).
int	getMaxProbeRoot () const
	Get maximum number of unsatisfied variables to look at (root node).
void	setMaxLookRoot (int value)
	Set maximum number of variables to look at in one probe (root node).
int	getMaxLookRoot () const
	Get maximum number of variables to look at in one probe (root node).
void	setMaxElementsRoot (int value)
	Set maximum number of elements in row for it to be considered (root node).
int	getMaxElementsRoot () const
	Get maximum number of elements in row for it to be considered (root node).
virtual bool	mayGenerateRowCutsInTree () const
	Returns true if may generate Row cuts in tree (rather than root node).
Get information back from probing

int	numberThisTime () const
	Number looked at this time.
const int *	lookedAt () const
	Which ones looked at this time.
Stop or restart row cuts (otherwise just fixing from probing)

void	setRowCuts (int type)
	Set 0 no cuts, 1 just disaggregation type, 2 coefficient ( 3 both).
int	rowCuts () const
	Get.
Whether use objective as constraint

void	setUsingObjective (int yesNo)
	Set 0 don't 1 do -1 don't even think about it.
int	getUsingObjective () const
	Get.
Mark which continuous variables are to be tightened

void	tightenThese (const OsiSolverInterface &solver, int number, const int *which)
	Mark variables to be tightened.
Constructors and destructors

	CglProbing ()
	Default constructor.
	CglProbing (const CglProbing &)
	Copy constructor.
virtual CglCutGenerator *	clone () const
	Clone.
CglProbing &	operator= (const CglProbing &rhs)
	Assignment operator.
virtual	~CglProbing ()
	Destructor.
virtual void	refreshSolver (OsiSolverInterface *solver)
	This can be used to refresh any inforamtion.
virtual std::string	generateCpp (FILE *fp)
	Create C++ lines to get to current state.
Private Member Functions
probe

int	probe (const OsiSolverInterface &si, const OsiRowCutDebugger debugger, OsiCuts &cs, double colLower, double colUpper, CoinPackedMatrix rowCopy, CoinPackedMatrix columnCopy, double rowLower, double rowUpper, char intVar, double minR, double maxR, int markR, CglTreeInfo info) const
	Does probing and adding cuts (without cliques and mode_!=0).
int	probeCliques (const OsiSolverInterface &si, const OsiRowCutDebugger debugger, OsiCuts &cs, double colLower, double colUpper, CoinPackedMatrix rowCopy, CoinPackedMatrix columnCopy, double rowLower, double rowUpper, char intVar, double minR, double maxR, int markR, CglTreeInfo info) const
	Does probing and adding cuts (with cliques).
int	probeSlacks (const OsiSolverInterface &si, const OsiRowCutDebugger debugger, OsiCuts &cs, double colLower, double colUpper, CoinPackedMatrix rowCopy, CoinPackedMatrix columnCopy, double rowLower, double rowUpper, char intVar, double minR, double maxR, int markR, CglTreeInfo info) const
	Does probing and adding cuts for clique slacks.
int	gutsOfGenerateCuts (const OsiSolverInterface &si, OsiCuts &cs, double rowLower, double rowUpper, double colLower, double colUpper, CglTreeInfo *info) const
	Does most of work of generateCuts Returns number of infeasibilities.
void	setupRowCliqueInformation (const OsiSolverInterface &si)
	Sets up clique information for each row.
int	tighten (double colLower, double colUpper, const int column, const double rowElements, const CoinBigIndex rowStart, const int rowLength, double rowLower, double rowUpper, int nRows, int nCols, char *intVar, int maxpass, double tolerance) const
	This tightens column bounds (and can declare infeasibility) It may also declare rows to be redundant.
void	tighten2 (double colLower, double colUpper, const int column, const double rowElements, const CoinBigIndex rowStart, const int rowLength, double rowLower, double rowUpper, double minR, double maxR, int *markR, int nRows, int nCols) const
	This just sets minima and maxima on rows.
Friends
struct	CglProbing::disaggregation_struct_tag
void	CglProbingUnitTest (const OsiSolverInterface *siP, const std::string mpdDir)
	A function that tests the methods in the CglProbing class.
Private member data

typedef struct CglProbing::disaggregation_struct_tag	disaggregation
	Disaggregation cuts and for building cliques.
CoinPackedMatrix *	rowCopy_
	Row copy (only if snapshot).
CoinPackedMatrix *	columnCopy_
	Column copy (only if snapshot).
double *	rowLower_
	Lower bounds on rows.
double *	rowUpper_
	Upper bounds on rows.
double *	colLower_
	Lower bounds on columns.
double *	colUpper_
	Upper bounds on columns.
int	numberRows_
	Number of rows in snapshot (or when cliqueRow stuff computed).
int	numberColumns_
	Number of columns in problem ( must == current).
double	primalTolerance_
	Tolerance to see if infeasible.
int	mode_
	Mode - 0 lazy using snapshot, 1 just unsatisfied, 2 all.
int	rowCuts_
	Row cuts flag 0 no cuts, 1 just disaggregation type, 2 coefficient ( 3 both), 4 just column cuts -n as +n but just fixes variables unless at root.
int	maxPass_
	Maximum number of passes to do in probing.
int	logLevel_
	Log level - 0 none, 1 - a bit, 2 - more details.
int	maxProbe_
	Maximum number of unsatisfied variables to probe.
int	maxStack_
	Maximum number of variables to look at in one probe.
int	maxElements_
	Maximum number of elements in row for scan.
int	maxPassRoot_
	Maximum number of passes to do in probing at root.
int	maxProbeRoot_
	Maximum number of unsatisfied variables to probe at root.
int	maxStackRoot_
	Maximum number of variables to look at in one probe at root.
int	maxElementsRoot_
	Maximum number of elements in row for scan at root.
int	usingObjective_
	Whether to include objective as constraint.
int	numberIntegers_
	Number of integer variables.
int	number01Integers_
	Number of 0-1 integer variables.
int	numberThisTime_
	Number looked at this time.
int *	lookedAt_
	Which ones looked at this time.
disaggregation *	cutVector_
	Disaggregation cuts and for building cliques.
int	numberCliques_
	Cliques Number of cliques.
cliqueType *	cliqueType_
	Disaggregation cuts and for building cliques.
int *	cliqueStart_
	Start of each clique.
cliqueEntry *	cliqueEntry_
	Disaggregation cuts and for building cliques.
int *	oneFixStart_
	Start of oneFixes cliques for a column in matrix or -1 if not in any clique.
int *	zeroFixStart_
	Start of zeroFixes cliques for a column in matrix or -1 if not in any clique.
int *	endFixStart_
	End of fixes for a column.
int *	whichClique_
	Clique numbers for one or zero fixes.
cliqueEntry *	cliqueRow_
	For each column with nonzero in row copy this gives a clique "number".
int *	cliqueRowStart_
	cliqueRow_ starts for each row
char *	tightenBounds_
	If not null and [i] !=0 then also tighten even if continuous.

Detailed Description

Probing Cut Generator Class.

Definition at line 11 of file CglProbing.hpp.

Member Typedef Documentation

typedef struct CglProbing::disaggregation_struct_tag CglProbing::disaggregation [private]

Disaggregation cuts and for building cliques.

Constructor & Destructor Documentation

CglProbing::CglProbing ( )

Default constructor.

CglProbing::CglProbing ( const CglProbing & )

Copy constructor.

virtual CglProbing::~CglProbing ( ) [virtual]

Destructor.

Member Function Documentation

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

Generate probing/disaggregation cuts for the model of the solver interface, si.

This is a simplification of probing ideas put into OSL about ten years ago. The only known documentation is a copy of a talk handout - we think Robin Lougee-Heimer has a copy!

For selected integer variables (e.g. unsatisfied ones) the effect of setting them up or down is investigated. Setting a variable up may in turn set other variables (continuous as well as integer). There are various possible results:

1) It is shown that problem is infeasible (this may also be because objective function or reduced costs show worse than best solution). If the other way is feasible we can generate a column cut (and continue probing), if not feasible we can say problem infeasible.

2) If both ways are feasible, it can happen that x to 0 implies y to 1 and x to 1 implies y to 1 (again a column cut). More common is that x to 0 implies y to 1 and x to 1 implies y to 0 so we could substitute for y which might lead later to more powerful cuts. This is not done in this code as there is no mechanism for returning information.

3) When x to 1 a constraint went slack by c. We can tighten the constraint ax + .... <= b (where a may be zero) to (a+c)x + .... <= b. If this cut is violated then it is generated.

4) Similarly we can generate implied disaggregation cuts

Note - differences to cuts in OSL.

a) OSL had structures intended to make this faster. b) The "chaining" in 2) was done c) Row cuts modified original constraint rather than adding cut b) This code can cope with general integer variables.

Insert the generated cuts into OsiCut, cs.

If a "snapshot" of a matrix exists then this will be used. Presumably this will give global cuts and will be faster. No check is done to see if cuts will be global.

Otherwise use current matrix.

Both row cuts and column cuts may be returned

The mode options are: 0) Only unsatisfied integer variables will be looked at. If no information exists for that variable then probing will be done so as a by-product you "may" get a fixing or infeasibility. This will be fast and is only available if a snapshot exists (otherwise as 1). The bounds in the snapshot are the ones used. 1) Look at unsatisfied integer variables, using current bounds. Probing will be done on all looked at. 2) Look at all integer variables, using current bounds. Probing will be done on all

If generateCutsAndModify is used then new relaxed row bounds and tightened coliumn bounds are generated Returns number of infeasibilities

Implements CglCutGenerator.

int CglProbing::generateCutsAndModify	(	const OsiSolverInterface &	si,
		OsiCuts &	cs,
		CglTreeInfo *	info
	)

Generate probing/disaggregation cuts for the model of the solver interface, si.

This is a simplification of probing ideas put into OSL about ten years ago. The only known documentation is a copy of a talk handout - we think Robin Lougee-Heimer has a copy!

For selected integer variables (e.g. unsatisfied ones) the effect of setting them up or down is investigated. Setting a variable up may in turn set other variables (continuous as well as integer). There are various possible results:

1) It is shown that problem is infeasible (this may also be because objective function or reduced costs show worse than best solution). If the other way is feasible we can generate a column cut (and continue probing), if not feasible we can say problem infeasible.

2) If both ways are feasible, it can happen that x to 0 implies y to 1 and x to 1 implies y to 1 (again a column cut). More common is that x to 0 implies y to 1 and x to 1 implies y to 0 so we could substitute for y which might lead later to more powerful cuts. This is not done in this code as there is no mechanism for returning information.

3) When x to 1 a constraint went slack by c. We can tighten the constraint ax + .... <= b (where a may be zero) to (a+c)x + .... <= b. If this cut is violated then it is generated.

4) Similarly we can generate implied disaggregation cuts

Note - differences to cuts in OSL.

a) OSL had structures intended to make this faster. b) The "chaining" in 2) was done c) Row cuts modified original constraint rather than adding cut b) This code can cope with general integer variables.

Insert the generated cuts into OsiCut, cs.

If a "snapshot" of a matrix exists then this will be used. Presumably this will give global cuts and will be faster. No check is done to see if cuts will be global.

Otherwise use current matrix.

Both row cuts and column cuts may be returned

The mode options are: 0) Only unsatisfied integer variables will be looked at. If no information exists for that variable then probing will be done so as a by-product you "may" get a fixing or infeasibility. This will be fast and is only available if a snapshot exists (otherwise as 1). The bounds in the snapshot are the ones used. 1) Look at unsatisfied integer variables, using current bounds. Probing will be done on all looked at. 2) Look at all integer variables, using current bounds. Probing will be done on all

If generateCutsAndModify is used then new relaxed row bounds and tightened coliumn bounds are generated Returns number of infeasibilities

int CglProbing::snapshot	(	const OsiSolverInterface &	si,
		char *	possible = `NULL`,
		bool	withObjective = `true`
	)

Create a copy of matrix which is to be used this is to speed up process and to give global cuts Can give an array with 1 set to select, 0 to ignore column bounds are tightened If array given then values of 1 will be set to 0 if redundant.

Objective may be added as constraint Returns 1 if infeasible otherwise 0

void CglProbing::deleteSnapshot ( )

Deletes snapshot.

int CglProbing::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 CglProbing::deleteCliques ( )

Delete all clique information.

const double* CglProbing::tightLower ( ) const

Lower.

const double* CglProbing::tightUpper ( ) const

Upper.

const char* CglProbing::tightenBounds ( ) const [inline]

Array which says tighten continuous.

Definition at line 124 of file CglProbing.hpp.

const double* CglProbing::relaxedRowLower ( ) const

Lower.

const double* CglProbing::relaxedRowUpper ( ) const

Upper.

void CglProbing::setMode ( int mode )

Set.

int CglProbing::getMode ( ) const

Get.

void CglProbing::setMaxPass ( int value )

Set maximum number of passes per node.

int CglProbing::getMaxPass ( ) const

Get maximum number of passes per node.

void CglProbing::setLogLevel ( int value )

Set log level - 0 none, 1 - a bit, 2 - more details.

int CglProbing::getLogLevel ( ) const

Get log level.

void CglProbing::setMaxProbe ( int value )

Set maximum number of unsatisfied variables to look at.

int CglProbing::getMaxProbe ( ) const

Get maximum number of unsatisfied variables to look at.

void CglProbing::setMaxLook ( int value )

Set maximum number of variables to look at in one probe.

int CglProbing::getMaxLook ( ) const

Get maximum number of variables to look at in one probe.

void CglProbing::setMaxElements ( int value )

Set maximum number of elements in row for it to be considered.

int CglProbing::getMaxElements ( ) const

Get maximum number of elements in row for it to be considered.

void CglProbing::setMaxPassRoot ( int value )

Set maximum number of passes per node (root node).

int CglProbing::getMaxPassRoot ( ) const

Get maximum number of passes per node (root node).

void CglProbing::setMaxProbeRoot ( int value )

Set maximum number of unsatisfied variables to look at (root node).

int CglProbing::getMaxProbeRoot ( ) const

Get maximum number of unsatisfied variables to look at (root node).

void CglProbing::setMaxLookRoot ( int value )

Set maximum number of variables to look at in one probe (root node).

int CglProbing::getMaxLookRoot ( ) const

Get maximum number of variables to look at in one probe (root node).

void CglProbing::setMaxElementsRoot ( int value )

Set maximum number of elements in row for it to be considered (root node).

int CglProbing::getMaxElementsRoot ( ) const

Get maximum number of elements in row for it to be considered (root node).

virtual bool CglProbing::mayGenerateRowCutsInTree ( ) const [virtual]

Returns true if may generate Row cuts in tree (rather than root node).

Used so know if matrix will change in tree. Really meant so column cut generators can still be active without worrying code. Default is true

Reimplemented from CglCutGenerator.

int CglProbing::numberThisTime ( ) const [inline]

Number looked at this time.

Definition at line 195 of file CglProbing.hpp.

const int* CglProbing::lookedAt ( ) const [inline]

Which ones looked at this time.

Definition at line 198 of file CglProbing.hpp.

void CglProbing::setRowCuts ( int type )

Set 0 no cuts, 1 just disaggregation type, 2 coefficient ( 3 both).

int CglProbing::rowCuts ( ) const

Get.

void CglProbing::setUsingObjective ( int yesNo )

Set 0 don't 1 do -1 don't even think about it.

int CglProbing::getUsingObjective ( ) const

Get.

void CglProbing::tightenThese	(	const OsiSolverInterface &	solver,
		int	number,
		const int *	which
	)

Mark variables to be tightened.

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

Clone.

Implements CglCutGenerator.

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

Assignment operator.

Reimplemented from CglCutGenerator.

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

This can be used to refresh any inforamtion.

Reimplemented from CglCutGenerator.

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

Create C++ lines to get to current state.

Reimplemented from CglCutGenerator.

int CglProbing::probe	(	const OsiSolverInterface &	si,
		const OsiRowCutDebugger *	debugger,
		OsiCuts &	cs,
		double *	colLower,
		double *	colUpper,
		CoinPackedMatrix *	rowCopy,
		CoinPackedMatrix *	columnCopy,
		double *	rowLower,
		double *	rowUpper,
		char *	intVar,
		double *	minR,
		double *	maxR,
		int *	markR,
		CglTreeInfo *	info
	)			const `[private]`

Does probing and adding cuts (without cliques and mode_!=0).

int CglProbing::probeCliques	(	const OsiSolverInterface &	si,
		const OsiRowCutDebugger *	debugger,
		OsiCuts &	cs,
		double *	colLower,
		double *	colUpper,
		CoinPackedMatrix *	rowCopy,
		CoinPackedMatrix *	columnCopy,
		double *	rowLower,
		double *	rowUpper,
		char *	intVar,
		double *	minR,
		double *	maxR,
		int *	markR,
		CglTreeInfo *	info
	)			const `[private]`

Does probing and adding cuts (with cliques).

int CglProbing::probeSlacks	(	const OsiSolverInterface &	si,
		const OsiRowCutDebugger *	debugger,
		OsiCuts &	cs,
		double *	colLower,
		double *	colUpper,
		CoinPackedMatrix *	rowCopy,
		CoinPackedMatrix *	columnCopy,
		double *	rowLower,
		double *	rowUpper,
		char *	intVar,
		double *	minR,
		double *	maxR,
		int *	markR,
		CglTreeInfo *	info
	)			const `[private]`

Does probing and adding cuts for clique slacks.

int CglProbing::gutsOfGenerateCuts	(	const OsiSolverInterface &	si,
		OsiCuts &	cs,
		double *	rowLower,
		double *	rowUpper,
		double *	colLower,
		double *	colUpper,
		CglTreeInfo *	info
	)			const `[private]`

Does most of work of generateCuts Returns number of infeasibilities.

void CglProbing::setupRowCliqueInformation ( const OsiSolverInterface & si ) [private]

Sets up clique information for each row.

int CglProbing::tighten	(	double *	colLower,
		double *	colUpper,
		const int *	column,
		const double *	rowElements,
		const CoinBigIndex *	rowStart,
		const int *	rowLength,
		double *	rowLower,
		double *	rowUpper,
		int	nRows,
		int	nCols,
		char *	intVar,
		int	maxpass,
		double	tolerance
	)			const `[private]`

This tightens column bounds (and can declare infeasibility) It may also declare rows to be redundant.

void CglProbing::tighten2	(	double *	colLower,
		double *	colUpper,
		const int *	column,
		const double *	rowElements,
		const CoinBigIndex *	rowStart,
		const int *	rowLength,
		double *	rowLower,
		double *	rowUpper,
		double *	minR,
		double *	maxR,
		int *	markR,
		int	nRows,
		int	nCols
	)			const `[private]`

This just sets minima and maxima on rows.

Friends And Related Function Documentation

friend struct CglProbing::disaggregation_struct_tag [friend]

Definition at line 316 of file CglProbing.hpp.

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

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