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:

[legend]

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)

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

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

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

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

SPxId selectEnter	(	Real &	val,
		int
	)

virtual

Implements SPxRatioTester.

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

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

SoPlex

Public Member Functions

Private Member Functions

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation