Scippy

SoPlex

Sequential object-oriented simPlex

SPxDevexPR Class Reference

Devex pricer.The Devex Pricer for SoPlex implements an approximate steepest edge pricing, that does without solving an extra linear system and computing the scalar products. More...

#include <spxdevexpr.h>

Public Member Functions

Construction / destruction
 SPxDevexPR ()
 default constructor More...
 
 SPxDevexPR (const SPxDevexPR &old)
 copy constructor More...
 
SPxDevexPRoperator= (const SPxDevexPR &rhs)
 assignment operator More...
 
virtual ~SPxDevexPR ()
 destructor More...
 
virtual SPxPricerclone () const
 clone function for polymorphism More...
 
Access / modification
virtual void load (SPxSolver *base)
 sets the solver More...
 
virtual void setType (SPxSolver::Type)
 set entering/leaving algorithm More...
 
virtual void setRep (SPxSolver::Representation)
 set row/column representation More...
 
virtual int selectLeave ()
 
virtual SPxId selectEnter ()
 
virtual void left4 (int n, SPxId id)
 
virtual void entered4 (SPxId id, int n)
 
virtual void addedVecs (int n)
 n vectors have been added to loaded LP. More...
 
virtual void addedCoVecs (int n)
 n covectors have been added to loaded LP. More...
 
Consistency check
virtual bool isConsistent () const
 consistency check More...
 
- Public Member Functions inherited from SPxPricer
virtual const char * getName () const
 get name of pricer. More...
 
virtual void clear ()
 unloads LP. More...
 
virtual SPxSolversolver () const
 returns loaded SPxSolver object. More...
 
virtual Real epsilon () const
 returns violation bound theeps. More...
 
virtual void setEpsilon (Real eps)
 sets violation bound. More...
 
virtual void removedVec (int)
 vector i was removed from loaded LP. More...
 
virtual void removedVecs (const int *)
 vectors given by perm have been removed from loaded LP. More...
 
virtual void removedCoVec (int)
 covector i was removed from loaded LP. More...
 
virtual void removedCoVecs (const int *)
 covectors given by perm have been removed from loaded LP. More...
 
 SPxPricer (const char *p_name)
 constructor More...
 
 SPxPricer (const SPxPricer &old)
 copy constructor More...
 
SPxPriceroperator= (const SPxPricer &rhs)
 assignment operator More...
 
virtual ~SPxPricer ()
 destructor. More...
 

Private Member Functions

Private helpers
void setupWeights (SPxSolver::Type)
 set entering/leaving algorithm More...
 
int buildBestPriceVectorLeave (Real feastol)
 build up vector of pricing values for later use More...
 
int selectLeaveX (Real feastol, int start=0, int incr=1)
 internal implementation of SPxPricer::selectLeave() More...
 
int selectLeaveSparse (Real feastol)
 implementation of sparse pricing in the leaving Simplex More...
 
int selectLeaveHyper (Real feastol)
 implementation of hyper sparse pricing in the leaving Simplex More...
 
SPxId buildBestPriceVectorEnterDim (Real &best, Real feastol)
 build up vector of pricing values for later use More...
 
SPxId buildBestPriceVectorEnterCoDim (Real &best, Real feastol)
 
SPxId selectEnterX (Real tol)
 choose the best entering index among columns and rows but prefer sparsity More...
 
SPxId selectEnterSparseDim (Real &best, Real feastol)
 implementation of sparse pricing in the entering Simplex (slack variables) More...
 
SPxId selectEnterSparseCoDim (Real &best, Real feastol)
 implementation of sparse pricing in the entering Simplex More...
 
SPxId selectEnterDenseDim (Real &best, Real feastol, int start=0, int incr=1)
 SPxPricer::selectEnter() in dense case (slack variabels) More...
 
SPxId selectEnterDenseCoDim (Real &best, Real feastol, int start=0, int incr=1)
 SPxPricer::selectEnter() in dense case. More...
 
SPxId selectEnterHyperDim (Real &best, Real feastol)
 implementation of hyper sparse pricing in the entering Simplex More...
 
SPxId selectEnterHyperCoDim (Real &best, Real feastol)
 implementation of hyper sparse pricing in the entering Simplex More...
 

Private Attributes

Data
Real last
 penalty, selected at last iteration. More...
 
DataArray< IdxElementprices
 temporary array of precomputed pricing values More...
 
DataArray< IdxElementpricesCo
 temporary array of precomputed pricing values More...
 
DIdxSet bestPrices
 set of best pricing candidates More...
 
DIdxSet bestPricesCo
 set of best pricing candidates More...
 
bool refined
 has a refinement step already been tried? More...
 

Additional Inherited Members

- Public Types inherited from SPxPricer
enum  ViolationType { NOT_VIOLATED = 0, VIOLATED = 1, VIOLATED_AND_CHECKED = 2 }
 
- Protected Attributes inherited from SPxPricer
IdxCompare compare
 
const char * m_name
 name of the pricer More...
 
SPxSolverthesolver
 the solver More...
 
Real theeps
 violation bound More...
 

Detailed Description

Devex pricer.

The Devex Pricer for SoPlex implements an approximate steepest edge pricing, that does without solving an extra linear system and computing the scalar products.

See SPxPricer for a class documentation.

Todo:
There seem to be problems with this pricer especially on the greenbe[ab] problems with the entering algorithm (row representation?).

Definition at line 43 of file spxdevexpr.h.

Constructor & Destructor Documentation

◆ SPxDevexPR() [1/2]

default constructor

Definition at line 96 of file spxdevexpr.h.

Referenced by SPxDevexPR::clone().

◆ SPxDevexPR() [2/2]

SPxDevexPR ( const SPxDevexPR old)

copy constructor

Definition at line 102 of file spxdevexpr.h.

◆ ~SPxDevexPR()

virtual ~SPxDevexPR ( )
virtual

destructor

Definition at line 119 of file spxdevexpr.h.

Member Function Documentation

◆ addedCoVecs()

void addedCoVecs ( int  n)
virtual

◆ addedVecs()

void addedVecs ( int  n)
virtual

◆ buildBestPriceVectorEnterCoDim()

◆ buildBestPriceVectorEnterDim()

◆ buildBestPriceVectorLeave()

◆ clone()

◆ entered4()

void entered4 ( SPxId  id,
int  n 
)
virtual
Todo:
suspicious: the pricer should be informed, that variable id has entered the basis at position n, but the id is not used here (this is true for all pricers)

Reimplemented from SPxPricer.

Definition at line 870 of file spxdevexpr.cpp.

References SPxSolver::coPvec(), SPxSolver::coWeights, UpdateVector::delta(), SPxSolver::ENTER, SPxSolver::epsilon(), SPxSolver::fVec(), UpdateVector::idx(), IdxSet::index(), SPxDevexPR::last, SPxSolver::pVec(), SPxDevexPR::setupWeights(), IdxSet::size(), SPxPricer::thesolver, SSVectorBase< R >::values(), and SPxSolver::weights.

Referenced by SPxDevexPR::clone().

◆ isConsistent()

bool isConsistent ( ) const
virtual

◆ left4()

◆ load()

void load ( SPxSolver base)
virtual

sets the solver

Reimplemented from SPxPricer.

Definition at line 24 of file spxdevexpr.cpp.

References SPxDevexPR::isConsistent(), SPxSolver::rep(), SPxDevexPR::setRep(), and SPxPricer::thesolver.

Referenced by SPxDevexPR::clone(), SPxHybridPR::load(), and SPxAutoPR::load().

◆ operator=()

SPxDevexPR& operator= ( const SPxDevexPR rhs)

assignment operator

Definition at line 108 of file spxdevexpr.h.

References SPxDevexPR::last, and SPxPricer::operator=().

◆ selectEnter()

◆ selectEnterDenseCoDim()

SPxId selectEnterDenseCoDim ( Real best,
Real  feastol,
int  start = 0,
int  incr = 1 
)
private

◆ selectEnterDenseDim()

SPxId selectEnterDenseDim ( Real best,
Real  feastol,
int  start = 0,
int  incr = 1 
)
private

◆ selectEnterHyperCoDim()

◆ selectEnterHyperDim()

◆ selectEnterSparseCoDim()

◆ selectEnterSparseDim()

◆ selectEnterX()

◆ selectLeave()

◆ selectLeaveHyper()

◆ selectLeaveSparse()

◆ selectLeaveX()

int selectLeaveX ( Real  feastol,
int  start = 0,
int  incr = 1 
)
private

◆ setRep()

void setRep ( SPxSolver::Representation  )
virtual

set row/column representation

Todo:
suspicious: Shouldn't the relation between dim, coDim, Vecs, and CoVecs be influenced by the representation ?

Reimplemented from SPxPricer.

Definition at line 99 of file spxdevexpr.cpp.

References SPxDevexPR::addedCoVecs(), SPxDevexPR::addedVecs(), SPxSolver::coDim(), SPxSolver::dim(), SPxDevexPR::isConsistent(), and SPxPricer::thesolver.

Referenced by SPxDevexPR::clone(), SPxDevexPR::load(), SPxHybridPR::setRep(), and SPxAutoPR::setRep().

◆ setType()

◆ setupWeights()

Member Data Documentation

◆ bestPrices

◆ bestPricesCo

DIdxSet bestPricesCo
private

◆ last

◆ prices

DataArray<IdxElement> prices
private

temporary array of precomputed pricing values

Definition at line 51 of file spxdevexpr.h.

Referenced by SPxDevexPR::buildBestPriceVectorEnterDim(), SPxDevexPR::buildBestPriceVectorLeave(), and SPxDevexPR::setType().

◆ pricesCo

DataArray<IdxElement> pricesCo
private

temporary array of precomputed pricing values

Definition at line 52 of file spxdevexpr.h.

Referenced by SPxDevexPR::buildBestPriceVectorEnterCoDim(), and SPxDevexPR::setType().

◆ refined

bool refined
private

has a refinement step already been tried?

Definition at line 55 of file spxdevexpr.h.

Referenced by SPxDevexPR::selectEnter(), SPxDevexPR::selectEnterX(), SPxDevexPR::selectLeave(), and SPxDevexPR::setType().