SoPlex Documentation
Loading...
Searching...
No Matches

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

#include <spxboundflippingrt.h>

Inheritance diagram for SPxBoundFlippingRT< R >:
SPxFastRT< R > SPxRatioTester< R >

Classes

struct  Breakpoint
 
struct  BreakpointCompare
 

Public Member Functions

Construction / destruction
 SPxBoundFlippingRT ()
 default constructor
 
 SPxBoundFlippingRT (const SPxBoundFlippingRT &old)
 copy constructor
 
SPxBoundFlippingRToperator= (const SPxBoundFlippingRT &rhs)
 assignment operator
 
virtual ~SPxBoundFlippingRT ()
 destructor
 
virtual SPxRatioTester< R > * clone () const
 clone function for polymorphism
 
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
 
- Public Member Functions inherited from SPxFastRT< R >
 SPxFastRT ()
 default constructor
 
 SPxFastRT (const SPxFastRT &old)
 copy constructor
 
SPxFastRToperator= (const SPxFastRT &rhs)
 assignment operator
 
 SPxFastRT (const char *name)
 bound flipping constructor
 
virtual ~SPxFastRT ()
 destructor
 
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.
 
virtual void clear ()
 unloads LP.
 
virtual SPxSolverBase< R > * solver () const
 returns loaded LP solver.
 
const std::shared_ptr< Tolerancestolerances () const
 get the _tolerances member variable
 
 SPxRatioTester (const char *name)
 default constructor
 
 SPxRatioTester (const SPxRatioTester &old)
 copy constructor
 
SPxRatioTesteroperator= (const SPxRatioTester &rhs)
 assignment operator
 
virtual ~SPxRatioTester ()
 destructor.
 

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
 
flipPotential
 
int relax_count
 
Array< Breakpointbreakpoints
 
SSVectorBase< R > updPrimRhs
 
SSVectorBase< R > updPrimVec
 

Additional Inherited Members

- Protected Member Functions inherited from SPxFastRT< R >
void resetTols ()
 resets tolerances (epsilon).
 
const R epsilonZero () const
 return epsilon
 
void relax ()
 relaxes stability requirements.
 
void tighten ()
 tightens stability requirements.
 
minStability (R maxabs)
 Compute stability requirement.
 
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.
 
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.
 
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.
 
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.
 
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.
 
bool maxShortLeave (R &sel, int leave, R maxabs)
 
bool minReLeave (R &sel, int leave, R maxabs, bool polish=false)
 numerical stability tests.
 
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.
 
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.
 
- Protected Attributes inherited from SPxFastRT< R >
minStab
 parameter for computing minimum stability requirement
 
epsilon
 zero tolerance used by the ratio tester
 
fastDelta
 currently allowed infeasibility.
 
bool iscoid
 flag used in methods minSelect/maxSelect to retrieve correct basis status
 
- Protected Attributes inherited from SPxRatioTester< R >
SPxSolverBase< R > * thesolver
 the solver
 
const char * m_name
 name of the ratio tester
 
SPxSolverBase< R >::Type m_type
 internal storage of type
 
delta
 allowed bound violation
 
std::shared_ptr< Tolerances_tolerances
 tolerances used by the solver
 

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 70 of file spxsolver.h.

Member Enumeration Documentation

◆ BreakpointSource

template<class R >
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]

template<class R >
SPxBoundFlippingRT ( )

default constructor

Definition at line 198 of file spxboundflippingrt.h.

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

◆ SPxBoundFlippingRT() [2/2]

template<class R >
SPxBoundFlippingRT ( const SPxBoundFlippingRT< R > & old)

copy constructor

Definition at line 209 of file spxboundflippingrt.h.

◆ ~SPxBoundFlippingRT()

template<class R >
virtual ~SPxBoundFlippingRT ( )
virtual

destructor

Definition at line 234 of file spxboundflippingrt.h.

Member Function Documentation

◆ clone()

template<class R >
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()

template<class R >
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
nBpnumber of found breakpoints so far
minIdxindex to current minimal breakpoint
idxpointer to indices of current vector
nnznumber of nonzeros in current vector
updpointer to update values of current vector
vecpointer to values of current vector
upppointer to upper bound/rhs of current vector
lowpointer to lower bound/lhs of current vector
srctype of vector (pVec or coPvec)

◆ collectBreakpointsMin()

template<class R >
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
nBpnumber of found breakpoints so far
minIdxindex to current minimal breakpoint
idxpointer to indices of current vector
nnznumber of nonzeros in current vector
updpointer to update values of current vector
vecpointer to values of current vector
upppointer to upper bound/rhs of current vector
lowpointer to lower bound/lhs of current vector
srctype of vector (pVec or coPvec)

◆ flipAndUpdate()

template<class R >
void flipAndUpdate ( int & usedBp)
private

perform necessary bound flips to restore dual feasibility

Parameters
usedBpnumber of bounds that should be flipped

◆ getData() [1/2]

template<class R >
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]

template<class R >
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()

template<class R >
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=()

◆ selectEnter()

template<class R >
virtual SPxId selectEnter ( R & val,
int leaveIdx,
bool polish = false )
virtual

Reimplemented from SPxFastRT< R >.

◆ selectLeave()

template<class R >
virtual int selectLeave ( R & val,
R enterTest,
bool polish = false )
virtual

Reimplemented from SPxFastRT< R >.

◆ setTolerances()

template<class R >
void setTolerances ( std::shared_ptr< Tolerances > tolerances)
virtual

◆ useBoundFlips()

template<class R >
void useBoundFlips ( bool bf)

Definition at line 259 of file spxboundflippingrt.h.

References SPxBoundFlippingRT< R >::enableBoundFlips.

◆ useBoundFlipsRow()

template<class R >
void useBoundFlipsRow ( bool bf)

Member Data Documentation

◆ breakpoints

template<class R >
Array<Breakpoint> breakpoints
private

array of breakpoints

Definition at line 115 of file spxboundflippingrt.h.

◆ enableBoundFlips

template<class R >
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

template<class R >
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

template<class R >
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

template<class R >
int relax_count
private

count rounds of ratio test

Definition at line 114 of file spxboundflippingrt.h.

◆ updPrimRhs

template<class R >
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

template<class R >
SSVectorBase<R> updPrimVec
private

allocation of memory for additional solution vector

Definition at line 119 of file spxboundflippingrt.h.

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