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>

Inheritance diagram for SPxFastRT:

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)
 
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. 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)
 numerical stability tests. More...
 
bool maxReLeave (Real &sel, int leave, Real maxabs)
 
bool minReEnter (Real &sel, Real maxabs, const SPxId &id, int nr)
 numerical stability check. More...
 
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. 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 ( )

default constructor

Definition at line 171 of file spxfastrt.h.

Referenced by SPxFastRT::clone().

SPxFastRT ( const SPxFastRT old)

copy constructor

Definition at line 179 of file spxfastrt.h.

SPxFastRT ( const char *  name)

bound flipping constructor

Definition at line 201 of file spxfastrt.h.

virtual ~SPxFastRT ( )
virtual

destructor

Definition at line 209 of file spxfastrt.h.

Member Function Documentation

virtual SPxRatioTester* clone ( ) const
virtual

clone function for polymorphism

Implements SPxRatioTester.

Reimplemented in SPxBoundFlippingRT.

Definition at line 212 of file spxfastrt.h.

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

virtual Real getDelta ( )
virtual

Reimplemented from SPxRatioTester.

Definition at line 238 of file spxfastrt.h.

References SPxFastRT::fastDelta.

void load ( SPxSolver solver)
virtual

Reimplemented from SPxRatioTester.

Definition at line 1310 of file spxfastrt.cpp.

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

Referenced by SPxFastRT::clone().

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 101 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().

int maxDelta ( Real val,
Real maxabs 
)
protected
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(), 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().

int maxSelect ( Real val,
Real stab,
Real bestDelta,
Real  max 
)
protected
bool maxShortLeave ( Real sel,
int  leave,
Real  maxabs 
)
protected
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 256 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().

int minDelta ( Real val,
Real maxabs 
)
protected
bool minReEnter ( Real sel,
Real  maxabs,
const SPxId id,
int  nr 
)
protected
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 814 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().

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(), 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().

int minSelect ( Real val,
Real stab,
Real bestDelta,
Real  max 
)
protected
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 757 of file spxfastrt.cpp.

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

Referenced by SPxFastRT::selectLeave().

Real minStability ( Real  maxabs)
protected

Compute stability requirement.

Definition at line 87 of file spxfastrt.cpp.

References SPxFastRT::minStab.

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

SPxFastRT& operator= ( const SPxFastRT rhs)

assignment operator

Definition at line 187 of file spxfastrt.h.

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

Referenced by SPxBoundFlippingRT::operator=().

void relax ( )
protected
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().

virtual void setDelta ( Real  newDelta)
virtual

Reimplemented from SPxRatioTester.

Definition at line 230 of file spxfastrt.h.

References DEFAULT_EPS_ZERO, and SPxRatioTester::delta.

void setType ( SPxSolver::Type  type)
virtual
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 1153 of file spxfastrt.cpp.

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

Referenced by SPxFastRT::selectEnter().

void tighten ( )
protected

Member Data Documentation

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().

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().