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

SPxDevexPR &	operator= (const SPxDevexPR &rhs)
	assignment operator More...

virtual	~SPxDevexPR ()
	destructor More...

virtual SPxPricer *	clone () 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 SPxSolver *	solver () 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...

SPxPricer &	operator= (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< IdxElement >	prices
	temporary array of precomputed pricing values More...

DataArray< IdxElement >	pricesCo
	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...

SPxSolver *	thesolver
	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]

SPxDevexPR ( )

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

n covectors have been added to loaded LP.

Reimplemented from SPxPricer.

Definition at line 926 of file spxdevexpr.cpp.

References SPxSolver::coWeights, VectorBase< R >::dim(), SPxSolver::dim(), SPxSolver::ENTER, DVectorBase< R >::reDim(), SPxPricer::thesolver, and SPxSolver::type().

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

◆ addedVecs()

void addedVecs ( int n )

virtual

n vectors have been added to loaded LP.

Reimplemented from SPxPricer.

Definition at line 915 of file spxdevexpr.cpp.

References SPxSolver::coDim(), VectorBase< R >::dim(), SPxSolver::ENTER, DVectorBase< R >::reDim(), SPxPricer::thesolver, SPxSolver::type(), and SPxSolver::weights.

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

◆ buildBestPriceVectorEnterCoDim()

SPxId buildBestPriceVectorEnterCoDim	(	Real &	best,
		Real	feastol
	)

private

◆ buildBestPriceVectorEnterDim()

SPxId buildBestPriceVectorEnterDim	(	Real &	best,
		Real	feastol
	)

private

build up vector of pricing values for later use

Definition at line 378 of file spxdevexpr.cpp.

References DIdxSet::addIdx(), DataArray< T >::append(), SPxDevexPR::bestPrices, IdxSet::clear(), DataArray< T >::clear(), SPxSolver::coId(), SPxPricer::compare, soplex::computePrice(), SPxSolver::coTest(), SPxSolver::coWeights, SPxPricer::IdxCompare::elements, DataArray< T >::get_const_ptr(), VectorBase< R >::get_const_ptr(), DataArray< T >::get_ptr(), HYPERPRICINGSIZE, SPxPricer::IdxElement::idx, IdxSet::index(), SPxSolver::infeasibilities, SPxSolver::isInfeasible, SPxPricer::NOT_VIOLATED, SPxDevexPR::prices, IdxSet::remove(), IdxSet::size(), DataArray< T >::size(), soplex::SPxQuicksortPart(), SPxPricer::thesolver, SPxPricer::IdxElement::val, SPxPricer::VIOLATED, and SPxPricer::VIOLATED_AND_CHECKED.

Referenced by SPxDevexPR::selectEnterX().

◆ buildBestPriceVectorLeave()

int buildBestPriceVectorLeave ( Real feastol )

private

build up vector of pricing values for later use

Definition at line 119 of file spxdevexpr.cpp.

References DIdxSet::addIdx(), DataArray< T >::append(), SPxDevexPR::bestPrices, IdxSet::clear(), DataArray< T >::clear(), SPxPricer::compare, soplex::computePrice(), SPxSolver::coWeights, SPxPricer::IdxCompare::elements, SPxSolver::fTest(), DataArray< T >::get_const_ptr(), VectorBase< R >::get_const_ptr(), DataArray< T >::get_ptr(), HYPERPRICINGSIZE, SPxPricer::IdxElement::idx, IdxSet::index(), SPxSolver::infeasibilities, SPxSolver::isInfeasible, SPxDevexPR::prices, IdxSet::size(), DataArray< T >::size(), soplex::SPxQuicksortPart(), SPxPricer::thesolver, SPxPricer::IdxElement::val, SPxPricer::VIOLATED, and SPxPricer::VIOLATED_AND_CHECKED.

Referenced by SPxDevexPR::selectLeave().

◆ clone()

virtual SPxPricer* clone ( ) const

virtual

clone function for polymorphism

Implements SPxPricer.

Definition at line 122 of file spxdevexpr.h.

References SPxDevexPR::addedCoVecs(), SPxDevexPR::addedVecs(), SPxDevexPR::entered4(), SPxDevexPR::isConsistent(), SPxDevexPR::left4(), SPxDevexPR::load(), SPxDevexPR::selectEnter(), SPxDevexPR::selectLeave(), SPxDevexPR::setRep(), SPxDevexPR::setType(), and SPxDevexPR::SPxDevexPR().

◆ 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.