SoPlex Documentation
Loading...
Searching...
No Matches
SPxFastRT< R > Class Template Reference

Fast shifting ratio test. More...

#include <spxfastrt.h>

Inheritance diagram for SPxFastRT< R >:
SPxRatioTester< R > SPxBoundFlippingRT< R >

Public Member Functions

Construction / destruction
 SPxFastRT ()
 default constructor
 
 SPxFastRT (const SPxFastRT &old)
 copy constructor
 
SPxFastRToperator= (const SPxFastRT &rhs)
 assignment operator
 
 SPxFastRT (const char *name)
 bound flipping constructor
 
virtual ~SPxFastRT ()
 destructor
 
virtual SPxRatioTester< R > * clone () const
 clone function for polymorphism
 
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.
 
virtual void clear ()
 unloads LP.
 
virtual SPxSolverBase< R > * solver () const
 returns loaded LP solver.
 
virtual void setTolerances (std::shared_ptr< Tolerances > newTolerances)
 set the _tolerances member variable
 
const std::shared_ptr< Tolerancestolerances () const
 get the _tolerances member variable
 
 SPxRatioTester (const char *name)
 default constructor
 
 SPxRatioTester (const SPxRatioTester &old)
 copy constructor
 
SPxRatioTesteroperator= (const SPxRatioTester &rhs)
 assignment operator
 
virtual ~SPxRatioTester ()
 destructor.
 

Protected Member Functions

Private helpers
void resetTols ()
 resets tolerances (epsilon).
 
const R epsilonZero () const
 return epsilon
 
void relax ()
 relaxes stability requirements.
 
void tighten ()
 tightens stability requirements.
 
minStability (R maxabs)
 Compute stability requirement.
 
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.
 
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.
 
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.
 
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.
 
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.
 
bool maxShortLeave (R &sel, int leave, R maxabs)
 
bool minReLeave (R &sel, int leave, R maxabs, bool polish=false)
 numerical stability tests.
 
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.
 
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.
 

Protected Attributes

Data
minStab
 parameter for computing minimum stability requirement
 
epsilon
 zero tolerance used by the ratio tester
 
fastDelta
 currently allowed infeasibility.
 
bool iscoid
 flag used in methods minSelect/maxSelect to retrieve correct basis status
 
- Protected Attributes inherited from SPxRatioTester< R >
SPxSolverBase< R > * thesolver
 the solver
 
const char * m_name
 name of the ratio tester
 
SPxSolverBase< R >::Type m_type
 internal storage of type
 
delta
 allowed bound violation
 
std::shared_ptr< Tolerances_tolerances
 tolerances used by the solver
 

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 68 of file spxsolver.h.

Constructor & Destructor Documentation

◆ SPxFastRT() [1/3]

template<class R >
SPxFastRT ( )

default constructor

Definition at line 189 of file spxfastrt.h.

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

◆ SPxFastRT() [2/3]

template<class R >
SPxFastRT ( const SPxFastRT< R > & old)

copy constructor

Definition at line 197 of file spxfastrt.h.

◆ SPxFastRT() [3/3]

template<class R >
SPxFastRT ( const char * name)

bound flipping constructor

Definition at line 219 of file spxfastrt.h.

◆ ~SPxFastRT()

template<class R >
virtual ~SPxFastRT ( )
virtual

destructor

Definition at line 227 of file spxfastrt.h.

Member Function Documentation

◆ clone()

template<class R >
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.

References SPxFastRT< R >::SPxFastRT().

◆ epsilonZero()

template<class R >
const R epsilonZero ( ) const
protected

return epsilon

Definition at line 75 of file spxfastrt.h.

References SPxFastRT< R >::epsilon.

◆ getDelta()

template<class R >
virtual R getDelta ( )
virtual

Reimplemented from SPxRatioTester< R >.

Definition at line 257 of file spxfastrt.h.

References SPxFastRT< R >::fastDelta.

◆ load()

template<class R >
virtual void load ( SPxSolverBase< R > * solver)
virtual

Reimplemented from SPxRatioTester< R >.

◆ maxDelta() [1/3]

template<class R >
SPxId maxDelta ( int & nr,
R & val,
R & maxabs )
protected

◆ maxDelta() [2/3]

template<class R >
int maxDelta ( R & val,
R & maxabs )
protected

◆ maxDelta() [3/3]

template<class R >
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.

◆ maxReEnter()

template<class R >
bool maxReEnter ( R & sel,
R maxabs,
const SPxId & id,
int nr,
bool polish = false )
protected

◆ maxReLeave()

template<class R >
bool maxReLeave ( R & sel,
int leave,
R maxabs,
bool polish = false )
protected

◆ maxSelect() [1/3]

template<class R >
SPxId maxSelect ( int & nr,
R & val,
R & stab,
R & bestDelta,
R max )
protected

◆ maxSelect() [2/3]

template<class R >
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.

◆ maxSelect() [3/3]

template<class R >
int maxSelect ( R & val,
R & stab,
R & bestDelta,
R max )
protected

◆ maxShortLeave()

template<class R >
bool maxShortLeave ( R & sel,
int leave,
R maxabs )
protected

◆ minDelta() [1/3]

template<class R >
SPxId minDelta ( int & nr,
R & val,
R & maxabs )
protected

◆ minDelta() [2/3]

template<class R >
int minDelta ( R & val,
R & maxabs )
protected

◆ minDelta() [3/3]

template<class R >
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.

◆ minReEnter()

template<class R >
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.

◆ minReLeave()

template<class R >
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.

◆ minSelect() [1/3]

template<class R >
SPxId minSelect ( int & nr,
R & val,
R & stab,
R & bestDelta,
R max )
protected

◆ minSelect() [2/3]

template<class R >
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.

◆ minSelect() [3/3]

template<class R >
int minSelect ( R & val,
R & stab,
R & bestDelta,
R max )
protected

◆ minShortLeave()

template<class R >
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.

◆ minStability()

template<class R >
R minStability ( R maxabs)
protected

Compute stability requirement.

◆ operator=()

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

◆ relax()

template<class R >
void relax ( )
protected

relaxes stability requirements.

◆ resetTols()

template<class R >
void resetTols ( )
protected

resets tolerances (epsilon).

◆ selectEnter()

template<class R >
virtual SPxId selectEnter ( R & val,
int ,
bool polish = false )
virtual

◆ selectLeave()

template<class R >
virtual int selectLeave ( R & val,
R ,
bool polish = false )
virtual

◆ setDelta()

template<class R >
virtual void setDelta ( R newDelta)
virtual

◆ setType()

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

Reimplemented from SPxRatioTester< R >.

◆ shortEnter()

template<class R >
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.

◆ tighten()

template<class R >
void tighten ( )
protected

tightens stability requirements.

Member Data Documentation

◆ epsilon

template<class R >
R epsilon
protected

zero tolerance used by the ratio tester

Definition at line 62 of file spxfastrt.h.

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

◆ fastDelta

template<class R >
R fastDelta
protected

currently allowed infeasibility.

Definition at line 64 of file spxfastrt.h.

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

◆ iscoid

template<class R >
bool iscoid
protected

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

Definition at line 66 of file spxfastrt.h.

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

◆ minStab

template<class R >
R minStab
protected

parameter for computing minimum stability requirement

Definition at line 60 of file spxfastrt.h.

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