Scippy

SoPlex

Sequential object-oriented simPlex

SPxDevexPR< R > Class Template 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 SPxPricer< R > * clone () const
 clone function for polymorphism More...
 
Access / modification
virtual void load (SPxSolverBase< R > *base)
 sets the solver More...
 
virtual void setType (typename SPxSolverBase< R >::Type)
 set entering/leaving algorithm More...
 
virtual void setRep (typename SPxSolverBase< R >::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< R >
virtual const char * getName () const
 get name of pricer. More...
 
virtual void clear ()
 unloads LP. More...
 
virtual SPxSolverBase< R > * solver () const
 returns loaded SPxSolverBase object. More...
 
virtual R epsilon () const
 returns violation bound theeps. More...
 
virtual void setEpsilon (R 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 (typename SPxSolverBase< R >::Type)
 set entering/leaving algorithm More...
 
int buildBestPriceVectorLeave (R feastol)
 build up vector of pricing values for later use More...
 
int selectLeaveX (R feastol, int start=0, int incr=1)
 internal implementation of SPxPricer::selectLeave() More...
 
int selectLeaveSparse (R feastol)
 implementation of sparse pricing in the leaving Simplex More...
 
int selectLeaveHyper (R feastol)
 implementation of hyper sparse pricing in the leaving Simplex More...
 
SPxId buildBestPriceVectorEnterDim (R &best, R feastol)
 build up vector of pricing values for later use More...
 
SPxId buildBestPriceVectorEnterCoDim (R &best, R feastol)
 
SPxId selectEnterX (R tol)
 choose the best entering index among columns and rows but prefer sparsity More...
 
SPxId selectEnterSparseDim (R &best, R feastol)
 implementation of sparse pricing in the entering Simplex (slack variables) More...
 
SPxId selectEnterSparseCoDim (R &best, R feastol)
 implementation of sparse pricing in the entering Simplex More...
 
SPxId selectEnterDenseDim (R &best, R feastol, int start=0, int incr=1)
 SPxPricer::selectEnter() in dense case (slack variabels) More...
 
SPxId selectEnterDenseCoDim (R &best, R feastol, int start=0, int incr=1)
 SPxPricer::selectEnter() in dense case. More...
 
SPxId selectEnterHyperDim (R &best, R feastol)
 implementation of hyper sparse pricing in the entering Simplex More...
 
SPxId selectEnterHyperCoDim (R &best, R feastol)
 implementation of hyper sparse pricing in the entering Simplex More...
 

Private Attributes

Data
last
 penalty, selected at last iteration. More...
 
Array< typename SPxPricer< R >::IdxElementprices
 temporary array of precomputed pricing values More...
 
Array< typename SPxPricer< R >::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< R >
enum  ViolationType { NOT_VIOLATED = 0, VIOLATED = 1, VIOLATED_AND_CHECKED = 2 }
 
- Protected Attributes inherited from SPxPricer< R >
IdxCompare compare
 
const char * m_name
 name of the pricer More...
 
SPxSolverBase< R > * thesolver
 the solver More...
 
theeps
 violation bound More...
 

Detailed Description

template<class R>
class soplex::SPxDevexPR< R >

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 44 of file spxdevexpr.h.

Constructor & Destructor Documentation

◆ SPxDevexPR() [1/2]

default constructor

Definition at line 99 of file spxdevexpr.h.

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

◆ SPxDevexPR() [2/2]

SPxDevexPR ( const SPxDevexPR< R > &  old)

copy constructor

Definition at line 105 of file spxdevexpr.h.

◆ ~SPxDevexPR()

virtual ~SPxDevexPR ( )
virtual

destructor

Definition at line 122 of file spxdevexpr.h.

Member Function Documentation

◆ addedCoVecs()

virtual void addedCoVecs ( int  n)
virtual

n covectors have been added to loaded LP.

Reimplemented from SPxPricer< R >.

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

◆ addedVecs()

virtual void addedVecs ( int  n)
virtual

n vectors have been added to loaded LP.

Reimplemented from SPxPricer< R >.

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

◆ buildBestPriceVectorEnterCoDim()

SPxId buildBestPriceVectorEnterCoDim ( R &  best,
feastol 
)
private

◆ buildBestPriceVectorEnterDim()

SPxId buildBestPriceVectorEnterDim ( R &  best,
feastol 
)
private

build up vector of pricing values for later use

◆ buildBestPriceVectorLeave()

int buildBestPriceVectorLeave ( feastol)
private

build up vector of pricing values for later use

◆ clone()

◆ entered4()

virtual void entered4 ( SPxId  id,
int  n 
)
virtual

Reimplemented from SPxPricer< R >.

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

◆ isConsistent()

virtual bool isConsistent ( ) const
virtual

consistency check

Reimplemented from SPxPricer< R >.

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

◆ left4()

virtual void left4 ( int  n,
SPxId  id 
)
virtual

Reimplemented from SPxPricer< R >.

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

◆ load()

virtual void load ( SPxSolverBase< R > *  base)
virtual

sets the solver

Reimplemented from SPxPricer< R >.

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

◆ operator=()

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

assignment operator

Definition at line 111 of file spxdevexpr.h.

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

◆ selectEnter()

virtual SPxId selectEnter ( )
virtual

Implements SPxPricer< R >.

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

◆ selectEnterDenseCoDim()

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

SPxPricer::selectEnter() in dense case.

◆ selectEnterDenseDim()

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

SPxPricer::selectEnter() in dense case (slack variabels)

◆ selectEnterHyperCoDim()

SPxId selectEnterHyperCoDim ( R &  best,
feastol 
)
private

implementation of hyper sparse pricing in the entering Simplex

◆ selectEnterHyperDim()

SPxId selectEnterHyperDim ( R &  best,
feastol 
)
private

implementation of hyper sparse pricing in the entering Simplex

◆ selectEnterSparseCoDim()

SPxId selectEnterSparseCoDim ( R &  best,
feastol 
)
private

implementation of sparse pricing in the entering Simplex

◆ selectEnterSparseDim()

SPxId selectEnterSparseDim ( R &  best,
feastol 
)
private

implementation of sparse pricing in the entering Simplex (slack variables)

◆ selectEnterX()

SPxId selectEnterX ( tol)
private

choose the best entering index among columns and rows but prefer sparsity

◆ selectLeave()

virtual int selectLeave ( )
virtual

Implements SPxPricer< R >.

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

◆ selectLeaveHyper()

int selectLeaveHyper ( feastol)
private

implementation of hyper sparse pricing in the leaving Simplex

◆ selectLeaveSparse()

int selectLeaveSparse ( feastol)
private

implementation of sparse pricing in the leaving Simplex

◆ selectLeaveX()

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

internal implementation of SPxPricer::selectLeave()

◆ setRep()

virtual void setRep ( typename SPxSolverBase< R >::Representation  )
virtual

set row/column representation

Reimplemented from SPxPricer< R >.

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

◆ setType()

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

set entering/leaving algorithm

Reimplemented from SPxPricer< R >.

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

◆ setupWeights()

void setupWeights ( typename SPxSolverBase< R >::Type  )
private

set entering/leaving algorithm

Member Data Documentation

◆ bestPrices

DIdxSet bestPrices
private

set of best pricing candidates

Definition at line 56 of file spxdevexpr.h.

◆ bestPricesCo

DIdxSet bestPricesCo
private

set of best pricing candidates

Definition at line 57 of file spxdevexpr.h.

◆ last

R last
private

penalty, selected at last iteration.

Definition at line 51 of file spxdevexpr.h.

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

◆ prices

Array<typename SPxPricer<R>::IdxElement> prices
private

temporary array of precomputed pricing values

Definition at line 53 of file spxdevexpr.h.

◆ pricesCo

Array<typename SPxPricer<R>::IdxElement> pricesCo
private

temporary array of precomputed pricing values

Definition at line 55 of file spxdevexpr.h.

◆ refined

bool refined
private

has a refinement step already been tried?

Definition at line 58 of file spxdevexpr.h.