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>

Inheritance diagram for SPxDevexPR:

[legend]

Public Member Functions
Construction / destruction
	SPxDevexPR ()
	default constructor

	SPxDevexPR (const SPxDevexPR &old)
	copy constructor

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

virtual	~SPxDevexPR ()
	destructor

virtual SPxPricer *	clone () const
	clone function for polymorphism

Access / modification
virtual void	load (SPxSolver *base)
	sets the solver

virtual void	setType (SPxSolver::Type)
	set entering/leaving algorithm

virtual void	setRep (SPxSolver::Representation)
	set row/column representation

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.

virtual void	addedCoVecs (int n)
	`n` covectors have been added to loaded LP.

Consistency check
virtual bool	isConsistent () const
	consistency check

Public Member Functions inherited from SPxPricer
virtual const char *	getName () const
	get name of pricer.

virtual void	clear ()
	unloads LP.

virtual SPxSolver *	solver () const
	returns loaded SPxSolver object.

virtual Real	epsilon () const
	returns violation bound theeps.

virtual void	setEpsilon (Real eps)
	sets violation bound.

virtual void	removedVec (int)
	vector `i` was removed from loaded LP.

virtual void	removedVecs (const int *)
	vectors given by `perm` have been removed from loaded LP.

virtual void	removedCoVec (int)
	covector `i` was removed from loaded LP.

virtual void	removedCoVecs (const int *)
	covectors given by `perm` have been removed from loaded LP.

virtual void	getNdualNorms (int &nrows, int &ncols) const
	get number of available norms

virtual bool	getDualNorms (int &nrows, int &ncols, Real *norms) const
	export norms from pricer

virtual bool	setDualNorms (int nrows, int ncols, Real *norms)
	import norms into pricer

	SPxPricer (const char *p_name)
	constructor

	SPxPricer (const SPxPricer &old)
	copy constructor

SPxPricer &	operator= (const SPxPricer &rhs)
	assignment operator

virtual	~SPxPricer ()
	destructor.

Private Member Functions
Private helpers
void	init (SPxSolver::Type)
	set entering/leaving algorithm

int	buildBestPriceVectorLeave (Real feastol)
	build up vector of pricing values for later use

int	selectLeaveX (Real feastol, int start=0, int incr=1)
	internal implementation of SPxPricer::selectLeave()

int	selectLeaveSparse (Real feastol)
	implementation of sparse pricing in the leaving Simplex

int	selectLeaveHyper (Real feastol)
	implementation of hyper sparse pricing in the leaving Simplex

SPxId	buildBestPriceVectorEnterDim (Real &best, Real feastol)
	build up vector of pricing values for later use

SPxId	buildBestPriceVectorEnterCoDim (Real &best, Real feastol)

SPxId	selectEnterX (Real tol)
	choose the best entering index among columns and rows but prefer sparsity

SPxId	selectEnterSparseDim (Real &best, Real feastol)
	implementation of sparse pricing in the entering Simplex (slack variables)

SPxId	selectEnterSparseCoDim (Real &best, Real feastol)
	implementation of sparse pricing in the entering Simplex

SPxId	selectEnterDenseDim (Real &best, Real feastol, int start=0, int incr=1)
	SPxPricer::selectEnter() in dense case (slack variabels)

SPxId	selectEnterDenseCoDim (Real &best, Real feastol, int start=0, int incr=1)
	SPxPricer::selectEnter() in dense case.

SPxId	selectEnterHyperDim (Real &best, Real feastol)
	implementation of hyper sparse pricing in the entering Simplex

SPxId	selectEnterHyperCoDim (Real &best, Real feastol)
	implementation of hyper sparse pricing in the entering Simplex

Private Attributes
Data
Real	last
	penalty, selected at last iteration.

DataArray< IdxElement >	prices
	temporary array of precomputed pricing values

DataArray< IdxElement >	pricesCo
	temporary array of precomputed pricing values

DIdxSet	bestPrices
	set of best pricing candidates

DIdxSet	bestPricesCo
	set of best pricing candidates

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

SPxSolver *	thesolver
	the solver

Real	theeps
	violation bound

DVector	weights
	vector to store pricing weights or norms

DVector	coWeights

bool	weightsAreSetup
	are the weights already set up?

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

default constructor

Definition at line 96 of file spxdevexpr.h.

Referenced by SPxDevexPR::clone().

SPxDevexPR ( const SPxDevexPR & old )

copy constructor

Definition at line 102 of file spxdevexpr.h.

virtual ~SPxDevexPR ( )

virtual

destructor

Definition at line 119 of file spxdevexpr.h.

Member Function Documentation

void addedCoVecs ( int n )

virtual

n covectors have been added to loaded LP.

Reimplemented from SPxPricer.

Definition at line 861 of file spxdevexpr.cpp.

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

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

void addedVecs ( int n )

virtual

n vectors have been added to loaded LP.

Reimplemented from SPxPricer.

Definition at line 852 of file spxdevexpr.cpp.

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

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

SPxId buildBestPriceVectorEnterCoDim	(	Real &	best,
		Real	feastol
	)

private

SPxId buildBestPriceVectorEnterDim	(	Real &	best,
		Real	feastol
	)

private

build up vector of pricing values for later use

Definition at line 348 of file spxdevexpr.cpp.

References DIdxSet::addIdx(), DataArray< T >::append(), SPxDevexPR::bestPrices, IdxSet::clear(), DataArray< T >::clear(), SPxSolver::coId(), SPxPricer::compare, SPxSolver::coTest(), SPxPricer::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().

int buildBestPriceVectorLeave ( Real feastol )

private

build up vector of pricing values for later use

Definition at line 102 of file spxdevexpr.cpp.

References DIdxSet::addIdx(), DataArray< T >::append(), SPxDevexPR::bestPrices, IdxSet::clear(), DataArray< T >::clear(), SPxPricer::compare, SPxPricer::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().

virtual SPxPricer* clone ( ) const

virtual

clone function for polymorphism

Implements SPxPricer.

Definition at line 122 of file spxdevexpr.h.

References SPxDevexPR::SPxDevexPR().

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 812 of file spxdevexpr.cpp.

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