Fast shifting ratio test.Class SPxFastRT is an implementation class of SPxRatioTester providing fast and stable ratio test. Stability is achieved by allowing some infeasibility to ensure numerical stability such as the Harris procedure. Performance is achieved by skipping the second phase if the first phase already shows a stable enough pivot. More...

#include <spxfastrt.h>

Inheritance diagram for SPxFastRT:

[legend]

Public Member Functions
Construction / destruction
	SPxFastRT ()
	default constructor

	SPxFastRT (const SPxFastRT &old)
	copy constructor

SPxFastRT &	operator= (const SPxFastRT &rhs)
	assignment operator

	SPxFastRT (const char *name)
	bound flipping constructor

virtual	~SPxFastRT ()
	destructor

virtual SPxRatioTester *	clone () const
	clone function for polymorphism

Access / modification
virtual void	load (SPxSolver *solver)

virtual int	selectLeave (Real &val, SPxId)

virtual SPxId	selectEnter (Real &val, int)

virtual void	setType (SPxSolver::Type type)

virtual void	setDelta (Real newDelta)

virtual Real	getDelta ()

Public Member Functions inherited from SPxRatioTester
virtual const char *	getName () const
	get name of ratio tester.

virtual void	clear ()
	unloads LP.

virtual SPxSolver *	solver () const
	returns loaded LP solver.

	SPxRatioTester (const char *name)
	default constructor

	SPxRatioTester (const SPxRatioTester &old)
	copy constructor

SPxRatioTester &	operator= (const SPxRatioTester &rhs)
	assignment operator

virtual	~SPxRatioTester ()
	destructor.

Protected Member Functions
Private helpers
void	resetTols ()
	resets tolerances (epsilon).

void	relax ()
	relaxes stability requirements.

void	tighten ()
	tightens stability requirements.

Real	minStability (Real maxabs)
	Compute stability requirement.

int	maxDelta (Real &val, Real &maxabs, UpdateVector &update, const Vector &lowBound, const Vector &upBound, int start, int incr) const
	Max phase 1 value.

int	maxDelta (Real &val, Real &maxabs)

SPxId	maxDelta (int &nr, Real &val, Real &maxabs)

int	minDelta (Real &val, Real &maxabs, UpdateVector &update, const Vector &lowBound, const Vector &upBound, int start, int incr) const
	Min phase 1 value.

int	minDelta (Real &val, Real &maxabs)

SPxId	minDelta (int &nr, Real &val, Real &maxabs)

int	maxSelect (Real &val, Real &stab, Real &best, Real &bestDelta, Real max, const UpdateVector &upd, const Vector &low, const Vector &up, int start=0, int incr=1) const
	selects stable index for maximizing ratio test.

int	maxSelect (Real &val, Real &stab, Real &bestDelta, Real max)

SPxId	maxSelect (int &nr, Real &val, Real &stab, Real &bestDelta, Real max)

int	minSelect (Real &val, Real &stab, Real &best, Real &bestDelta, Real max, const UpdateVector &upd, const Vector &low, const Vector &up, int start=0, int incr=1) const
	selects stable index for minimizing ratio test.

int	minSelect (Real &val, Real &stab, Real &bestDelta, Real max)

SPxId	minSelect (int &nr, Real &val, Real &stab, Real &bestDelta, Real max)

bool	minShortLeave (Real &sel, int leave, Real maxabs)
	tests for stop after phase 1.

bool	maxShortLeave (Real &sel, int leave, Real maxabs)

bool	minReLeave (Real &sel, int leave, Real maxabs)
	numerical stability tests.

bool	maxReLeave (Real &sel, int leave, Real maxabs)

bool	minReEnter (Real &sel, Real maxabs, const SPxId &id, int nr)
	numerical stability check.

bool	maxReEnter (Real &sel, Real maxabs, const SPxId &id, int nr)

bool	shortEnter (const SPxId &enterId, int nr, Real max, Real maxabs) const
	Tests and returns whether a shortcut after phase 1 is feasible for the selected enter pivot.

Protected Attributes
Data
Real	minStab
	parameter for computing minimum stability requirement

Real	epsilon
	\|value\| < epsilon is considered 0.

Real	fastDelta
	currently allowed infeasibility.

bool	iscoid
	flag used in methods minSelect/maxSelect to retrieve correct basis status

Protected Attributes inherited from SPxRatioTester
SPxSolver *	thesolver
	the solver

const char *	m_name
	name of the ratio tester

SPxSolver::Type	m_type
	internal storage of type

Real	delta
	allowed bound violation

Detailed Description

Fast shifting ratio test.

Class SPxFastRT is an implementation class of SPxRatioTester providing fast and stable ratio test. Stability is achieved by allowing some infeasibility to ensure numerical stability such as the Harris procedure. Performance is achieved by skipping the second phase if the first phase already shows a stable enough pivot.

See SPxRatioTester for a class documentation.

Definition at line 41 of file spxfastrt.h.

Constructor & Destructor Documentation

SPxFastRT ( )

default constructor

Definition at line 171 of file spxfastrt.h.

Referenced by SPxFastRT::clone().

SPxFastRT ( const SPxFastRT & old )

copy constructor

Definition at line 176 of file spxfastrt.h.

SPxFastRT ( const char * name )

bound flipping constructor

Definition at line 198 of file spxfastrt.h.

virtual ~SPxFastRT ( )

virtual

destructor

Definition at line 203 of file spxfastrt.h.

Member Function Documentation

virtual SPxRatioTester* clone ( ) const

virtual

clone function for polymorphism

Implements SPxRatioTester.

Reimplemented in SPxBoundFlippingRT.

Definition at line 206 of file spxfastrt.h.

References SPxFastRT::SPxFastRT().

virtual Real getDelta ( )

virtual

Reimplemented from SPxRatioTester.

Definition at line 232 of file spxfastrt.h.

References SPxFastRT::fastDelta.

void load ( SPxSolver * solver )

virtual

Reimplemented from SPxRatioTester.

Definition at line 1290 of file spxfastrt.cpp.

References SPxFastRT::setType(), SPxRatioTester::thesolver, and SPxSolver::type().

int maxDelta	(	Real &	val,
		Real &	maxabs,
		UpdateVector &	update,
		const Vector &	lowBound,
		const Vector &	upBound,
		int	start,
		int	incr
	)		const

protected

Max phase 1 value.

Computes the maximum value val that could be used for updating update such that it would still fulfill the upper and lower bounds upBound and lowBound, respectively, within delta. Return value is the index where the maximum value is encountered. At the same time the maximum absolute value of update.delta() is computed and returned in maxabs. Internally all loops are started at start and incremented by incr.

Definition at line 103 of file spxfastrt.cpp.

References SSVector::altIndexMem(), SSVector::altValues(), UpdateVector::delta(), Vector::dim(), SPxFastRT::epsilon, SPxFastRT::fastDelta, SSVector::forceSetup(), Vector::get_const_ptr(), SSVector::indexMem(), soplex::infinity, SPxSolver::isBasic(), SPxSolver::isCoBasic(), SPxFastRT::iscoid, SSVector::isSetup(), SPxSolver::LEAVE, SPxRatioTester::m_type, SSVector::setSize(), SSVector::size(), SPxRatioTester::thesolver, and SSVector::values().

Referenced by SPxFastRT::maxDelta(), SPxFastRT::selectEnter(), and SPxFastRT::selectLeave().

int maxDelta	(	Real &	val,
		Real &	maxabs
	)

protected

Definition at line 413 of file spxfastrt.cpp.

References SPxSolver::fVec(), SPxSolver::lbBound(), SPxFastRT::maxDelta(), SPxRatioTester::thesolver, and SPxSolver::ubBound().

SPxId maxDelta	(	int &	nr,
		Real &	val,
		Real &	maxabs
	)

protected

Definition at line 429 of file spxfastrt.cpp.

References SPxSolver::coId(), SPxSolver::coPvec(), SPxSolver::id(), SPxFastRT::iscoid, SPxSolver::lcBound(), SPxSolver::lpBound(), SPxFastRT::maxDelta(), SPxSolver::pVec(), SPxRatioTester::thesolver, SPxSolver::ucBound(), and SPxSolver::upBound().

bool maxReEnter	(	Real &	sel,
		Real	maxabs,
		const SPxId &	id,
		int	nr
	)

protected

Definition at line 957 of file spxfastrt.cpp.

References SSVector::clearIdx(), SPxSolver::coPvec(), UpdateVector::delta(), SPxFastRT::fastDelta, SPxSolver::isBasic(), SPxSolver::isCoBasic(), SPxSolver::isCoId(), SPxSolver::isId(), SPxSolver::lcBound(), SPxSolver::lpBound(), SPxSolver::pVec(), SPxSolver::theShift, SPxRatioTester::thesolver, SPxSolver::ucBound(), SPxSolver::upBound(), and SPxSolver::vector().

Referenced by SPxFastRT::selectEnter().

bool maxReLeave	(	Real &	sel,
		int	leave,
		Real	maxabs
	)

protected

Definition at line 777 of file spxfastrt.cpp.

References UpdateVector::delta(), SPxFastRT::fastDelta, SPxSolver::fVec(), SPxSolver::lbBound(), SPxSolver::shiftLBbound(), SPxSolver::shiftUBbound(), SPxRatioTester::thesolver, and SPxSolver::ubBound().

Referenced by SPxFastRT::selectLeave().

int maxSelect	(	Real &	val,
		Real &	stab,
		Real &	best,
		Real &	bestDelta,
		Real	max,
		const UpdateVector &	upd,
		const Vector &	low,
		const Vector &	up,
		int	start = `0`,
		int	incr = `1`
	)		const

protected

selects stable index for maximizing ratio test.

Selects from all update values val < max the one with the largest value of upd.delta() which must be greater than stab and is returned in stab. The index is returned as well as the corresponding update value val. Internally all loops are started at start and incremented by incr.

Definition at line 567 of file spxfastrt.cpp.

References UpdateVector::delta(), Vector::get_const_ptr(), SSVector::indexMem(), SPxSolver::isBasic(), SPxSolver::isCoBasic(), SPxFastRT::iscoid, SPxSolver::LEAVE, SPxRatioTester::m_type, SSVector::size(), SPxRatioTester::thesolver, and SSVector::values().

Referenced by SPxFastRT::maxSelect(), SPxFastRT::selectEnter(), and SPxFastRT::selectLeave().

int maxSelect	(	Real &	val,
		Real &	stab,
		Real &	bestDelta,
		Real	max
	)

protected

Definition at line 646 of file spxfastrt.cpp.

References SPxSolver::fVec(), soplex::infinity, SPxSolver::lbBound(), SPxFastRT::maxSelect(), SPxRatioTester::thesolver, and SPxSolver::ubBound().

SPxId maxSelect	(	int &	nr,
		Real &	val,
		Real &	stab,
		Real &	bestDelta,
		Real	max
	)

protected

Definition at line 658 of file spxfastrt.cpp.

References SPxSolver::coId(), SPxSolver::coPvec(), SPxSolver::id(), soplex::infinity, SPxFastRT::iscoid, SPxSolver::lcBound(), SPxSolver::lpBound(), SPxFastRT::maxSelect(), SPxSolver::pVec(), SPxRatioTester::thesolver, SPxSolver::ucBound(), and SPxSolver::upBound().

bool maxShortLeave	(	Real &	sel,
		int	leave,
		Real	maxabs
	)

protected

Definition at line 733 of file spxfastrt.cpp.

References UpdateVector::delta(), SPxSolver::fVec(), SPxSolver::lbBound(), SHORT, SPxRatioTester::thesolver, and SPxSolver::ubBound().

Referenced by SPxFastRT::selectLeave().

int minDelta	(	Real &	val,
		Real &	maxabs,
		UpdateVector &	update,
		const Vector &	lowBound,
		const Vector &	upBound,
		int	start,
		int	incr
	)		const

protected

Min phase 1 value.

Computes the minimum value val that could be used for updating update such that it would still fulfill the upper and lower bounds upBound and lowBound, respectively, within delta. Return value is the index where the minimum value is encountered. At the same time the maximum absolute value of update.delta() is computed and returned in maxabs. Internally all loops are started at start and incremented by incr.

Definition at line 258 of file spxfastrt.cpp.

References SSVector::altIndexMem(), SSVector::altValues(), UpdateVector::delta(), Vector::dim(), SPxFastRT::epsilon, SPxFastRT::fastDelta, SSVector::forceSetup(), Vector::get_const_ptr(), SSVector::indexMem(), soplex::infinity, SPxSolver::isBasic(), SPxSolver::isCoBasic(), SPxFastRT::iscoid, SSVector::isSetup(), SPxSolver::LEAVE, SPxRatioTester::m_type, SSVector::setSize(), SSVector::size(), SPxRatioTester::thesolver, and SSVector::values().

Referenced by SPxFastRT::minDelta(), SPxFastRT::selectEnter(), and SPxFastRT::selectLeave().

int minDelta	(	Real &	val,
		Real &	maxabs
	)

protected

Definition at line 421 of file spxfastrt.cpp.

References SPxSolver::fVec(), SPxSolver::lbBound(), SPxFastRT::minDelta(), SPxRatioTester::thesolver, and SPxSolver::ubBound().

SPxId minDelta	(	int &	nr,
		Real &	val,
		Real &	maxabs
	)

protected

Definition at line 457 of file spxfastrt.cpp.

References SPxSolver::coId(), SPxSolver::coPvec(), SPxSolver::id(), SPxFastRT::iscoid, SPxSolver::lcBound(), SPxSolver::lpBound(), SPxFastRT::minDelta(), SPxSolver::pVec(), SPxRatioTester::thesolver, SPxSolver::ucBound(), and SPxSolver::upBound().

bool minReEnter	(	Real &	sel,
		Real	maxabs,
		const SPxId &	id,
		int	nr
	)

protected

numerical stability check.

Tests whether the selected enter id needs to be discarded (and do so) and the ratio test is to be recomputed.

Definition at line 1049 of file spxfastrt.cpp.

References SSVector::clearIdx(), SPxSolver::coPvec(), UpdateVector::delta(), SPxFastRT::fastDelta, SPxSolver::isBasic(), SPxSolver::isCoBasic(), SPxSolver::isCoId(), SPxSolver::isId(), SPxSolver::lcBound(), SPxSolver::lpBound(), SPxSolver::pVec(), SPxSolver::theShift, SPxRatioTester::thesolver, SPxSolver::ucBound(), SPxSolver::upBound(), and SPxSolver::vector().

Referenced by SPxFastRT::selectEnter().

bool minReLeave	(	Real &	sel,
		int	leave,
		Real	maxabs
	)

protected

numerical stability tests.

Tests whether the selected leave index needs to be discarded (and do so) and the ratio test is to be recomputed.

Definition at line 809 of file spxfastrt.cpp.

References UpdateVector::delta(), SPxFastRT::fastDelta, SPxSolver::fVec(), SPxSolver::lbBound(), SPxSolver::theShift, SPxRatioTester::thesolver, and SPxSolver::ubBound().

Referenced by SPxFastRT::selectLeave().

int minSelect	(	Real &	val,
		Real &	stab,
		Real &	best,
		Real &	bestDelta,
		Real	max,
		const UpdateVector &	upd,
		const Vector &	low,
		const Vector &	up,
		int	start = `0`,
		int	incr = `1`
	)		const

protected

selects stable index for minimizing ratio test.

Select from all update values val > max the one with the largest value of upd.delta() which must be greater than stab and is returned in stab. The index is returned as well as the corresponding update value val. Internally all loops are started at start and incremented by incr.

Definition at line 488 of file spxfastrt.cpp.

References UpdateVector::delta(), Vector::get_const_ptr(), SSVector::indexMem(), SPxSolver::isBasic(), SPxSolver::isCoBasic(), SPxFastRT::iscoid, SPxSolver::LEAVE, SPxRatioTester::m_type, SSVector::size(), SPxRatioTester::thesolver, and SSVector::values().