Scippy

SoPlex

Sequential object-oriented simPlex

SPxHarrisRT Class Reference

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>

Inheritance diagram for SPxHarrisRT:

Public Member Functions

Construction / destruction
 SPxHarrisRT ()
 default constructor More...
 
 SPxHarrisRT (const SPxHarrisRT &old)
 copy constructor More...
 
SPxHarrisRToperator= (const SPxHarrisRT &rhs)
 assignment operator More...
 
virtual ~SPxHarrisRT ()
 destructor More...
 
virtual SPxRatioTesterclone () const
 clone function for polymorphism More...
 
Leave / enter
virtual int selectLeave (Real &val, Real)
 
virtual SPxId selectEnter (Real &val, int)
 
- 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 SPxSolversolver () 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...
 
SPxRatioTesteroperator= (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
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

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.

Todo:
HarrisRT leads to cycling in dcmulti.sub.lp

Definition at line 40 of file spxharrisrt.h.

Constructor & Destructor Documentation

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 ~SPxHarrisRT ( )
virtual

destructor

Definition at line 101 of file spxharrisrt.h.

Member Function Documentation

virtual SPxRatioTester* clone ( ) const
virtual

clone function for polymorphism

Implements SPxRatioTester.

Definition at line 104 of file spxharrisrt.h.

References SPxHarrisRT::selectEnter(), SPxHarrisRT::selectLeave(), and SPxHarrisRT::SPxHarrisRT().

Real degenerateEps ( ) const
private
Todo:
suspicious: *max is not set, but it is used (with the default setting *max=1) in selectLeave and selectEnter The question might be if max shouldn't be updated with themax?

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

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
private
Todo:
patch suggests using *max instead of themax
Parameters
valinitial and chosen value
numnumber of indices in idx
idxnonzero indices in upd
updupdate vector for vec
veccurrent vector
lowlower bounds for vec
upupper bounds for vec
epsilonwhat is 0?

Definition at line 39 of file spxharrisrt.cpp.

References SPxRatioTester::delta, and soplex::infinity.

Referenced by SPxHarrisRT::selectEnter(), and SPxHarrisRT::selectLeave().

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
private
Todo:
suspicious: *max is not set, but it is used (with the default setting *max=1) in selectLeave and selectEnter
Todo:
patch suggests using *max instead of themax
Parameters
valinitial and chosen value
numof indices in idx
idxnonzero indices in upd
updupdate vector for vec
veccurrent vector
lowlower bounds for vec
upupper bounds for vec
epsilonwhat is 0?

Definition at line 90 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=().

int selectLeave ( Real val,
Real   
)
virtual

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