SoPlex
Sequential object-oriented simPlex
Sequential object-oriented simPlex
Harris pricing with shifting.Class SPxHarrisRT is a stable implementation of a SPxRatioTester class along the lines of Harris' two phase algorithm. Additionally it uses shifting of bounds in order to avoid cycling. More...
#include <spxharrisrt.h>
Public Member Functions | |
Construction / destruction | |
| SPxHarrisRT () | |
| default constructor More... | |
| SPxHarrisRT (const SPxHarrisRT &old) | |
| copy constructor More... | |
| SPxHarrisRT & | operator= (const SPxHarrisRT &rhs) |
| assignment operator More... | |
| virtual | ~SPxHarrisRT () |
| destructor More... | |
| virtual SPxRatioTester * | clone () const |
| clone function for polymorphism More... | |
Leave / enter | |
| virtual int | selectLeave (Real &val, Real, bool) |
| virtual SPxId | selectEnter (Real &val, int, bool) |
 Public Member Functions inherited from SPxRatioTester | |
| virtual const char * | getName () const |
| get name of ratio tester. More... | |
| virtual void | load (SPxSolver *p_solver) |
| loads LP. More... | |
| virtual void | clear () |
| unloads LP. More... | |
| virtual SPxSolver * | solver () const |
| returns loaded LP solver. More... | |
| virtual void | setDelta (Real newDelta) |
| set allowed bound violation More... | |
| virtual Real | getDelta () |
| get allowed bound violation More... | |
| virtual void | setType (SPxSolver::Type) |
| sets Simplex type. 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... | |
Private Member Functions | |
Private helpers | |
| Real | degenerateEps () const |
| int | maxDelta (Real *, Real *val, int num, const int *idx, const Real *upd, const Real *vec, const Real *low, const Real *up, Real epsilon) const |
| int | minDelta (Real *, Real *val, int num, const int *idx, const Real *upd, const Real *vec, const Real *low, const Real *up, Real epsilon) const |
Additional Inherited Members | |
| 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... | |
Harris pricing with shifting.
Class SPxHarrisRT is a stable implementation of a SPxRatioTester class along the lines of Harris' two phase algorithm. Additionally it uses shifting of bounds in order to avoid cycling.
See SPxRatioTester for a class documentation.
Definition at line 40 of file spxharrisrt.h.
| SPxHarrisRT | ( | ) |
default constructor
Definition at line 83 of file spxharrisrt.h.
Referenced by SPxHarrisRT::clone().
| SPxHarrisRT | ( | const SPxHarrisRT & | old | ) |
copy constructor
Definition at line 87 of file spxharrisrt.h.
|
virtual |
destructor
Definition at line 101 of file spxharrisrt.h.
|
virtual |
clone function for polymorphism
Implements SPxRatioTester.
Definition at line 104 of file spxharrisrt.h.
References SPxHarrisRT::selectEnter(), SPxHarrisRT::selectLeave(), and SPxHarrisRT::SPxHarrisRT().
|
private |
numCycle and maxCycle are integers. So degeneps will be exactly delta until numCycle >= maxCycle. Then it will be 0 until numCycle >= 2 * maxCycle, after wich it becomes negative. This does not look ok.
Definition at line 33 of file spxharrisrt.cpp.
References SPxSolver::delta(), SPxSolver::maxCycle(), SPxSolver::numCycle(), and SPxRatioTester::solver().
Referenced by SPxHarrisRT::selectEnter(), and SPxHarrisRT::selectLeave().
|
private |
| val | initial and chosen value |
| num | number of indices in idx |
| idx | nonzero indices in upd |
| upd | update vector for vec |
| vec | current vector |
| low | lower bounds for vec |
| up | upper bounds for vec |
| epsilon | what is 0? |
Definition at line 39 of file spxharrisrt.cpp.
References SPxRatioTester::delta, and soplex::infinity.
Referenced by SPxHarrisRT::selectEnter(), and SPxHarrisRT::selectLeave().
|
private |
| val | initial and chosen value |
| num | of indices in idx |
| idx | nonzero indices in upd |
| upd | update vector for vec |
| vec | current vector |
| low | lower bounds for vec |
| up | upper bounds for vec |
| epsilon | what is 0? |
Definition at line 94 of file spxharrisrt.cpp.
References SPxRatioTester::delta, and soplex::infinity.
Referenced by SPxHarrisRT::selectEnter(), and SPxHarrisRT::selectLeave().
| SPxHarrisRT& operator= | ( | const SPxHarrisRT & | rhs | ) |
assignment operator
Definition at line 91 of file spxharrisrt.h.
References SPxRatioTester::operator=().
Implements SPxRatioTester.
Definition at line 344 of file spxharrisrt.cpp.
References SSVectorBase< R >::clearNum(), SPxSolver::coId(), SPxSolver::coPvec(), SPxHarrisRT::degenerateEps(), SPxRatioTester::delta, UpdateVector::delta(), SPxSolver::epsilon(), VectorBase< R >::get_const_ptr(), SPxSolver::id(), SSVectorBase< R >::index(), SSVectorBase< R >::indexMem(), soplex::infinity, SPxId::INVALID, SPxId::inValidate(), SPxSolver::lcBound(), SPxSolver::lpBound(), SPxHarrisRT::maxDelta(), SPxHarrisRT::minDelta(), MSG_DEBUG, SPxSolver::pVec(), SSVectorBase< R >::setup(), SSVectorBase< R >::setValue(), SPxSolver::shift(), SPxSolver::shiftLCbound(), SPxSolver::shiftLPbound(), SPxSolver::shiftUCbound(), SPxSolver::shiftUPbound(), SSVectorBase< R >::size(), SPxRatioTester::solver(), SPxId::type(), SPxSolver::ucBound(), SPxSolver::upBound(), SSVectorBase< R >::values(), and SPxSolver::vector().
Referenced by SPxHarrisRT::clone().
Here comes our implementation of the Harris procedure improved by shifting bounds. The basic idea is to used the tolerated infeasibility within solver()->entertol() for searching numerically stable pivots.
The algorithms operates in two phases. In a first phase, the maximum val is determined, when infeasibility within solver()->entertol() is allowed. In the second phase, between all variables with values < val the one is selected which gives the best step forward in the simplex iteration. However, this may not allways yield an improvement. In that case, we shift the variable toward infeasibility and retry. This avoids cycling in the shifted LP.
Implements SPxRatioTester.
Definition at line 157 of file spxharrisrt.cpp.
References SSVectorBase< R >::clearNum(), SPxHarrisRT::degenerateEps(), SPxRatioTester::delta, UpdateVector::delta(), SPxSolver::epsilon(), SPxSolver::fVec(), VectorBase< R >::get_const_ptr(), SSVectorBase< R >::index(), SSVectorBase< R >::indexMem(), soplex::infinity, SPxSolver::lbBound(), SPxHarrisRT::maxDelta(), SPxHarrisRT::minDelta(), SSVectorBase< R >::setup(), SPxSolver::shift(), SPxSolver::shiftLBbound(), SPxSolver::shiftUBbound(), SSVectorBase< R >::size(), SPxRatioTester::solver(), SPxSolver::ubBound(), and SSVectorBase< R >::values().
Referenced by SPxHarrisRT::clone().