|
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>
|
|
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
|
|
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.
void addedCoVecs |
( |
int |
n | ) |
|
|
virtual |
SPxId buildBestPriceVectorEnterCoDim |
( |
Real & |
best, |
|
|
Real |
feastol |
|
) |
| |
|
private |
Definition at line 398 of file spxdevexpr.cpp.
References DIdxSet::addIdx(), DataArray< T >::append(), SPxDevexPR::bestPricesCo, IdxSet::clear(), DataArray< T >::clear(), SPxPricer::compare, SPxPricer::IdxCompare::elements, DataArray< T >::get_const_ptr(), VectorBase< R >::get_const_ptr(), DataArray< T >::get_ptr(), HYPERPRICINGSIZE, SPxSolver::id(), SPxPricer::IdxElement::idx, IdxSet::index(), SPxSolver::infeasibilitiesCo, SPxSolver::isInfeasibleCo, SPxPricer::NOT_VIOLATED, SPxDevexPR::pricesCo, IdxSet::remove(), IdxSet::size(), DataArray< T >::size(), soplex::SPxQuicksortPart(), SPxSolver::test(), SPxPricer::thesolver, SPxPricer::IdxElement::val, SPxPricer::VIOLATED, SPxPricer::VIOLATED_AND_CHECKED, and SPxPricer::weights.
Referenced by SPxDevexPR::selectEnterX().
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().
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.
set entering/leaving algorithm
Definition at line 43 of file spxdevexpr.cpp.
References SPxDevexPR::bestPrices, SPxDevexPR::bestPricesCo, IdxSet::clear(), SPxSolver::coDim(), SPxPricer::coWeights, VectorBase< R >::dim(), SPxSolver::dim(), SPxSolver::ENTER, SPxSolver::hyperPricingEnter, SPxSolver::hyperPricingLeave, SPxDevexPR::isConsistent(), SPxDevexPR::prices, SPxDevexPR::pricesCo, DataArray< T >::reMax(), DIdxSet::setMax(), SPxSolver::sparsePricingEnter, SPxSolver::sparsePricingEnterCo, SPxSolver::sparsePricingLeave, SPxPricer::thesolver, SPxPricer::weights, and SPxPricer::weightsAreSetup.
Referenced by SPxDevexPR::entered4(), and SPxDevexPR::setType().
bool isConsistent |
( |
| ) |
const |
|
virtual |
void left4 |
( |
int |
n, |
|
|
SPxId |
id |
|
) |
| |
|
virtual |
Reimplemented from SPxPricer.
Definition at line 315 of file spxdevexpr.cpp.
References SPxSolver::coPvec(), SPxPricer::coWeights, UpdateVector::delta(), SPxSolver::fVec(), UpdateVector::idx(), SSVectorBase< R >::length2(), MSG_ERROR, IdxSet::size(), soplex::spxAbs(), SPxPricer::theeps, SPxPricer::thesolver, and SSVectorBase< R >::values().
SPxId selectEnterDenseCoDim |
( |
Real & |
best, |
|
|
Real |
feastol, |
|
|
int |
start = 0 , |
|
|
int |
incr = 1 |
|
) |
| |
|
private |
SPxId selectEnterDenseDim |
( |
Real & |
best, |
|
|
Real |
feastol, |
|
|
int |
start = 0 , |
|
|
int |
incr = 1 |
|
) |
| |
|
private |
implementation of hyper sparse pricing in the entering Simplex
Definition at line 588 of file spxdevexpr.cpp.
References DIdxSet::addIdx(), SPxDevexPR::bestPricesCo, VectorBase< R >::get_const_ptr(), SPxSolver::id(), IdxSet::index(), soplex::infinity, SPxSolver::isInfeasibleCo, SPxDevexPR::last, SPxPricer::NOT_VIOLATED, IdxSet::remove(), IdxSet::size(), SPxSolver::test(), SPxPricer::thesolver, SPxSolver::updateViolsCo, SPxPricer::VIOLATED, SPxPricer::VIOLATED_AND_CHECKED, and SPxPricer::weights.
Referenced by SPxDevexPR::selectEnterX().
implementation of hyper sparse pricing in the entering Simplex
Definition at line 506 of file spxdevexpr.cpp.
References DIdxSet::addIdx(), SPxDevexPR::bestPrices, SPxSolver::coId(), SPxSolver::coTest(), SPxPricer::coWeights, VectorBase< R >::get_const_ptr(), IdxSet::index(), soplex::infinity, SPxSolver::isInfeasible, SPxDevexPR::last, SPxPricer::NOT_VIOLATED, IdxSet::remove(), IdxSet::size(), SPxPricer::thesolver, SPxSolver::updateViols, SPxPricer::VIOLATED, and SPxPricer::VIOLATED_AND_CHECKED.
Referenced by SPxDevexPR::selectEnterX().
implementation of sparse pricing in the entering Simplex
Definition at line 708 of file spxdevexpr.cpp.
References VectorBase< R >::dim(), VectorBase< R >::get_const_ptr(), SPxSolver::id(), IdxSet::index(), SPxSolver::infeasibilitiesCo, SPxSolver::isInfeasibleCo, SPxDevexPR::last, SPxPricer::NOT_VIOLATED, IdxSet::remove(), IdxSet::size(), SPxSolver::test(), SPxPricer::thesolver, and SPxPricer::weights.
Referenced by SPxDevexPR::selectEnterX().
implementation of sparse pricing in the entering Simplex (slack variables)
Definition at line 669 of file spxdevexpr.cpp.
References SPxSolver::coId(), SPxSolver::coTest(), SPxPricer::coWeights, VectorBase< R >::dim(), VectorBase< R >::get_const_ptr(), IdxSet::index(), SPxSolver::infeasibilities, SPxSolver::isInfeasible, SPxDevexPR::last, SPxPricer::NOT_VIOLATED, IdxSet::remove(), IdxSet::size(), and SPxPricer::thesolver.
Referenced by SPxDevexPR::selectEnterX().
choose the best entering index among columns and rows but prefer sparsity
Definition at line 467 of file spxdevexpr.cpp.
References SPxSolver::basis(), SPxDevexPR::bestPrices, SPxDevexPR::bestPricesCo, SPxDevexPR::buildBestPriceVectorEnterCoDim(), SPxDevexPR::buildBestPriceVectorEnterDim(), SPxSolver::hyperPricingEnter, SPxId::isValid(), SPxDevexPR::last, SPxBasis::lastUpdate(), SPxDevexPR::selectEnterDenseCoDim(), SPxDevexPR::selectEnterDenseDim(), SPxDevexPR::selectEnterHyperCoDim(), SPxDevexPR::selectEnterHyperDim(), SPxDevexPR::selectEnterSparseCoDim(), SPxDevexPR::selectEnterSparseDim(), IdxSet::size(), SPxSolver::sparsePricingEnter, SPxSolver::sparsePricingEnterCo, SPARSITY_TRADEOFF, and SPxPricer::thesolver.
Referenced by SPxDevexPR::selectEnter().
Implements SPxPricer.
Definition at line 146 of file spxdevexpr.cpp.
References SPxSolver::basis(), SPxDevexPR::bestPrices, SPxDevexPR::buildBestPriceVectorLeave(), DEVEX_REFINETOL, SPxSolver::hyperPricingLeave, SPxBasis::lastUpdate(), MSG_INFO3, SPxDevexPR::selectLeaveHyper(), SPxDevexPR::selectLeaveSparse(), SPxDevexPR::selectLeaveX(), IdxSet::size(), SPxSolver::sparsePricingLeave, SPxSolver::spxout, SPxPricer::theeps, and SPxPricer::thesolver.
int selectLeaveHyper |
( |
Real |
feastol | ) |
|
|
private |
implementation of hyper sparse pricing in the leaving Simplex
Definition at line 240 of file spxdevexpr.cpp.
References DIdxSet::addIdx(), SPxDevexPR::bestPrices, SPxPricer::coWeights, SPxSolver::fTest(), VectorBase< R >::get_const_ptr(), IdxSet::index(), soplex::infinity, SPxSolver::isInfeasible, SPxDevexPR::last, SPxPricer::NOT_VIOLATED, IdxSet::remove(), IdxSet::size(), SPxPricer::thesolver, SPxSolver::updateViols, SPxPricer::VIOLATED, and SPxPricer::VIOLATED_AND_CHECKED.
Referenced by SPxDevexPR::selectLeave().
int selectLeaveSparse |
( |
Real |
feastol | ) |
|
|
private |
implementation of sparse pricing in the leaving Simplex
Definition at line 203 of file spxdevexpr.cpp.
References SPxPricer::coWeights, SPxSolver::fTest(), VectorBase< R >::get_const_ptr(), IdxSet::index(), SPxSolver::infeasibilities, SPxSolver::isInfeasible, SPxDevexPR::last, SPxPricer::NOT_VIOLATED, IdxSet::remove(), IdxSet::size(), SPxPricer::thesolver, SPxPricer::VIOLATED, and SPxPricer::VIOLATED_AND_CHECKED.
Referenced by SPxDevexPR::selectLeave().
int selectLeaveX |
( |
Real |
feastol, |
|
|
int |
start = 0 , |
|
|
int |
incr = 1 |
|
) |
| |
|
private |
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 92 of file spxdevexpr.cpp.
References SPxDevexPR::addedCoVecs(), SPxDevexPR::addedVecs(), SPxSolver::coDim(), SPxSolver::dim(), SPxDevexPR::isConsistent(), and SPxPricer::thesolver.
Referenced by SPxDevexPR::load(), SPxHybridPR::setRep(), and SPxAutoPR::setRep().
penalty, selected at last iteration.
Definition at line 50 of file spxdevexpr.h.
Referenced by SPxDevexPR::entered4(), SPxDevexPR::operator=(), SPxDevexPR::selectEnterDenseCoDim(), SPxDevexPR::selectEnterDenseDim(), SPxDevexPR::selectEnterHyperCoDim(), SPxDevexPR::selectEnterHyperDim(), SPxDevexPR::selectEnterSparseCoDim(), SPxDevexPR::selectEnterSparseDim(), SPxDevexPR::selectEnterX(), SPxDevexPR::selectLeaveHyper(), SPxDevexPR::selectLeaveSparse(), and SPxDevexPR::selectLeaveX().
|