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

#include <spxboundflippingrt.h>

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< R > *	clone () const
	clone function for polymorphism More...

Select enter/leave
virtual int	selectLeave (R &val, R enterTest, bool polish=false)

virtual SPxId	selectEnter (R &val, int leaveIdx, bool polish=false)

void	useBoundFlips (bool bf)

void	useBoundFlipsRow (bool bf)

void	setTolerances (std::shared_ptr< Tolerances > tolerances)
	set tolerances More...

Public Member Functions inherited from SPxFastRT< R >
	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 (SPxSolverBase< R > *solver)

virtual void	setType (typename SPxSolverBase< R >::Type type)

virtual void	setDelta (R newDelta)

virtual R	getDelta ()

Public Member Functions inherited from SPxRatioTester< R >
virtual const char *	getName () const
	get name of ratio tester. More...

virtual void	clear ()
	unloads LP. More...

virtual SPxSolverBase< R > *	solver () const
	returns loaded LP solver. More...

const std::shared_ptr< Tolerances >	tolerances () const
	get the _tolerances member variable 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 R upd, const R vec, const R upp, const R *low, BreakpointSource src)

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

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

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

void	flipAndUpdate (int &usedBp)

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

Private Attributes
Data
bool	enableBoundFlips

bool	enableRowBoundFlips

R	flipPotential

int	relax_count

Array< Breakpoint >	breakpoints

SSVectorBase< R >	updPrimRhs

SSVectorBase< R >	updPrimVec

Additional Inherited Members
Protected Member Functions inherited from SPxFastRT< R >
void	resetTols ()
	resets tolerances (epsilon). More...

const R	epsilonZero () const
	return epsilon More...

void	relax ()
	relaxes stability requirements. More...

void	tighten ()
	tightens stability requirements. More...

R	minStability (R maxabs)
	Compute stability requirement. More...

int	maxDelta (R &val, R &maxabs, UpdateVector< R > &update, const VectorBase< R > &lowBound, const VectorBase< R > &upBound, int start, int incr) const
	Max phase 1 value. More...

int	maxDelta (R &val, R &maxabs)

SPxId	maxDelta (int &nr, R &val, R &maxabs)

int	minDelta (R &val, R &maxabs, UpdateVector< R > &update, const VectorBase< R > &lowBound, const VectorBase< R > &upBound, int start, int incr) const
	Min phase 1 value. More...

int	minDelta (R &val, R &maxabs)

SPxId	minDelta (int &nr, R &val, R &maxabs)

int	maxSelect (R &val, R &stab, R &best, R &bestDelta, R max, const UpdateVector< R > &upd, const VectorBase< R > &low, const VectorBase< R > &up, int start=0, int incr=1) const
	selects stable index for maximizing ratio test. More...

int	maxSelect (R &val, R &stab, R &bestDelta, R max)

SPxId	maxSelect (int &nr, R &val, R &stab, R &bestDelta, R max)

int	minSelect (R &val, R &stab, R &best, R &bestDelta, R max, const UpdateVector< R > &upd, const VectorBase< R > &low, const VectorBase< R > &up, int start=0, int incr=1) const
	selects stable index for minimizing ratio test. More...

int	minSelect (R &val, R &stab, R &bestDelta, R max)

SPxId	minSelect (int &nr, R &val, R &stab, R &bestDelta, R max)

bool	minShortLeave (R &sel, int leave, R maxabs)
	tests for stop after phase 1. More...

bool	maxShortLeave (R &sel, int leave, R maxabs)

bool	minReLeave (R &sel, int leave, R maxabs, bool polish=false)
	numerical stability tests. More...

bool	maxReLeave (R &sel, int leave, R maxabs, bool polish=false)

bool	minReEnter (R &sel, R maxabs, const SPxId &id, int nr, bool polish=false)
	numerical stability check. More...

bool	maxReEnter (R &sel, R maxabs, const SPxId &id, int nr, bool polish=false)

bool	shortEnter (const SPxId &enterId, int nr, R max, R maxabs) const
	Tests and returns whether a shortcut after phase 1 is feasible for the selected enter pivot. More...

Protected Attributes inherited from SPxFastRT< R >
R	minStab
	parameter for computing minimum stability requirement More...

R	epsilon
	zero tolerance used by the ratio tester More...

R	fastDelta
	currently allowed infeasibility. More...

bool	iscoid
	flag used in methods minSelect/maxSelect to retrieve correct basis status More...

Protected Attributes inherited from SPxRatioTester< R >
SPxSolverBase< R > *	thesolver
	the solver More...

const char *	m_name
	name of the ratio tester More...

SPxSolverBase< R >::Type	m_type
	internal storage of type More...

R	delta
	allowed bound violation More...

std::shared_ptr< Tolerances >	_tolerances
	tolerances used by the solver More...

Detailed Description

template<class R>
class soplex::SPxBoundFlippingRT< R >

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 60 of file spxboundflippingrt.h.

Member Enumeration Documentation

◆ BreakpointSource

enum BreakpointSource

private

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

Enumerator
FVEC
PVEC
COPVEC

Definition at line 67 of file spxboundflippingrt.h.

Constructor & Destructor Documentation

◆ SPxBoundFlippingRT() [1/2]

SPxBoundFlippingRT ( )

default constructor

Definition at line 198 of file spxboundflippingrt.h.

Referenced by SPxBoundFlippingRT< R >::clone().

◆ SPxBoundFlippingRT() [2/2]

SPxBoundFlippingRT ( const SPxBoundFlippingRT< R > & old )

copy constructor

Definition at line 209 of file spxboundflippingrt.h.

◆ ~SPxBoundFlippingRT()

virtual ~SPxBoundFlippingRT ( )

virtual

destructor

Definition at line 234 of file spxboundflippingrt.h.

Member Function Documentation

◆ clone()

virtual SPxRatioTester< R > * clone ( ) const

virtual

clone function for polymorphism

Reimplemented from SPxFastRT< R >.

Definition at line 237 of file spxboundflippingrt.h.

References SPxBoundFlippingRT< R >::SPxBoundFlippingRT().

◆ collectBreakpointsMax()

void collectBreakpointsMax	(	int &	nBp,
		int &	minIdx,
		const int *	idx,
		int	nnz,
		const R *	upd,
		const R *	vec,
		const R *	upp,
		const R *	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)

◆ collectBreakpointsMin()

void collectBreakpointsMin	(	int &	nBp,
		int &	minIdx,
		const int *	idx,
		int	nnz,
		const R *	upd,
		const R *	vec,
		const R *	upp,
		const R *	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)

◆ flipAndUpdate()

void flipAndUpdate ( int & usedBp )

private

perform necessary bound flips to restore dual feasibility

Parameters

usedBp number of bounds that should be flipped

◆ getData() [1/2]

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

private

get values for leaving index and perform shifts if necessary

◆ getData() [2/2]

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

private

get values for entering index and perform shifts if necessary

◆ isSmaller()

static bool isSmaller	(	Breakpoint	x,
		Breakpoint	y
	)

staticprivate

comparison method for breakpoints

Definition at line 184 of file spxboundflippingrt.h.

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

◆ operator=()

SPxBoundFlippingRT & operator= ( const SPxBoundFlippingRT< R > & rhs )

assignment operator

Definition at line 220 of file spxboundflippingrt.h.

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

◆ selectEnter()

virtual SPxId selectEnter	(	R &	val,
		int	leaveIdx,
		bool	polish = `false`
	)

virtual

Reimplemented from SPxFastRT< R >.

◆ selectLeave()

virtual int selectLeave	(	R &	val,
		R	enterTest,
		bool	polish = `false`
	)

virtual

Reimplemented from SPxFastRT< R >.

◆ setTolerances()

void setTolerances ( std::shared_ptr< Tolerances > tolerances )

virtual

set tolerances

Reimplemented from SPxRatioTester< R >.

Definition at line 270 of file spxboundflippingrt.h.

References SPxRatioTester< R >::_tolerances, SPxRatioTester< R >::tolerances(), SPxBoundFlippingRT< R >::updPrimRhs, and SPxBoundFlippingRT< R >::updPrimVec.

◆ useBoundFlips()

void useBoundFlips ( bool bf )

Definition at line 259 of file spxboundflippingrt.h.

References SPxBoundFlippingRT< R >::enableBoundFlips.

◆ useBoundFlipsRow()

void useBoundFlipsRow ( bool bf )

Definition at line 264 of file spxboundflippingrt.h.

References SPxBoundFlippingRT< R >::enableRowBoundFlips.

Member Data Documentation

◆ breakpoints

Array<Breakpoint> breakpoints

private

array of breakpoints

Definition at line 115 of file spxboundflippingrt.h.

◆ enableBoundFlips

bool enableBoundFlips

private

enable or disable long steps in BoundFlippingRT

Definition at line 110 of file spxboundflippingrt.h.

Referenced by SPxBoundFlippingRT< R >::operator=(), and SPxBoundFlippingRT< R >::useBoundFlips().

◆ enableRowBoundFlips

bool enableRowBoundFlips

private

enable bound flips also for row representation

Definition at line 111 of file spxboundflippingrt.h.

Referenced by SPxBoundFlippingRT< R >::operator=(), and SPxBoundFlippingRT< R >::useBoundFlipsRow().

◆ flipPotential

R flipPotential

private

tracks bound flip history and decides which ratio test to use

Definition at line 113 of file spxboundflippingrt.h.

Referenced by SPxBoundFlippingRT< R >::operator=().

◆ relax_count

int relax_count

private

count rounds of ratio test

Definition at line 114 of file spxboundflippingrt.h.

◆ updPrimRhs

SSVectorBase<R> updPrimRhs

private

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

Definition at line 117 of file spxboundflippingrt.h.

Referenced by SPxBoundFlippingRT< R >::setTolerances().

◆ updPrimVec

SSVectorBase<R> updPrimVec

private

allocation of memory for additional solution vector

Definition at line 119 of file spxboundflippingrt.h.

Referenced by SPxBoundFlippingRT< R >::setTolerances().

SoPlex

Classes

Public Member Functions

Private Types

Private Member Functions

Static Private Member Functions

Private Attributes

Additional Inherited Members

Detailed Description

Member Enumeration Documentation

◆ BreakpointSource

Constructor & Destructor Documentation

◆ SPxBoundFlippingRT() [1/2]

◆ SPxBoundFlippingRT() [2/2]

◆ ~SPxBoundFlippingRT()

Member Function Documentation

◆ clone()

◆ collectBreakpointsMax()

◆ collectBreakpointsMin()

◆ flipAndUpdate()

◆ getData() [1/2]

◆ getData() [2/2]

◆ isSmaller()

◆ operator=()

◆ selectEnter()

◆ selectLeave()

◆ setTolerances()

◆ useBoundFlips()

◆ useBoundFlipsRow()

Member Data Documentation

◆ breakpoints

◆ enableBoundFlips

◆ enableRowBoundFlips

◆ flipPotential

◆ relax_count

◆ updPrimRhs

◆ updPrimVec