SPxBoundFlippingRT Class Reference

Bound flipping ratio test ("long step dual") for SoPlex.Class SPxBoundFlippingRT provides an implementation of the bound flipping ratio test as a derived class of SPxRatioTester. Dual step length is increased beyond some breakpoints and corresponding primal nonbasic variables are set to their other bound to handle the resulting dual infeasibility. More...

#include <spxboundflippingrt.h>

Inheritance diagram for SPxBoundFlippingRT:

Classes
struct	Breakpoint
struct	BreakpointCompare

Public Member Functions
Construction / destruction
	SPxBoundFlippingRT ()
	default constructor More...
	SPxBoundFlippingRT (const SPxBoundFlippingRT &old)
	copy constructor More...
SPxBoundFlippingRT &	operator= (const SPxBoundFlippingRT &rhs)
	assignment operator More...
virtual	~SPxBoundFlippingRT ()
	destructor More...
virtual SPxRatioTester *	clone () const
	clone function for polymorphism More...
Select enter/leave
virtual int	selectLeave (Real &val, Real enterTest)
virtual SPxId	selectEnter (Real &val, int leaveIdx)
void	useBoundFlips (bool bf)
void	useBoundFlipsRow (bool bf)
Public Member Functions inherited from SPxFastRT
	SPxFastRT ()
	default constructor More...
	SPxFastRT (const SPxFastRT &old)
	copy constructor More...
SPxFastRT &	operator= (const SPxFastRT &rhs)
	assignment operator More...
	SPxFastRT (const char *name)
	bound flipping constructor More...
virtual	~SPxFastRT ()
	destructor More...
virtual void	load (SPxSolver *solver)
virtual void	setType (SPxSolver::Type type)
virtual void	setDelta (Real newDelta)
virtual Real	getDelta ()
Public Member Functions inherited from SPxRatioTester
virtual const char *	getName () const
	get name of ratio tester. More...
virtual void	clear ()
	unloads LP. More...
virtual SPxSolver *	solver () const
	returns loaded LP solver. 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 Types
substructures
enum	BreakpointSource { FVEC = -1, PVEC = 0, COPVEC = 1 }

Private Member Functions
void	collectBreakpointsMax (int &nBp, int &minIdx, const int *idx, int nnz, const Real *upd, const Real *vec, const Real *upp, const Real *low, BreakpointSource src)
void	collectBreakpointsMin (int &nBp, int &minIdx, const int *idx, int nnz, const Real *upd, const Real *vec, const Real *upp, const Real *low, BreakpointSource src)
bool	getData (Real &val, SPxId &enterId, int idx, Real stab, Real degeneps, const Real *upd, const Real *vec, const Real *low, const Real *upp, BreakpointSource src, Real max)
bool	getData (Real &val, int &leaveIdx, int idx, Real stab, Real degeneps, const Real *upd, const Real *vec, const Real *low, const Real *upp, BreakpointSource src, Real max)
void	flipAndUpdate (int &usedBp)

Static Private Member Functions
static bool	isSmaller (Breakpoint x, Breakpoint y)

Private Attributes
Data
bool	enableBoundFlips
bool	enableRowBoundFlips
Real	flipPotential
int	relax_count
DataArray< Breakpoint >	breakpoints
SSVector	updPrimRhs
SSVector	updPrimVec

Additional Inherited Members
Protected Member Functions inherited from SPxFastRT
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...
Protected Attributes inherited from SPxFastRT
Real	minStab
	parameter for computing minimum stability requirement More...
Real	epsilon
	|value| < epsilon is considered 0. More...
Real	fastDelta
	currently allowed infeasibility. More...
bool	iscoid
	flag used in methods minSelect/maxSelect to retrieve correct basis status More...
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

Bound flipping ratio test ("long step dual") for SoPlex.

Class SPxBoundFlippingRT provides an implementation of the bound flipping ratio test as a derived class of SPxRatioTester. Dual step length is increased beyond some breakpoints and corresponding primal nonbasic variables are set to their other bound to handle the resulting dual infeasibility.

The implementation mostly follows the papers

• I. Maros, "A generalized dual phase-2 simplex algorithm", European Journal of Operational Research Vol 149, Issue 1, pp. 1-16, 2003
• A. Koberstein, "Progress in the dual simplex algorithm for solving large scale LP problems: techniques for a fast and stable implementation", Computational Optimization and Applications Vol 41, Nr 2, pp. 185-204, 2008

See SPxRatioTester for a class documentation.

Definition at line 51 of file spxboundflippingrt.h.

Member Enumeration Documentation

enum BreakpointSource

private

enumerator to remember which vector we have been searching to find a breakpoint

Enumerator
FVEC
PVEC
COPVEC

Definition at line 58 of file spxboundflippingrt.h.

Constructor & Destructor Documentation

SPxBoundFlippingRT

(

)

default constructor

Definition at line 186 of file spxboundflippingrt.h.

Referenced by SPxBoundFlippingRT::clone().

SPxBoundFlippingRT

(

const SPxBoundFlippingRT &

old

)

copy constructor

Definition at line 197 of file spxboundflippingrt.h.

virtual ~SPxBoundFlippingRT ( )

virtual

destructor

Definition at line 222 of file spxboundflippingrt.h.

Member Function Documentation

virtual SPxRatioTester* clone ( ) const

virtual

clone function for polymorphism

Reimplemented from SPxFastRT.

Definition at line 225 of file spxboundflippingrt.h.

References SPxBoundFlippingRT::selectEnter(), SPxBoundFlippingRT::selectLeave(), SPxBoundFlippingRT::SPxBoundFlippingRT(), and SPxBoundFlippingRT::Breakpoint::val.

void collectBreakpointsMax ( int &  nBp, int &  minIdx, const int *  idx, int  nnz, const Real *  upd, const Real *  vec, const Real *  upp, const Real *  low, BreakpointSource  src  )

private

store all available pivots/breakpoints in an array (positive pivot search direction)

Parameters

nBp	number of found breakpoints so far
minIdx	index to current minimal breakpoint
idx	pointer to indices of current vector
nnz	number of nonzeros in current vector
upd	pointer to update values of current vector
vec	pointer to values of current vector
upp	pointer to upper bound/rhs of current vector
low	pointer to lower bound/lhs of current vector
src	type of vector (pVec or coPvec)

Definition at line 277 of file spxboundflippingrt.cpp.

References SPxBoundFlippingRT::breakpoints, SPxFastRT::epsilon, SPxFastRT::fastDelta, and soplex::infinity.

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

void collectBreakpointsMin ( int &  nBp, int &  minIdx, const int *  idx, int  nnz, const Real *  upd, const Real *  vec, const Real *  upp, const Real *  low, BreakpointSource  src  )

private

store all available pivots/breakpoints in an array (negative pivot search direction)

Parameters

nBp	number of found breakpoints so far
minIdx	index to current minimal breakpoint
idx	pointer to indices of current vector
nnz	number of nonzeros in current vector
upd	pointer to update values of current vector
vec	pointer to values of current vector
upp	pointer to upper bound/rhs of current vector
low	pointer to lower bound/lhs of current vector
src	type of vector (pVec or coPvec)

Definition at line 350 of file spxboundflippingrt.cpp.

References SPxBoundFlippingRT::breakpoints, SPxFastRT::epsilon, SPxFastRT::fastDelta, and soplex::infinity.

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

void flipAndUpdate ( int &  nflips )

private

perform necessary bound flips to restore dual feasibility

Parameters

nflips

number of bounds that should be flipped

Definition at line 33 of file spxboundflippingrt.cpp.

References SSVectorBase< R >::add(), SPxBasis::baseId(), SPxSolver::basis(), SPxBoundFlippingRT::breakpoints, SSVectorBase< R >::clear(), SPxBasis::Desc::colStatus(), SPxSolver::COLUMN, SPxBoundFlippingRT::COPVEC, SPxSolver::coPvec(), SPxBasis::Desc::coStatus(), UpdateVector::delta(), SPxBasis::desc(), SPxSolver::dim(), SPxSolver::ENTER, SPxBoundFlippingRT::FVEC, SPxSolver::fVec(), soplex::infinity, SPxSolver::LEAVE, SPxLPBase< R >::lhs(), SPxLPBase< R >::lower(), SPxRatioTester::m_type, MSG_DEBUG, MSG_WARNING, SSVectorBase< R >::multAdd(), SPxLPBase< R >::number(), SPxBasis::Desc::P_ON_LOWER, SPxBasis::Desc::P_ON_UPPER, SPxBoundFlippingRT::PVEC, SPxSolver::pVec(), SSVectorBase< R >::reDim(), SPxSolver::rep(), SPxLPBase< R >::rhs(), SPxSolver::ROW, SPxBasis::Desc::rowStatus(), SSVectorBase< R >::setup(), SPxSolver::setup4coSolve2(), SPxSolver::setup4solve2(), SSVectorBase< R >::setValue(), soplex::spxAbs(), SPxSolver::spxout, SPxBasis::Desc::status(), SPxSolver::theCoLbound, SPxSolver::theCoPrhs, SPxSolver::theCoUbound, SPxSolver::theFrhs, SPxSolver::theLBbound, SPxSolver::theLbound, SPxSolver::theLCbound, SPxSolver::theLRbound, SPxRatioTester::thesolver, SPxSolver::theUBbound, SPxSolver::theUbound, SPxSolver::theUCbound, SPxSolver::theURbound, SPxSolver::updateNonbasicValue(), SPxBoundFlippingRT::updPrimRhs, SPxBoundFlippingRT::updPrimVec, SPxLPBase< R >::upper(), and SPxSolver::vector().

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

bool getData ( Real &  val, SPxId &  enterId, int  idx, Real  stab, Real  degeneps, const Real *  upd, const Real *  vec, const Real *  low, const Real *  upp, BreakpointSource  src, Real  max  )

private

get values for entering index and perform shifts if necessary

Definition at line 424 of file spxboundflippingrt.cpp.

References SPxSolver::coId(), SPxSolver::coPvec(), SPxSolver::id(), SPxSolver::lcBound(), SPxSolver::lpBound(), SPxBoundFlippingRT::PVEC, SPxSolver::pVec(), SPxSolver::shiftLCbound(), SPxSolver::shiftLPbound(), SPxSolver::shiftUCbound(), SPxSolver::shiftUPbound(), soplex::spxAbs(), SPxSolver::theShift, SPxRatioTester::thesolver, SPxSolver::ucBound(), SPxSolver::upBound(), and SPxSolver::vector().

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

bool getData ( Real &  val, int &  leaveIdx, int  idx, Real  stab, Real  degeneps, const Real *  upd, const Real *  vec, const Real *  low, const Real *  upp, BreakpointSource  src, Real  max  )

private

get values for leaving index and perform shifts if necessary

Definition at line 500 of file spxboundflippingrt.cpp.

References SPxBasis::baseId(), SPxBasis::Desc::D_ON_BOTH, SPxBasis::dualStatus(), SPxBoundFlippingRT::FVEC, SPxSolver::shiftLBbound(), SPxSolver::shiftUBbound(), soplex::spxAbs(), and SPxRatioTester::thesolver.

static bool isSmaller ( Breakpoint  x, Breakpoint  y  )

staticprivate

comparison method for breakpoints

Definition at line 172 of file spxboundflippingrt.h.

References soplex::spxAbs(), and SPxBoundFlippingRT::Breakpoint::val.

SPxBoundFlippingRT& operator=

(

const SPxBoundFlippingRT &

rhs

)

assignment operator

Definition at line 208 of file spxboundflippingrt.h.

References SPxBoundFlippingRT::enableBoundFlips, SPxBoundFlippingRT::enableRowBoundFlips, SPxBoundFlippingRT::flipPotential, and SPxFastRT::operator=().

SPxId selectEnter ( Real &  val, int  leaveIdx  )

virtual

determine entering row/column

Reimplemented from SPxFastRT.

Definition at line 546 of file spxboundflippingrt.cpp.

References SPxSolver::basis(), SPxSolver::boundflips, SPxBoundFlippingRT::breakpoints, SSVectorBase< R >::clearIdx(), SPxBoundFlippingRT::collectBreakpointsMax(), SPxBoundFlippingRT::collectBreakpointsMin(), SPxBoundFlippingRT::COPVEC, SPxSolver::coPvec(), SPxRatioTester::delta, UpdateVector::delta(), SPxBoundFlippingRT::enableBoundFlips, SPxBoundFlippingRT::BreakpointCompare::entry, SPxFastRT::fastDelta, SPxBoundFlippingRT::flipAndUpdate(), SPxBoundFlippingRT::flipPotential, SPxSolver::fTest(), VectorBase< R >::get_const_ptr(), SPxBoundFlippingRT::getData(), SSVectorBase< R >::indexMem(), SPxSolver::instableLeave, SPxSolver::instableLeaveNum, SPxSolver::instableLeaveVal, SPxSolver::isBasic(), SPxSolver::isCoBasic(), SPxId::isValid(), SPxBasis::iteration(), SPxSolver::lcBound(), SPxSolver::LEAVE, SPxSolver::leaveCount, SPxLPBase< R >::lhs(), LONGSTEP_FREQ, SPxLPBase< R >::lower(), LOWSTAB, SPxSolver::lpBound(), SPxRatioTester::m_type, MAX_RELAX_COUNT, SPxFastRT::minStability(), MSG_DEBUG, SPxBoundFlippingRT::PVEC, SPxSolver::pVec(), SPxFastRT::relax(), SPxBoundFlippingRT::relax_count, SPxSolver::rep(), SPxFastRT::resetTols(), SPxLPBase< R >::rhs(), SPxSolver::ROW, SPxFastRT::selectEnter(), SSVectorBase< R >::size(), soplex::spxAbs(), soplex::SPxQuicksortPart(), SPxRatioTester::thesolver, SPxFastRT::tighten(), SPxSolver::ucBound(), SPxSolver::upBound(), SPxLPBase< R >::upper(), SSVectorBase< R >::values(), and SPxSolver::vector().

Referenced by SPxBoundFlippingRT::clone().

int selectLeave ( Real &  val, Real  enterTest  )

virtual

determine leaving row/column

< pointer to values of current vector

< pointer to update values of current vector

< pointer to indices of current vector

< number of nonzeros in update vector

< pointer to lower bound/lhs of current vector

< pointer to upper bound/rhs of current vector

Reimplemented from SPxFastRT.

Definition at line 888 of file spxboundflippingrt.cpp.

References SPxBasis::baseId(), SPxSolver::basis(), SPxSolver::boundflips, SPxBoundFlippingRT::breakpoints, SPxBoundFlippingRT::collectBreakpointsMax(), SPxBoundFlippingRT::collectBreakpointsMin(), SPxSolver::COLUMN, SPxRatioTester::delta, UpdateVector::delta(), SPxBoundFlippingRT::enableBoundFlips, SPxBoundFlippingRT::enableRowBoundFlips, SPxSolver::ENTER, SPxSolver::enterCount, SPxBoundFlippingRT::BreakpointCompare::entry, SPxFastRT::fastDelta, SPxBoundFlippingRT::flipAndUpdate(), SPxBoundFlippingRT::flipPotential, SPxBoundFlippingRT::FVEC, SPxSolver::fVec(), VectorBase< R >::get_const_ptr(), SPxBoundFlippingRT::getData(), SSVectorBase< R >::indexMem(), SPxSolver::instableEnter, SPxSolver::instableEnterId, SPxSolver::instableEnterVal, SSVectorBase< R >::isSetup(), SPxId::isSPxColId(), SPxId::isSPxRowId(), SPxId::isValid(), SPxBasis::iteration(), SPxSolver::lbBound(), SPxLPBase< R >::lhs(), LONGSTEP_FREQ, SPxLPBase< R >::lower(), LOWSTAB, SPxRatioTester::m_type, MAX_RELAX_COUNT, SPxFastRT::minStability(), MSG_DEBUG, SPxLPBase< R >::number(), SPxFastRT::relax(), SPxBoundFlippingRT::relax_count, SPxSolver::rep(), SPxFastRT::resetTols(), SPxLPBase< R >::rhs(), SPxFastRT::selectLeave(), SSVectorBase< R >::size(), soplex::spxAbs(), soplex::SPxQuicksortPart(), SPxRatioTester::thesolver, SPxFastRT::tighten(), SPxSolver::ubBound(), SPxLPBase< R >::upper(), and SSVectorBase< R >::values().

Referenced by SPxBoundFlippingRT::clone().

void useBoundFlips

(

bool

bf

)

Definition at line 245 of file spxboundflippingrt.h.

void useBoundFlipsRow

(

bool

bf

)

Definition at line 250 of file spxboundflippingrt.h.

Referenced by SoPlex::setBoolParam().

Member Data Documentation

DataArray<Breakpoint> breakpoints

private

array of breakpoints

Definition at line 105 of file spxboundflippingrt.h.

Referenced by SPxBoundFlippingRT::collectBreakpointsMax(), SPxBoundFlippingRT::collectBreakpointsMin(), SPxBoundFlippingRT::flipAndUpdate(), SPxBoundFlippingRT::selectEnter(), and SPxBoundFlippingRT::selectLeave().

bool enableBoundFlips

private

enable or disable long steps in BoundFlippingRT

Definition at line 101 of file spxboundflippingrt.h.

Referenced by SPxBoundFlippingRT::operator=(), SPxBoundFlippingRT::selectEnter(), and SPxBoundFlippingRT::selectLeave().

bool enableRowBoundFlips

private

enable bound flips also for row representation

Definition at line 102 of file spxboundflippingrt.h.

Referenced by SPxBoundFlippingRT::operator=(), and SPxBoundFlippingRT::selectLeave().

Real flipPotential

private

tracks bound flip history and decides which ratio test to use

Definition at line 103 of file spxboundflippingrt.h.

Referenced by SPxBoundFlippingRT::operator=(), SPxBoundFlippingRT::selectEnter(), and SPxBoundFlippingRT::selectLeave().

int relax_count

private

count rounds of ratio test

Definition at line 104 of file spxboundflippingrt.h.

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

SSVector updPrimRhs

private

right hand side vector of additional system to be solved after the ratio test

Definition at line 106 of file spxboundflippingrt.h.

Referenced by SPxBoundFlippingRT::flipAndUpdate().

SSVector updPrimVec

private

allocation of memory for additional solution vector

Definition at line 107 of file spxboundflippingrt.h.

Referenced by SPxBoundFlippingRT::flipAndUpdate().