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>

Public Member Functions
Construction / destruction
	SPxFastRT ()
	default constructor More...

	SPxFastRT (const SPxFastRT &old)
	copy constructor More...

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

	SPxFastRT (const char *name)
	bound flipping constructor More...

virtual	~SPxFastRT ()
	destructor More...

virtual SPxRatioTester< R > *	clone () const
	clone function for polymorphism More...

Access / modification
virtual void	load (SPxSolverBase< R > *solver)

virtual int	selectLeave (R &val, R, bool polish=false)

virtual SPxId	selectEnter (R &val, int, bool polish=false)

virtual void	setType (typename SPxSolverBase< R >::Type type)

virtual void	setDelta (R newDelta)

virtual R	getDelta ()

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

virtual void	clear ()
	unloads LP. More...

virtual SPxSolverBase< R > *	solver () const
	returns loaded LP solver. More...

virtual void	setTolerances (std::shared_ptr< Tolerances > newTolerances)
	set the _tolerances member variable More...

const std::shared_ptr< Tolerances >	tolerances () const
	get the _tolerances member variable More...

	SPxRatioTester (const char *name)
	default constructor More...

	SPxRatioTester (const SPxRatioTester &old)
	copy constructor More...

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

virtual	~SPxRatioTester ()
	destructor. More...

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

const R	epsilonZero () const
	return epsilon More...

void	relax ()
	relaxes stability requirements. More...

void	tighten ()
	tightens stability requirements. More...

R	minStability (R maxabs)
	Compute stability requirement. More...

int	maxDelta (R &val, R &maxabs, UpdateVector< R > &update, const VectorBase< R > &lowBound, const VectorBase< R > &upBound, int start, int incr) const
	Max phase 1 value. More...

int	maxDelta (R &val, R &maxabs)

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

int	minDelta (R &val, R &maxabs, UpdateVector< R > &update, const VectorBase< R > &lowBound, const VectorBase< R > &upBound, int start, int incr) const
	Min phase 1 value. More...

int	minDelta (R &val, R &maxabs)

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

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

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

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

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

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

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

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

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

bool	minReLeave (R &sel, int leave, R maxabs, bool polish=false)
	numerical stability tests. More...

bool	maxReLeave (R &sel, int leave, R maxabs, bool polish=false)

bool	minReEnter (R &sel, R maxabs, const SPxId &id, int nr, bool polish=false)
	numerical stability check. More...

bool	maxReEnter (R &sel, R maxabs, const SPxId &id, int nr, bool polish=false)

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

Protected Attributes
Data
R	minStab
	parameter for computing minimum stability requirement More...

R	epsilon
	zero tolerance used by the ratio tester More...

R	fastDelta
	currently allowed infeasibility. More...

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

Protected Attributes inherited from SPxRatioTester< R >
SPxSolverBase< R > *	thesolver
	the solver More...

const char *	m_name
	name of the ratio tester More...

SPxSolverBase< R >::Type	m_type
	internal storage of type More...

R	delta
	allowed bound violation More...

std::shared_ptr< Tolerances >	_tolerances
	tolerances used by the solver More...

Detailed Description

template<class R>
class soplex::SPxFastRT< R >

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 53 of file spxfastrt.h.

Constructor & Destructor Documentation

◆ SPxFastRT() [1/3]

SPxFastRT ( )

default constructor

Definition at line 189 of file spxfastrt.h.

Referenced by SPxFastRT< BP >::clone().

◆ SPxFastRT() [2/3]

SPxFastRT ( const SPxFastRT< R > & old )

copy constructor

Definition at line 197 of file spxfastrt.h.

◆ SPxFastRT() [3/3]

SPxFastRT ( const char * name )

bound flipping constructor

Definition at line 219 of file spxfastrt.h.

◆ ~SPxFastRT()

virtual ~SPxFastRT ( )

virtual

destructor

Definition at line 227 of file spxfastrt.h.

Member Function Documentation

◆ clone()

virtual SPxRatioTester<R>* clone ( ) const

virtual

clone function for polymorphism

Implements SPxRatioTester< R >.

Reimplemented in SPxBoundFlippingRT< R >, and SPxBoundFlippingRT< BP >.

Definition at line 230 of file spxfastrt.h.

◆ epsilonZero()

const R epsilonZero ( ) const

protected

return epsilon

Definition at line 75 of file spxfastrt.h.

◆ getDelta()

virtual R getDelta ( )

virtual

Reimplemented from SPxRatioTester< R >.

Definition at line 257 of file spxfastrt.h.

◆ load()

virtual void load ( SPxSolverBase< R > * solver )

virtual

Reimplemented from SPxRatioTester< R >.

Referenced by SPxFastRT< BP >::clone().

◆ maxDelta() [1/3]

int maxDelta	(	R &	val,
		R &	maxabs,
		UpdateVector< R > &	update,
		const VectorBase< R > &	lowBound,
		const VectorBase< R > &	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.

Referenced by SPxFastRT< BP >::epsilonZero().

◆ maxDelta() [2/3]

int maxDelta	(	R &	val,
		R &	maxabs
	)

protected

◆ maxDelta() [3/3]

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

protected

◆ maxReEnter()

bool maxReEnter	(	R &	sel,
		R	maxabs,
		const SPxId &	id,
		int	nr,
		bool	polish = `false`
	)

protected

Referenced by SPxFastRT< BP >::epsilonZero().

◆ maxReLeave()

bool maxReLeave	(	R &	sel,
		int	leave,
		R	maxabs,
		bool	polish = `false`
	)

protected

Referenced by SPxFastRT< BP >::epsilonZero().

◆ maxSelect() [1/3]

int maxSelect	(	R &	val,
		R &	stab,
		R &	best,
		R &	bestDelta,
		R	max,
		const UpdateVector< R > &	upd,
		const VectorBase< R > &	low,
		const VectorBase< R > &	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.

Referenced by SPxFastRT< BP >::epsilonZero().

◆ maxSelect() [2/3]

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

protected

◆ maxSelect() [3/3]

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

protected

◆ maxShortLeave()

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

protected

Referenced by SPxFastRT< BP >::epsilonZero().

◆ minDelta() [1/3]

int minDelta	(	R &	val,
		R &	maxabs,
		UpdateVector< R > &	update,
		const VectorBase< R > &	lowBound,
		const VectorBase< R > &	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.

Referenced by SPxFastRT< BP >::epsilonZero().

◆ minDelta() [2/3]

int minDelta	(	R &	val,
		R &	maxabs
	)

protected

◆ minDelta() [3/3]

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

protected

◆ minReEnter()

bool minReEnter	(	R &	sel,
		R	maxabs,
		const SPxId &	id,
		int	nr,
		bool	polish = `false`
	)

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.

Referenced by SPxFastRT< BP >::epsilonZero().

◆ minReLeave()

bool minReLeave	(	R &	sel,
		int	leave,
		R	maxabs,
		bool	polish = `false`
	)

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. If polish is set to true no shifts are applied.

Referenced by SPxFastRT< BP >::epsilonZero().

◆ minSelect() [1/3]

int minSelect	(	R &	val,
		R &	stab,
		R &	best,
		R &	bestDelta,
		R	max,
		const UpdateVector< R > &	upd,
		const VectorBase< R > &	low,
		const VectorBase< R > &	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.

Referenced by SPxFastRT< BP >::epsilonZero().

◆ minSelect() [2/3]

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

protected

◆ minSelect() [3/3]

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

protected

◆ minShortLeave()

bool minShortLeave	(	R &	sel,
		int	leave,
		R	maxabs
	)

protected

tests for stop after phase 1.

Tests whether a shortcut after phase 1 is feasible for the selected leave pivot. In this case return the update value in sel.

Referenced by SPxFastRT< BP >::epsilonZero().

◆ minStability()

R minStability ( R maxabs )

protected

Compute stability requirement.

Referenced by SPxFastRT< BP >::epsilonZero().

◆ operator=()

SPxFastRT& operator= ( const SPxFastRT< R > & rhs )

assignment operator

Definition at line 205 of file spxfastrt.h.

Referenced by SPxBoundFlippingRT< BP >::operator=().

◆ relax()

void relax ( )

protected

relaxes stability requirements.

Referenced by SPxFastRT< BP >::epsilonZero().

◆ resetTols()

void resetTols ( )

protected

resets tolerances (epsilon).

◆ selectEnter()

virtual SPxId selectEnter	(	R &	val,
		int	,
		bool	polish = `false`
	)

virtual

Implements SPxRatioTester< R >.

Reimplemented in SPxBoundFlippingRT< R >, and SPxBoundFlippingRT< BP >.

Referenced by SPxFastRT< BP >::clone().

◆ selectLeave()

virtual int selectLeave	(	R &	val,
		R	,
		bool	polish = `false`
	)

virtual

Implements SPxRatioTester< R >.

Reimplemented in SPxBoundFlippingRT< R >, and SPxBoundFlippingRT< BP >.

Referenced by SPxFastRT< BP >::clone().

◆ setDelta()

virtual void setDelta ( R newDelta )

virtual

Reimplemented from SPxRatioTester< R >.

Definition at line 248 of file spxfastrt.h.

◆ setType()

virtual void setType ( typename SPxSolverBase< R >::Type type )

virtual

Reimplemented from SPxRatioTester< R >.

Referenced by SPxFastRT< BP >::clone().

◆ shortEnter()

bool shortEnter	(	const SPxId &	enterId,
		int	nr,
		R	max,
		R	maxabs
	)		const

protected

Tests and returns whether a shortcut after phase 1 is feasible for the selected enter pivot.

Referenced by SPxFastRT< BP >::epsilonZero().

◆ tighten()

void tighten ( )

protected

tightens stability requirements.

Referenced by SPxFastRT< BP >::epsilonZero().

Member Data Documentation

◆ epsilon

R epsilon

protected

zero tolerance used by the ratio tester

Definition at line 62 of file spxfastrt.h.

Referenced by SPxFastRT< BP >::epsilonZero(), SPxFastRT< BP >::operator=(), and SPxFastRT< BP >::setDelta().

◆ fastDelta

R fastDelta

protected

currently allowed infeasibility.

Definition at line 64 of file spxfastrt.h.

Referenced by SPxFastRT< BP >::getDelta(), and SPxFastRT< BP >::operator=().

◆ iscoid

bool iscoid

protected

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

Definition at line 66 of file spxfastrt.h.

◆ minStab

R minStab

protected

parameter for computing minimum stability requirement

Definition at line 60 of file spxfastrt.h.

Referenced by SPxFastRT< BP >::operator=().

SoPlex

Public Member Functions

Protected Member Functions

Protected Attributes

Detailed Description

template<class R> class soplex::SPxFastRT< R >

Constructor & Destructor Documentation

◆ SPxFastRT() [1/3]

◆ SPxFastRT() [2/3]

◆ SPxFastRT() [3/3]

◆ ~SPxFastRT()

Member Function Documentation

◆ clone()

◆ epsilonZero()

◆ getDelta()

◆ load()

◆ maxDelta() [1/3]

◆ maxDelta() [2/3]

◆ maxDelta() [3/3]

◆ maxReEnter()

◆ maxReLeave()

◆ maxSelect() [1/3]

◆ maxSelect() [2/3]

◆ maxSelect() [3/3]

◆ maxShortLeave()

◆ minDelta() [1/3]

◆ minDelta() [2/3]

◆ minDelta() [3/3]

◆ minReEnter()

◆ minReLeave()

◆ minSelect() [1/3]

◆ minSelect() [2/3]

◆ minSelect() [3/3]

◆ minShortLeave()

◆ minStability()

◆ operator=()

◆ relax()

◆ resetTols()

◆ selectEnter()

◆ selectLeave()

◆ setDelta()

◆ setType()

◆ shortEnter()

◆ tighten()

Member Data Documentation

◆ epsilon

◆ fastDelta

◆ iscoid

◆ minStab

template<class R>
class soplex::SPxFastRT< R >