SoPlex
Sequential object-oriented simPlex
Sequential object-oriented simPlex
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 * | clone () 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 SPxSolver * | solver () const |
| returns loaded LP solver. 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... | |
| 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 | |
| SPxSolver * | thesolver |
| 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... | |
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.
| SPxFastRT | ( | ) |
copy constructor
Definition at line 180 of file spxfastrt.h.
| SPxFastRT | ( | const char * | name | ) |
bound flipping constructor
Definition at line 202 of file spxfastrt.h.
|
virtual |
destructor
Definition at line 210 of file spxfastrt.h.
|
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().
|
virtual |
Reimplemented from SPxRatioTester.
Definition at line 240 of file spxfastrt.h.
References SPxFastRT::fastDelta.
|
virtual |
Reimplemented from SPxRatioTester.
Definition at line 1487 of file spxfastrt.cpp.
References SPxFastRT::setType(), SPxRatioTester::thesolver, and SPxSolver::type().
Referenced by SPxFastRT::clone().
|
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().
Definition at line 435 of file spxfastrt.cpp.
References SPxSolver::ENTER, SPxSolver::fVec(), SPxSolver::lbBound(), SPxRatioTester::m_type, SPxFastRT::maxDelta(), SPxRatioTester::thesolver, and SPxSolver::ubBound().
Definition at line 453 of file spxfastrt.cpp.
References SPxSolver::coId(), SPxSolver::coPvec(), SPxSolver::id(), SPxFastRT::iscoid, SPxSolver::lcBound(), SPxSolver::lpBound(), SPxFastRT::maxDelta(), SPxSolver::pVec(), SPxRatioTester::thesolver, SPxSolver::ucBound(), and SPxSolver::upBound().
|
protected |
Definition at line 1075 of file spxfastrt.cpp.
References SSVectorBase< R >::clearIdx(), SPxSolver::coPvec(), UpdateVector::delta(), SPxFastRT::fastDelta, SPxSolver::isBasic(), SPxSolver::isCoBasic(), SPxSolver::isCoId(), SPxSolver::isId(), SPxSolver::lcBound(), SPxSolver::lpBound(), SPxSolver::pVec(), SPxSolver::theShift, SPxRatioTester::thesolver, SPxSolver::ucBound(), SPxSolver::upBound(), and SPxSolver::vector().
Referenced by SPxFastRT::selectEnter().
Definition at line 815 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().
|
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().
Definition at line 678 of file spxfastrt.cpp.
References SPxSolver::ENTER, SPxSolver::fVec(), soplex::infinity, SPxSolver::lbBound(), SPxRatioTester::m_type, SPxFastRT::maxSelect(), SPxRatioTester::thesolver, and SPxSolver::ubBound().
Definition at line 691 of file spxfastrt.cpp.
References SPxSolver::coId(), SPxSolver::coPvec(), SPxSolver::id(), soplex::infinity, SPxFastRT::iscoid, SPxSolver::lcBound(), SPxSolver::lpBound(), SPxFastRT::maxSelect(), SPxSolver::pVec(), SPxRatioTester::thesolver, SPxSolver::ucBound(), and SPxSolver::upBound().
Definition at line 771 of file spxfastrt.cpp.
References UpdateVector::delta(), SPxSolver::fVec(), SPxSolver::lbBound(), SHORT, SPxRatioTester::thesolver, and SPxSolver::ubBound().
Referenced by SPxFastRT::selectLeave().
|
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().
Definition at line 444 of file spxfastrt.cpp.
References SPxSolver::ENTER, SPxSolver::fVec(), SPxSolver::lbBound(), SPxRatioTester::m_type, SPxFastRT::minDelta(), SPxRatioTester::thesolver, and SPxSolver::ubBound().
Definition at line 483 of file spxfastrt.cpp.
References SPxSolver::coId(), SPxSolver::coPvec(), SPxSolver::id(), SPxFastRT::iscoid, SPxSolver::lcBound(), SPxSolver::lpBound(), SPxFastRT::minDelta(), SPxSolver::pVec(), SPxRatioTester::thesolver, SPxSolver::ucBound(), and SPxSolver::upBound().
|
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.
Definition at line 1179 of file spxfastrt.cpp.
References SSVectorBase< R >::clearIdx(), SPxSolver::coPvec(), UpdateVector::delta(), SPxFastRT::fastDelta, SPxSolver::isBasic(), SPxSolver::isCoBasic(), SPxSolver::isCoId(), SPxSolver::isId(), SPxSolver::lcBound(), SPxSolver::lpBound(), SPxSolver::pVec(), SPxSolver::theShift, SPxRatioTester::thesolver, SPxSolver::ucBound(), SPxSolver::upBound(), and SPxSolver::vector().
Referenced by SPxFastRT::selectEnter().
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().
|
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().
Definition at line 725 of file spxfastrt.cpp.
References SPxSolver::ENTER, SPxSolver::fVec(), soplex::infinity, SPxSolver::lbBound(), SPxRatioTester::m_type, SPxFastRT::minSelect(), SPxRatioTester::thesolver, and SPxSolver::ubBound().
Definition at line 738 of file spxfastrt.cpp.
References SPxSolver::coId(), SPxSolver::coPvec(), SPxSolver::id(), soplex::infinity, SPxFastRT::iscoid, SPxSolver::lcBound(), SPxSolver::lpBound(), SPxFastRT::minSelect(), SPxSolver::pVec(), SPxRatioTester::thesolver, SPxSolver::ucBound(), and SPxSolver::upBound().
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().
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().
assignment operator
Definition at line 188 of file spxfastrt.h.
References SPxFastRT::epsilon, SPxFastRT::fastDelta, SPxFastRT::minStab, and SPxRatioTester::operator=().
Referenced by SPxBoundFlippingRT::operator=().
|
protected |
relaxes stability requirements.
Definition at line 82 of file spxfastrt.cpp.
References DELTA_SHIFT, SPxFastRT::fastDelta, and SPxFastRT::minStab.
Referenced by SPxFastRT::selectEnter(), SPxBoundFlippingRT::selectEnter(), SPxFastRT::selectLeave(), and SPxBoundFlippingRT::selectLeave().
|
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().
Implements SPxRatioTester.
Reimplemented in SPxBoundFlippingRT.
Definition at line 1319 of file spxfastrt.cpp.
References SPxSolver::basis(), SPxSolver::coPvec(), UpdateVector::delta(), DELTA_SHIFT, SPxFastRT::epsilon, SPxSolver::instableLeave, SPxSolver::integerVariables, SPxSolver::isBasic(), SPxSolver::isCoId(), SPxId::isSPxColId(), SPxId::isSPxRowId(), SPxId::isValid(), SPxBasis::iteration(), SPxSolver::LEAVE, LOWSTAB, SPxRatioTester::m_type, SPxFastRT::maxDelta(), SPxFastRT::maxReEnter(), SPxFastRT::maxSelect(), SPxFastRT::minDelta(), SPxFastRT::minReEnter(), SPxFastRT::minSelect(), SPxFastRT::minStab, SPxFastRT::minStability(), MSG_DEBUG, SPxLPBase< R >::nCols(), SPxLPBase< R >::number(), SPxSolver::POLISH_FRACTIONALITY, SPxSolver::POLISH_INTEGRALITY, SPxSolver::polishObj, SPxSolver::pVec(), SPxFastRT::relax(), SPxSolver::rep(), SPxFastRT::resetTols(), SPxSolver::ROW, SPxFastRT::shortEnter(), DataArray< T >::size(), SPxRatioTester::solver(), SPxRatioTester::thesolver, SPxFastRT::tighten(), and TRIES.
Referenced by SPxFastRT::clone(), and SPxBoundFlippingRT::selectEnter().
Implements SPxRatioTester.
Reimplemented in SPxBoundFlippingRT.
Definition at line 899 of file spxfastrt.cpp.
References SPxBasis::baseId(), SPxSolver::basis(), SPxBasis::Desc::colStatus(), SPxSolver::COLUMN, UpdateVector::delta(), DELTA_SHIFT, SPxBasis::desc(), SPxSolver::ENTER, SPxFastRT::epsilon, SPxSolver::epsilon(), SPxSolver::fVec(), SPxSolver::instableEnter, SPxSolver::integerVariables, SPxId::isSPxColId(), SPxBasis::iteration(), LOWSTAB, SPxRatioTester::m_type, SPxFastRT::maxDelta(), SPxFastRT::maxReLeave(), SPxFastRT::maxSelect(), SPxFastRT::maxShortLeave(), SPxFastRT::minDelta(), SPxFastRT::minReLeave(), SPxFastRT::minSelect(), SPxFastRT::minShortLeave(), SPxFastRT::minStab, SPxFastRT::minStability(), MSG_DEBUG, SPxLPBase< R >::nCols(), SPxLPBase< R >::number(), SPxBasis::Desc::P_FIXED, SPxSolver::POLISH_FRACTIONALITY, SPxSolver::POLISH_INTEGRALITY, SPxSolver::polishObj, SPxFastRT::relax(), SPxSolver::rep(), SPxFastRT::resetTols(), DataArray< T >::size(), SPxRatioTester::solver(), SPxBasis::stability(), SPxRatioTester::thesolver, SPxFastRT::tighten(), TRIES, and SPxSolver::value().
Referenced by SPxFastRT::clone(), and SPxBoundFlippingRT::selectLeave().
|
virtual |
Reimplemented from SPxRatioTester.
Definition at line 231 of file spxfastrt.h.
References DEFAULT_EPS_ZERO, and SPxRatioTester::delta.
|
virtual |
Reimplemented from SPxRatioTester.
Definition at line 1493 of file spxfastrt.cpp.
References SPxRatioTester::delta, SPxFastRT::fastDelta, SPxRatioTester::m_type, MINSTAB, and SPxFastRT::minStab.
Referenced by SPxFastRT::clone(), and SPxFastRT::load().
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().
|
protected |
tightens stability requirements.
Definition at line 58 of file spxfastrt.cpp.
References SPxRatioTester::delta, DELTA_SHIFT, SPxFastRT::fastDelta, MINSTAB, and SPxFastRT::minStab.
Referenced by SPxFastRT::selectEnter(), SPxBoundFlippingRT::selectEnter(), SPxFastRT::selectLeave(), and SPxBoundFlippingRT::selectLeave().
|
protected |
|value| < epsilon is considered 0.
Definition at line 50 of file spxfastrt.h.
Referenced by SPxBoundFlippingRT::collectBreakpointsMax(), SPxBoundFlippingRT::collectBreakpointsMin(), SPxFastRT::maxDelta(), SPxFastRT::minDelta(), SPxFastRT::operator=(), SPxFastRT::resetTols(), SPxFastRT::selectEnter(), and SPxFastRT::selectLeave().
|
protected |
currently allowed infeasibility.
Definition at line 52 of file spxfastrt.h.
Referenced by SPxBoundFlippingRT::collectBreakpointsMax(), SPxBoundFlippingRT::collectBreakpointsMin(), SPxFastRT::getDelta(), SPxFastRT::maxDelta(), SPxFastRT::maxReEnter(), SPxFastRT::maxReLeave(), SPxFastRT::minDelta(), SPxFastRT::minReEnter(), SPxFastRT::minReLeave(), SPxFastRT::operator=(), SPxFastRT::relax(), SPxBoundFlippingRT::selectEnter(), SPxBoundFlippingRT::selectLeave(), SPxFastRT::setType(), and SPxFastRT::tighten().
|
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().
|
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().