Scippy

SoPlex

Sequential object-oriented simPlex

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...
 
SPxBoundFlippingRToperator= (const SPxBoundFlippingRT &rhs)
 assignment operator More...
 
virtual ~SPxBoundFlippingRT ()
 destructor More...
 
virtual SPxRatioTesterclone () 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...
 
SPxFastRToperator= (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 SPxSolversolver () const
 returns loaded LP solver. More...
 
 SPxRatioTester (const char *name)
 default constructor More...
 
 SPxRatioTester (const SPxRatioTester &old)
 copy constructor More...
 
SPxRatioTesteroperator= (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< Breakpointbreakpoints
 
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
SPxSolverthesolver
 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

default constructor

Definition at line 186 of file spxboundflippingrt.h.

Referenced by SPxBoundFlippingRT::clone().

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

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

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

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

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