|
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>
|
|
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...
|
|
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.
bound flipping constructor
Definition at line 201 of file spxfastrt.h.
virtual Real getDelta |
( |
| ) |
|
|
virtual |
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 |
Definition at line 429 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().
bool maxReEnter |
( |
Real & |
sel, |
|
|
Real |
maxabs, |
|
|
const SPxId & |
id, |
|
|
int |
nr |
|
) |
| |
|
protected |
Definition at line 971 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().
bool maxReLeave |
( |
Real & |
sel, |
|
|
int |
leave, |
|
|
Real |
maxabs |
|
) |
| |
|
protected |
Definition at line 779 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().
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().
Definition at line 659 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().
bool maxShortLeave |
( |
Real & |
sel, |
|
|
int |
leave, |
|
|
Real |
maxabs |
|
) |
| |
|
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 |
Definition at line 457 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().
bool minReEnter |
( |
Real & |
sel, |
|
|
Real |
maxabs, |
|
|
const SPxId & |
id, |
|
|
int |
nr |
|
) |
| |
|
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 1063 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().
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().
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().
Definition at line 704 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().
bool minShortLeave |
( |
Real & |
sel, |
|
|
int |
leave, |
|
|
Real |
maxabs |
|
) |
| |
|
protected |
Implements SPxRatioTester.
Reimplemented in SPxBoundFlippingRT.
Definition at line 1183 of file spxfastrt.cpp.
References SPxSolver::basis(), SPxSolver::coPvec(), UpdateVector::delta(), DELTA_SHIFT, SPxFastRT::epsilon, SPxSolver::instableLeave, SPxSolver::isBasic(), SPxSolver::isCoId(), 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 >::number(), SPxSolver::pVec(), SPxFastRT::relax(), SPxFastRT::resetTols(), SPxFastRT::shortEnter(), SPxRatioTester::solver(), SPxRatioTester::thesolver, SPxFastRT::tighten(), and TRIES.
Referenced by SPxFastRT::clone(), and SPxBoundFlippingRT::selectEnter().
Implements SPxRatioTester.
Reimplemented in SPxBoundFlippingRT.
Definition at line 849 of file spxfastrt.cpp.
References SPxBasis::baseId(), SPxSolver::basis(), SPxBasis::Desc::colStatus(), UpdateVector::delta(), DELTA_SHIFT, SPxBasis::desc(), SPxSolver::ENTER, SPxFastRT::epsilon, SPxSolver::epsilon(), SPxSolver::fVec(), SPxSolver::instableEnter, 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 >::number(), SPxBasis::Desc::P_FIXED, SPxFastRT::relax(), SPxFastRT::resetTols(), SPxRatioTester::solver(), SPxBasis::stability(), SPxRatioTester::thesolver, SPxFastRT::tighten(), TRIES, and SPxSolver::value().
Referenced by SPxFastRT::clone(), and SPxBoundFlippingRT::selectLeave().
virtual void setDelta |
( |
Real |
newDelta | ) |
|
|
virtual |
bool shortEnter |
( |
const SPxId & |
enterId, |
|
|
int |
nr, |
|
|
Real |
max, |
|
|
Real |
maxabs |
|
) |
| const |
|
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().
|