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
	SPxHarrisRT (const SPxHarrisRT &old)
	copy constructor
SPxHarrisRT &	operator= (const SPxHarrisRT &rhs)
	assignment operator
virtual	~SPxHarrisRT ()
	destructor
virtual SPxRatioTester *	clone () const
	clone function for polymorphism
Leave / enter
virtual int	selectLeave (Real &val, SPxId)
virtual SPxId	selectEnter (Real &val, int)
Public Member Functions inherited from SPxRatioTester
virtual const char *	getName () const
	get name of ratio tester.
virtual void	load (SPxSolver *p_solver)
	loads LP.
virtual void	clear ()
	unloads LP.
virtual SPxSolver *	solver () const
	returns loaded LP solver.
virtual void	setDelta (Real newDelta)
	set allowed bound violation
virtual Real	getDelta ()
	get allowed bound violation
virtual void	setType (SPxSolver::Type)
	sets Simplex type.
	SPxRatioTester (const char *name)
	default constructor
	SPxRatioTester (const SPxRatioTester &old)
	copy constructor
SPxRatioTester &	operator= (const SPxRatioTester &rhs)
	assignment operator
virtual	~SPxRatioTester ()
	destructor.

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
const char *	m_name
	name of the ratio tester
SPxSolver::Type	m_type
	internal storage of type
Real	delta
	allowed bound violation

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

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 ~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::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 35 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

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 41 of file spxharrisrt.cpp.

References 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

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 92 of file spxharrisrt.cpp.

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

SPxId selectEnter ( Real &  val, int    )

virtual

Implements SPxRatioTester.

Definition at line 324 of file spxharrisrt.cpp.

References SSVector::clearNum(), SPxSolver::coId(), SPxSolver::coPvec(), SPxHarrisRT::degenerateEps(), SPxRatioTester::delta, UpdateVector::delta(), SPxSolver::epsilon(), Vector::get_const_ptr(), SPxSolver::id(), SSVector::index(), SSVector::indexMem(), soplex::infinity, SPxId::INVALID, SPxId::inValidate(), SPxSolver::lcBound(), SPxSolver::lpBound(), SPxHarrisRT::maxDelta(), SPxHarrisRT::minDelta(), MSG_DEBUG, SPxSolver::pVec(), SSVector::setup(), SSVector::setValue(), SPxSolver::shift(), SPxSolver::shiftLCbound(), SPxSolver::shiftLPbound(), SPxSolver::shiftUCbound(), SPxSolver::shiftUPbound(), SSVector::size(), SPxRatioTester::solver(), soplex::spxout, SPxId::type(), SPxSolver::ucBound(), SPxSolver::upBound(), SSVector::values(), and SPxSolver::vector().

int selectLeave ( Real &  val, SPxId  enterId  )

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 151 of file spxharrisrt.cpp.

References SSVector::clearNum(), SPxHarrisRT::degenerateEps(), SPxRatioTester::delta, UpdateVector::delta(), SPxSolver::epsilon(), SPxSolver::fVec(), Vector::get_const_ptr(), SSVector::index(), SSVector::indexMem(), soplex::infinity, SPxSolver::lbBound(), SPxHarrisRT::maxDelta(), SPxHarrisRT::minDelta(), SSVector::setup(), SPxSolver::shift(), SPxSolver::shiftLBbound(), SPxSolver::shiftUBbound(), SSVector::size(), SPxRatioTester::solver(), SPxSolver::ubBound(), and SSVector::values().