ClpPrimalColumnSteepest Class Reference

Primal Column Pivot Steepest Edge Algorithm Class. More...

#include <ClpPrimalColumnSteepest.hpp>

Inheritance diagram for ClpPrimalColumnSteepest:

[legend]

Collaboration diagram for ClpPrimalColumnSteepest:

[legend]

List of all members.

Public Types
enum	Persistence { normal = 0x00, keep = 0x01 }
	enums for persistence More...
Public Member Functions
Algorithmic methods

virtual int	pivotColumn (CoinIndexedVector updates, CoinIndexedVector spareRow1, CoinIndexedVector spareRow2, CoinIndexedVector spareColumn1, CoinIndexedVector *spareColumn2)
	Returns pivot column, -1 if none.
int	pivotColumnOldMethod (CoinIndexedVector updates, CoinIndexedVector spareRow1, CoinIndexedVector spareRow2, CoinIndexedVector spareColumn1, CoinIndexedVector *spareColumn2)
	For quadratic or funny nonlinearities.
void	justDjs (CoinIndexedVector updates, CoinIndexedVector spareRow1, CoinIndexedVector spareRow2, CoinIndexedVector spareColumn1, CoinIndexedVector *spareColumn2)
	Just update djs.
int	partialPricing (CoinIndexedVector updates, CoinIndexedVector spareRow2, int numberWanted, int numberLook)
	Update djs doing partial pricing (dantzig).
void	djsAndDevex (CoinIndexedVector updates, CoinIndexedVector spareRow1, CoinIndexedVector spareRow2, CoinIndexedVector spareColumn1, CoinIndexedVector *spareColumn2)
	Update djs, weights for Devex using djs.
void	djsAndSteepest (CoinIndexedVector updates, CoinIndexedVector spareRow1, CoinIndexedVector spareRow2, CoinIndexedVector spareColumn1, CoinIndexedVector *spareColumn2)
	Update djs, weights for Steepest using djs.
void	djsAndDevex2 (CoinIndexedVector updates, CoinIndexedVector spareRow1, CoinIndexedVector spareRow2, CoinIndexedVector spareColumn1, CoinIndexedVector *spareColumn2)
	Update djs, weights for Devex using pivot row.
void	djsAndSteepest2 (CoinIndexedVector updates, CoinIndexedVector spareRow1, CoinIndexedVector spareRow2, CoinIndexedVector spareColumn1, CoinIndexedVector *spareColumn2)
	Update djs, weights for Steepest using pivot row.
void	justDevex (CoinIndexedVector updates, CoinIndexedVector spareRow1, CoinIndexedVector spareRow2, CoinIndexedVector spareColumn1, CoinIndexedVector *spareColumn2)
	Update weights for Devex.
void	justSteepest (CoinIndexedVector updates, CoinIndexedVector spareRow1, CoinIndexedVector spareRow2, CoinIndexedVector spareColumn1, CoinIndexedVector *spareColumn2)
	Update weights for Steepest.
void	transposeTimes2 (const CoinIndexedVector pi1, CoinIndexedVector dj1, const CoinIndexedVector pi2, CoinIndexedVector dj2, CoinIndexedVector *spare, double scaleFactor)
	Updates two arrays for steepest.
virtual void	updateWeights (CoinIndexedVector *input)
	Updates weights - part 1 - also checks accuracy.
void	checkAccuracy (int sequence, double relativeTolerance, CoinIndexedVector rowArray1, CoinIndexedVector rowArray2)
	Checks accuracy - just for debug.
void	initializeWeights ()
	Initialize weights.
virtual void	saveWeights (ClpSimplex *model, int mode)
	Save weights.
virtual void	unrollWeights ()
	Gets rid of last update.
virtual void	clearArrays ()
	Gets rid of all arrays.
virtual bool	looksOptimal () const
	Returns true if would not find any column.
virtual void	maximumPivotsChanged ()
	Called when maximum pivots changes.
gets and sets

int	mode () const
	Mode.
virtual int	numberSprintColumns (int &numberIterations) const
	Returns number of extra columns for sprint algorithm - 0 means off.
virtual void	switchOffSprint ()
	Switch off sprint idea.
Constructors and destructors

	ClpPrimalColumnSteepest (int mode=3)
	Default Constructor 0 is exact devex, 1 full steepest, 2 is partial exact devex 3 switches between 0 and 2 depending on factorization 4 starts as partial dantzig/devex but then may switch between 0 and 2.
	ClpPrimalColumnSteepest (const ClpPrimalColumnSteepest &)
	Copy constructor.
ClpPrimalColumnSteepest &	operator= (const ClpPrimalColumnSteepest &rhs)
	Assignment operator.
virtual	~ClpPrimalColumnSteepest ()
	Destructor.
virtual ClpPrimalColumnPivot *	clone (bool copyData=true) const
	Clone.
Private functions to deal with devex

bool	reference (int i) const
	reference would be faster using ClpSimplex's status_, but I prefer to keep modularity.
void	setReference (int i, bool trueFalse)
	reference would be faster using ClpSimplex's status_, but I prefer to keep modularity.
void	setPersistence (Persistence life)
	Set/ get persistence.
Persistence	persistence () const
	reference would be faster using ClpSimplex's status_, but I prefer to keep modularity.
Private Attributes
Private member data

double	devex_
	weight array
double *	weights_
	weight array
CoinIndexedVector *	infeasible_
	square of infeasibility array (just for infeasible columns)
CoinIndexedVector *	alternateWeights_
	alternate weight array (so we can unroll)
double *	savedWeights_
	save weight array (so we can use checkpoint)
unsigned int *	reference_
	weight array
int	state_
	Status 0) Normal -1) Needs initialization 1) Weights are stored by sequence number.
int	mode_
	0 is exact devex, 1 full steepest, 2 is partial exact devex 3 switches between 0 and 2 depending on factorization 4 starts as partial dantzig/devex but then may switch between 0 and 2.
Persistence	persistence_
	Life of weights.
int	numberSwitched_
	Number of times switched from partial dantzig to 0/2.
int	pivotSequence_
	weight array
int	savedPivotSequence_
	weight array
int	savedSequenceOut_
	weight array
int	lastRectified_
	weight array
int	sizeFactorization_
	weight array

Detailed Description

Primal Column Pivot Steepest Edge Algorithm Class.

See Forrest-Goldfarb paper for algorithm

Definition at line 20 of file ClpPrimalColumnSteepest.hpp.

Member Enumeration Documentation

enum ClpPrimalColumnSteepest::Persistence

enums for persistence

Enumerator:

normal
keep

Definition at line 136 of file ClpPrimalColumnSteepest.hpp.

Constructor & Destructor Documentation

ClpPrimalColumnSteepest::ClpPrimalColumnSteepest ( int mode = 3 )

Default Constructor 0 is exact devex, 1 full steepest, 2 is partial exact devex 3 switches between 0 and 2 depending on factorization 4 starts as partial dantzig/devex but then may switch between 0 and 2.

By partial exact devex is meant that the weights are updated as normal but only part of the nonbasic variables are scanned. This can be faster on very easy problems.

ClpPrimalColumnSteepest::ClpPrimalColumnSteepest ( const ClpPrimalColumnSteepest & )

Copy constructor.

virtual ClpPrimalColumnSteepest::~ClpPrimalColumnSteepest ( ) [virtual]

Destructor.

Member Function Documentation

virtual int ClpPrimalColumnSteepest::pivotColumn	(	CoinIndexedVector *	updates,
		CoinIndexedVector *	spareRow1,
		CoinIndexedVector *	spareRow2,
		CoinIndexedVector *	spareColumn1,
		CoinIndexedVector *	spareColumn2
	)			`[virtual]`

Returns pivot column, -1 if none.

The Packed CoinIndexedVector updates has cost updates - for normal LP that is just +-weight where a feasibility changed. It also has reduced cost from last iteration in pivot row Parts of operation split out into separate functions for profiling and speed

Implements ClpPrimalColumnPivot.

int ClpPrimalColumnSteepest::pivotColumnOldMethod	(	CoinIndexedVector *	updates,
		CoinIndexedVector *	spareRow1,
		CoinIndexedVector *	spareRow2,
		CoinIndexedVector *	spareColumn1,
		CoinIndexedVector *	spareColumn2
	)

For quadratic or funny nonlinearities.

void ClpPrimalColumnSteepest::justDjs	(	CoinIndexedVector *	updates,
		CoinIndexedVector *	spareRow1,
		CoinIndexedVector *	spareRow2,
		CoinIndexedVector *	spareColumn1,
		CoinIndexedVector *	spareColumn2
	)

Just update djs.

int ClpPrimalColumnSteepest::partialPricing	(	CoinIndexedVector *	updates,
		CoinIndexedVector *	spareRow2,
		int	numberWanted,
		int	numberLook
	)

Update djs doing partial pricing (dantzig).

void ClpPrimalColumnSteepest::djsAndDevex	(	CoinIndexedVector *	updates,
		CoinIndexedVector *	spareRow1,
		CoinIndexedVector *	spareRow2,
		CoinIndexedVector *	spareColumn1,
		CoinIndexedVector *	spareColumn2
	)

Update djs, weights for Devex using djs.

void ClpPrimalColumnSteepest::djsAndSteepest	(	CoinIndexedVector *	updates,
		CoinIndexedVector *	spareRow1,
		CoinIndexedVector *	spareRow2,
		CoinIndexedVector *	spareColumn1,
		CoinIndexedVector *	spareColumn2
	)

Update djs, weights for Steepest using djs.

void ClpPrimalColumnSteepest::djsAndDevex2	(	CoinIndexedVector *	updates,
		CoinIndexedVector *	spareRow1,
		CoinIndexedVector *	spareRow2,
		CoinIndexedVector *	spareColumn1,
		CoinIndexedVector *	spareColumn2
	)

Update djs, weights for Devex using pivot row.

void ClpPrimalColumnSteepest::djsAndSteepest2	(	CoinIndexedVector *	updates,
		CoinIndexedVector *	spareRow1,
		CoinIndexedVector *	spareRow2,
		CoinIndexedVector *	spareColumn1,
		CoinIndexedVector *	spareColumn2
	)

Update djs, weights for Steepest using pivot row.

void ClpPrimalColumnSteepest::justDevex	(	CoinIndexedVector *	updates,
		CoinIndexedVector *	spareRow1,
		CoinIndexedVector *	spareRow2,
		CoinIndexedVector *	spareColumn1,
		CoinIndexedVector *	spareColumn2
	)

Update weights for Devex.

void ClpPrimalColumnSteepest::justSteepest	(	CoinIndexedVector *	updates,
		CoinIndexedVector *	spareRow1,
		CoinIndexedVector *	spareRow2,
		CoinIndexedVector *	spareColumn1,
		CoinIndexedVector *	spareColumn2
	)

Update weights for Steepest.

void ClpPrimalColumnSteepest::transposeTimes2	(	const CoinIndexedVector *	pi1,
		CoinIndexedVector *	dj1,
		const CoinIndexedVector *	pi2,
		CoinIndexedVector *	dj2,
		CoinIndexedVector *	spare,
		double	scaleFactor
	)

Updates two arrays for steepest.

virtual void ClpPrimalColumnSteepest::updateWeights ( CoinIndexedVector * input ) [virtual]

Updates weights - part 1 - also checks accuracy.

Reimplemented from ClpPrimalColumnPivot.

void ClpPrimalColumnSteepest::checkAccuracy	(	int	sequence,
		double	relativeTolerance,
		CoinIndexedVector *	rowArray1,
		CoinIndexedVector *	rowArray2
	)

Checks accuracy - just for debug.

void ClpPrimalColumnSteepest::initializeWeights ( )

Initialize weights.

virtual void ClpPrimalColumnSteepest::saveWeights	(	ClpSimplex *	model,
		int	mode
	)			`[virtual]`

Save weights.

Implements ClpPrimalColumnPivot.

virtual void ClpPrimalColumnSteepest::unrollWeights ( ) [virtual]

Gets rid of last update.

virtual void ClpPrimalColumnSteepest::clearArrays ( ) [virtual]

Gets rid of all arrays.

Reimplemented from ClpPrimalColumnPivot.

virtual bool ClpPrimalColumnSteepest::looksOptimal ( ) const [virtual]

Returns true if would not find any column.

Reimplemented from ClpPrimalColumnPivot.

virtual void ClpPrimalColumnSteepest::maximumPivotsChanged ( ) [virtual]

Called when maximum pivots changes.

Reimplemented from ClpPrimalColumnPivot.

int ClpPrimalColumnSteepest::mode ( ) const [inline]

Mode.

Definition at line 123 of file ClpPrimalColumnSteepest.hpp.

virtual int ClpPrimalColumnSteepest::numberSprintColumns ( int & numberIterations ) const [virtual]

Returns number of extra columns for sprint algorithm - 0 means off.

Also number of iterations before recompute

Reimplemented from ClpPrimalColumnPivot.

virtual void ClpPrimalColumnSteepest::switchOffSprint ( ) [virtual]

Switch off sprint idea.

Reimplemented from ClpPrimalColumnPivot.

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

Assignment operator.

Reimplemented from ClpPrimalColumnPivot.

virtual ClpPrimalColumnPivot* ClpPrimalColumnSteepest::clone ( bool copyData = true ) const [virtual]

Clone.

Implements ClpPrimalColumnPivot.

bool ClpPrimalColumnSteepest::reference ( int i ) const [inline]

reference would be faster using ClpSimplex's status_, but I prefer to keep modularity.

Definition at line 171 of file ClpPrimalColumnSteepest.hpp.

void ClpPrimalColumnSteepest::setReference	(	int	i,
		bool	trueFalse
	)			`[inline]`

reference would be faster using ClpSimplex's status_, but I prefer to keep modularity.

Definition at line 174 of file ClpPrimalColumnSteepest.hpp.

void ClpPrimalColumnSteepest::setPersistence ( Persistence life ) [inline]

Set/ get persistence.

Definition at line 183 of file ClpPrimalColumnSteepest.hpp.

Persistence ClpPrimalColumnSteepest::persistence ( ) const [inline]

reference would be faster using ClpSimplex's status_, but I prefer to keep modularity.

Definition at line 185 of file ClpPrimalColumnSteepest.hpp.

Member Data Documentation

double ClpPrimalColumnSteepest::devex_ [private]

weight array

Definition at line 194 of file ClpPrimalColumnSteepest.hpp.

double* ClpPrimalColumnSteepest::weights_ [private]

weight array

Definition at line 196 of file ClpPrimalColumnSteepest.hpp.

CoinIndexedVector* ClpPrimalColumnSteepest::infeasible_ [private]

square of infeasibility array (just for infeasible columns)

Definition at line 198 of file ClpPrimalColumnSteepest.hpp.

CoinIndexedVector* ClpPrimalColumnSteepest::alternateWeights_ [private]

alternate weight array (so we can unroll)

Definition at line 200 of file ClpPrimalColumnSteepest.hpp.

double* ClpPrimalColumnSteepest::savedWeights_ [private]

save weight array (so we can use checkpoint)

Definition at line 202 of file ClpPrimalColumnSteepest.hpp.

unsigned int* ClpPrimalColumnSteepest::reference_ [private]

weight array

Definition at line 204 of file ClpPrimalColumnSteepest.hpp.

int ClpPrimalColumnSteepest::state_ [private]

Status 0) Normal -1) Needs initialization 1) Weights are stored by sequence number.

Definition at line 210 of file ClpPrimalColumnSteepest.hpp.

int ClpPrimalColumnSteepest::mode_ [private]

0 is exact devex, 1 full steepest, 2 is partial exact devex 3 switches between 0 and 2 depending on factorization 4 starts as partial dantzig/devex but then may switch between 0 and 2.

5 is always partial dantzig By partial exact devex is meant that the weights are updated as normal but only part of the nonbasic variables are scanned. This can be faster on very easy problems.

New dubious option is >=10 which does mini-sprint

Definition at line 223 of file ClpPrimalColumnSteepest.hpp.

Persistence ClpPrimalColumnSteepest::persistence_ [private]

Life of weights.

Definition at line 225 of file ClpPrimalColumnSteepest.hpp.

int ClpPrimalColumnSteepest::numberSwitched_ [private]

Number of times switched from partial dantzig to 0/2.

Definition at line 227 of file ClpPrimalColumnSteepest.hpp.

int ClpPrimalColumnSteepest::pivotSequence_ [private]

weight array

Definition at line 229 of file ClpPrimalColumnSteepest.hpp.

int ClpPrimalColumnSteepest::savedPivotSequence_ [private]