Scippy

SoPlex

Sequential object-oriented simPlex

SPxFastRT Class Reference

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...
 
SPxFastRToperator= (const SPxFastRT &rhs)
 assignment operator More...
 
 SPxFastRT (const char *name)
 bound flipping constructor More...
 
virtual ~SPxFastRT ()
 destructor More...
 
virtual SPxRatioTesterclone () const
 clone function for polymorphism More...
 
Access / modification
virtual void load (SPxSolver *solver)
 
virtual int selectLeave (Real &val, Real, bool polish=false)
 
virtual SPxId selectEnter (Real &val, int, bool polish=false)
 
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. More...
 
virtual void clear ()
 unloads LP. More...
 
virtual SPxSolversolver () const
 returns loaded LP solver. More...
 
 SPxRatioTester (const char *name)
 default constructor More...
 
 SPxRatioTester (const SPxRatioTester &old)
 copy constructor More...
 
SPxRatioTesteroperator= (const SPxRatioTester &rhs)
 assignment operator More...
 
virtual ~SPxRatioTester ()
 destructor. More...
 

Protected Member Functions

Private helpers
void resetTols ()
 resets tolerances (epsilon). More...
 
void relax ()
 relaxes stability requirements. More...
 
void tighten ()
 tightens stability requirements. More...
 
Real minStability (Real maxabs)
 Compute stability requirement. More...
 
int maxDelta (Real &val, Real &maxabs, UpdateVector &update, const Vector &lowBound, const Vector &upBound, int start, int incr) const
 Max phase 1 value. More...
 
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. More...
 
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. More...
 
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. More...
 
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. More...
 
bool maxShortLeave (Real &sel, int leave, Real maxabs)
 
bool minReLeave (Real &sel, int leave, Real maxabs, bool polish=false)
 numerical stability tests. More...
 
bool maxReLeave (Real &sel, int leave, Real maxabs, bool polish=false)
 
bool minReEnter (Real &sel, Real maxabs, const SPxId &id, int nr, bool polish=false)
 numerical stability check. More...
 
bool maxReEnter (Real &sel, Real maxabs, const SPxId &id, int nr, bool polish=false)
 
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. More...
 

Protected Attributes

Data
Real minStab
 parameter for computing minimum stability requirement More...
 
Real epsilon
 |value| < epsilon is considered 0. More...
 
Real fastDelta
 currently allowed infeasibility. More...
 
bool iscoid
 flag used in methods minSelect/maxSelect to retrieve correct basis status More...
 
- Protected Attributes inherited from SPxRatioTester
SPxSolverthesolver
 the solver More...
 
const char * m_name
 name of the ratio tester More...
 
SPxSolver::Type m_type
 internal storage of type More...
 
Real delta
 allowed bound violation More...
 

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() [1/3]

SPxFastRT ( )

default constructor

Definition at line 172 of file spxfastrt.h.

Referenced by SPxFastRT::clone().

◆ SPxFastRT() [2/3]

SPxFastRT ( const SPxFastRT old)

copy constructor

Definition at line 180 of file spxfastrt.h.

◆ SPxFastRT() [3/3]

SPxFastRT ( const char *  name)

bound flipping constructor

Definition at line 202 of file spxfastrt.h.

◆ ~SPxFastRT()

virtual ~SPxFastRT ( )
virtual

destructor

Definition at line 210 of file spxfastrt.h.

Member Function Documentation

◆ clone()

virtual SPxRatioTester* clone ( ) const
virtual

clone function for polymorphism

Implements SPxRatioTester.

Reimplemented in SPxBoundFlippingRT.

Definition at line 213 of file spxfastrt.h.

References SPxFastRT::load(), SPxFastRT::selectEnter(), SPxFastRT::selectLeave(), SPxFastRT::setType(), SPxRatioTester::solver(), and SPxFastRT::SPxFastRT().

◆ getDelta()

virtual Real getDelta ( )
virtual

Reimplemented from SPxRatioTester.

Definition at line 240 of file spxfastrt.h.

References SPxFastRT::fastDelta.

◆ load()

void load ( SPxSolver solver)
virtual

Reimplemented from SPxRatioTester.

Definition at line 1487 of file spxfastrt.cpp.

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

Referenced by SPxFastRT::clone().

◆ maxDelta() [1/3]

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 104 of file spxfastrt.cpp.

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

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

◆ maxDelta() [2/3]

int maxDelta ( Real val,
Real maxabs 
)
protected

◆ maxDelta() [3/3]

◆ maxReEnter()

◆ maxReLeave()

◆ maxSelect() [1/3]

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 597 of file spxfastrt.cpp.

References UpdateVector::delta(), VectorBase< R >::get_const_ptr(), SSVectorBase< R >::indexMem(), SPxSolver::isBasic(), SPxSolver::isCoBasic(), SPxFastRT::iscoid, SPxSolver::LEAVE, SPxRatioTester::m_type, SSVectorBase< R >::size(), SPxRatioTester::thesolver, and SSVectorBase< R >::values().

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

◆ maxSelect() [2/3]

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

◆ maxSelect() [3/3]

◆ maxShortLeave()

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

◆ minDelta() [1/3]

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 270 of file spxfastrt.cpp.

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

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

◆ minDelta() [2/3]

int minDelta ( Real val,
Real maxabs 
)
protected

◆ minDelta() [3/3]

◆ minReEnter()

bool minReEnter ( Real sel,
Real  maxabs,
const SPxId id,
int  nr,
bool  polish = false 
)
protected

◆ minReLeave()

bool minReLeave ( Real sel,
int  leave,
Real  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.

Definition at line 857 of file spxfastrt.cpp.

References SPxBasis::baseId(), SPxBasis::Desc::D_ON_BOTH, UpdateVector::delta(), SPxBasis::dualStatus(), SPxFastRT::fastDelta, SPxSolver::fVec(), SPxSolver::lbBound(), SPxSolver::shiftLBbound(), SPxSolver::shiftUBbound(), SPxRatioTester::thesolver, and SPxSolver::ubBound().

Referenced by SPxFastRT::selectLeave().

◆ minSelect() [1/3]

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 516 of file spxfastrt.cpp.

References UpdateVector::delta(), VectorBase< R >::get_const_ptr(), SSVectorBase< R >::indexMem(), SPxSolver::isBasic(), SPxSolver::isCoBasic(), SPxFastRT::iscoid, SPxSolver::LEAVE, SPxRatioTester::m_type, SSVectorBase< R >::size(), SPxRatioTester::thesolver, and SSVectorBase< R >::values().

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

◆ minSelect() [2/3]

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

◆ minSelect() [3/3]

◆ minShortLeave()

bool minShortLeave ( Real sel,
int  leave,
Real  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.

Definition at line 793 of file spxfastrt.cpp.

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

Referenced by SPxFastRT::selectLeave().

◆ minStability()

Real minStability ( Real  maxabs)
protected

Compute stability requirement.

Definition at line 89 of file spxfastrt.cpp.

References SPxFastRT::minStab.

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

◆ operator=()

SPxFastRT& operator= ( const SPxFastRT rhs)

assignment operator

Definition at line 188 of file spxfastrt.h.

References SPxFastRT::epsilon, SPxFastRT::fastDelta, SPxFastRT::minStab, and SPxRatioTester::operator=().

Referenced by SPxBoundFlippingRT::operator=().

◆ relax()

void relax ( )
protected

◆ resetTols()

void resetTols ( )
protected

resets tolerances (epsilon).

Definition at line 48 of file spxfastrt.cpp.

References EPSILON, and SPxFastRT::epsilon.

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

◆ selectEnter()

◆ selectLeave()

◆ setDelta()

virtual void setDelta ( Real  newDelta)
virtual

Reimplemented from SPxRatioTester.

Definition at line 231 of file spxfastrt.h.

References DEFAULT_EPS_ZERO, and SPxRatioTester::delta.

◆ setType()

void setType ( SPxSolver::Type  type)
virtual

◆ shortEnter()

bool shortEnter ( const SPxId enterId,
int  nr,
Real  max,
Real  maxabs 
) const
protected

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

Definition at line 1285 of file spxfastrt.cpp.

References SPxSolver::coPvec(), UpdateVector::delta(), SPxSolver::isCoId(), SPxSolver::isId(), SPxSolver::pVec(), SHORT, and SPxRatioTester::thesolver.

Referenced by SPxFastRT::selectEnter().

◆ tighten()

void tighten ( )
protected

Member Data Documentation

◆ epsilon

◆ fastDelta

◆ iscoid

bool iscoid
protected

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

Definition at line 54 of file spxfastrt.h.

Referenced by SPxFastRT::maxDelta(), SPxFastRT::maxSelect(), SPxFastRT::minDelta(), and SPxFastRT::minSelect().

◆ minStab

Real minStab
protected

parameter for computing minimum stability requirement

Definition at line 48 of file spxfastrt.h.

Referenced by SPxFastRT::minStability(), SPxFastRT::operator=(), SPxFastRT::relax(), SPxFastRT::selectEnter(), SPxFastRT::selectLeave(), SPxFastRT::setType(), and SPxFastRT::tighten().