Scippy

SoPlex

Sequential object-oriented simPlex

SPxFastRT< R > Class Template 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 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...
 
 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...
 
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
minStab
 parameter for computing minimum stability requirement More...
 
epsilon
 |value| < epsilon is considered 0. More...
 
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...
 
delta
 allowed bound violation 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 42 of file spxfastrt.h.

Constructor & Destructor Documentation

◆ SPxFastRT() [1/3]

SPxFastRT ( )

default constructor

Definition at line 173 of file spxfastrt.h.

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

◆ SPxFastRT() [2/3]

SPxFastRT ( const SPxFastRT< R > &  old)

copy constructor

Definition at line 181 of file spxfastrt.h.

◆ SPxFastRT() [3/3]

SPxFastRT ( const char *  name)

bound flipping constructor

Definition at line 203 of file spxfastrt.h.

◆ ~SPxFastRT()

virtual ~SPxFastRT ( )
virtual

destructor

Definition at line 211 of file spxfastrt.h.

Member Function Documentation

◆ clone()

virtual SPxRatioTester<R>* clone ( ) const
virtual

◆ getDelta()

virtual R getDelta ( )
virtual

Reimplemented from SPxRatioTester< R >.

Definition at line 241 of file spxfastrt.h.

References SPxFastRT< R >::fastDelta.

◆ load()

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

Reimplemented from SPxRatioTester< R >.

Referenced by SPxFastRT< R >::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.

◆ 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,
maxabs,
const SPxId id,
int  nr,
bool  polish = false 
)
protected

◆ maxReLeave()

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

◆ maxSelect() [1/3]

int maxSelect ( R &  val,
R &  stab,
R &  best,
R &  bestDelta,
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() [2/3]

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

◆ maxSelect() [3/3]

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

◆ maxShortLeave()

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

◆ 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.

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

bool minReLeave ( R &  sel,
int  leave,
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]

int minSelect ( R &  val,
R &  stab,
R &  best,
R &  bestDelta,
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() [2/3]

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

◆ minSelect() [3/3]

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

◆ minShortLeave()

bool minShortLeave ( R &  sel,
int  leave,
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()

R minStability ( maxabs)
protected

Compute stability requirement.

◆ operator=()

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

◆ relax()

void relax ( )
protected

relaxes stability requirements.

◆ 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 >.

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

◆ selectLeave()

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

Implements SPxRatioTester< R >.

Reimplemented in SPxBoundFlippingRT< R >.

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

◆ setDelta()

virtual void setDelta ( newDelta)
virtual

Reimplemented from SPxRatioTester< R >.

Definition at line 232 of file spxfastrt.h.

References DEFAULT_EPS_ZERO, and SPxRatioTester< R >::delta.

◆ setType()

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

Reimplemented from SPxRatioTester< R >.

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

◆ shortEnter()

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

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

◆ tighten()

void tighten ( )
protected

tightens stability requirements.

Member Data Documentation

◆ epsilon

R epsilon
protected

|value| < epsilon is considered 0.

Definition at line 51 of file spxfastrt.h.

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

◆ fastDelta

R fastDelta
protected

currently allowed infeasibility.

Definition at line 53 of file spxfastrt.h.

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

◆ iscoid

bool iscoid
protected

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

Definition at line 55 of file spxfastrt.h.

◆ minStab

R minStab
protected

parameter for computing minimum stability requirement

Definition at line 49 of file spxfastrt.h.

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