Scippy

SoPlex

Sequential object-oriented simPlex

Todo List
Member checkSolutionRational (SoPlex &soplex)
implement external check; currently we use the internal methods for convenience
Member checkSolutionReal (SoPlex &soplex)
implement external check; currently we use the internal methods for convenience
Member CLUFactor::eliminatePivot (int prow, int pos, Real eps)
If this test failes, lv has no value. I suppose that in this case none of the loops below that uses lv is executed. But this is unproven.
Member CLUFactor::forestUpdate (int col, Real *work, int num, int *nonz)

Use an extra member variable as a buffer for working with the dense row instead of misusing p_work. I think that should be as efficient and much cleaner.

Use an extra member variable as a buffer for the heap instead of misusing nonz and num. The method enQueueMin() seems to sort the nonzeros or something, for which it only needs some empty vector of size num.

Use an extra member variable as a buffer for the heap instead of misusing nonz and num. The method enQueueMin() seems to sort the nonzeros or something, for which it only needs some empty vector of size num.

Member CLUFactorRational::eliminatePivot (int prow, int pos)
If this test failes, lv has no value. I suppose that in this case none of the loops below that uses lv is executed. But this is unproven.
Member CLUFactorRational::forestUpdate (int col, Rational *work, int num, int *nonz)

Use an extra member variable as a buffer for working with the dense row instead of misusing p_work. I think that should be as efficient and much cleaner.

Use an extra member variable as a buffer for the heap instead of misusing nonz and num. The method enQueueMin() seems to sort the nonzeros or something, for which it only needs some empty vector of size num.

Use an extra member variable as a buffer for the heap instead of misusing nonz and num. The method enQueueMin() seems to sort the nonzeros or something, for which it only needs some empty vector of size num.

Class DataKey
data members should be private.
Member DataSet< DATA >::number (const DATA *item) const
Please check whether this is correctly implemented!
Class DSVectorBase< R >
Both DSVectorBase and SVectorBase have a member variable that points to allocated memory. This does not seem to make too much sense. Why doesn't DSVectorBase use the element of its base class?
Member DUPLICATE_ROWS
check: with this simplification step, the unsimplified basis seems to be slightly suboptimal for some instances
Member IdxSet::remove (int n)
Shouldn't this be an assert instead of an if (see add())
Member main (int argc, char *argv[])
the EGlib version info should be printed after the SoPlex version info
Member Rational::powRound ()
implement
Member Rational::sizeInBase (const int base=2) const
this is only correct for base 2
File slufactor.cpp

SLUfactor seems to be partly an wrapper for CLUFactor (was C). This should be properly integrated and demangled.

Does is make sense, to call x.clear() when next x.altValues() is called.

Member SLUFactor::load (const SVector *vec[], int dim)
if the factorization fails with stat = SINGULAR, distinuish between proven singularity (e.g., because of an empty column) and singularity due to numerics, that could be avoided by changing minStability and lastThreshold; in the first case, we want to abort, otherwise change the numerics
Member SLUFactor::solveLeft (Vector &x, const Vector &b)
Why is x.clear() here used and not with solveRight() ?
File slufactor_rational.cpp

SLUFactorRational seems to be partly an wrapper for CLUFactorRational (was C). This should be properly integrated and demangled.

Does is make sense, to call x.clear() when next x.altValues() is called.

Member SLUFactorRational::solveLeft (VectorRational &x, const VectorRational &b)
Why is x.clear() here used and not with solveRight() ?
Namespace soplex

SoPlex should also have an spxout object to avoid using a global one

introduce status codes for SoPlex, especially for rational solving

implement main IR loop for primal and dual feasible case with fail otherwise (Ambros)

implement statistical info (time, factor time, iters, ...) since last call to solveReal() or solveRational() (Ambros?)

implement performInfeasibilityIR (Ambros?)

extend IR loop to infeasible case (Dan?)

extend IR loop to unbounded case (Dan?)

integrate rational reconstruction into IR loop

templatize SPxSolver and necessary components (SLUFactor, pricer, ratiotester)

integrate rational SPxSolver and distinguish between original and transformed rational LP

rational scalers

rational simplifier

try to move to cpp file by forward declaration

implement automatic rep switch, based on row/col dim

record and return "best" solutions found during IR (Ambros)

interface rational reconstruction code for rational vectors

Member SoPlex::_computeInfeasBox (SolRational &sol, bool transformed)
this currently works only if all constraints are equations aggregate rows and sides using the multipliers of the Farkas ray
Member SoPlex::_ensureRealLPLoaded ()
this should not fail even if the basis is invalid (wrong dimension or wrong number of basic entries); fix either in SPxSolver or in SPxBasis
Member SoPlex::_invalidateSolution ()
maybe this should be done individually at the places when this method is called
Member SoPlex::_performOptIRStable (SolRational &sol, bool acceptUnbounded, bool acceptInfeasible, int minRounds, bool &primalFeasible, bool &dualFeasible, bool &infeasible, bool &unbounded, bool &stopped, bool &error)
remove _modObj and use dualScale * sol._redCost directly
Member SoPlex::_preprocessAndSolveReal (bool applyPreprocessing)

implement for both objective senses

this should not fail even if the basis is invalid (wrong dimension or wrong number of basic entries); fix either in SPxSolver or in SPxBasis

this should not fail even if the basis is invalid (wrong dimension or wrong number of basic entries); fix either in SPxSolver or in SPxBasis

Member SoPlex::_project (SolRational &sol)
if we know the mapping between original and lifting columns, we simply need to add the reduced cost of the lifting column to the reduced cost of the original column; this is not implemented now, because for optimal solutions the reduced costs of the lifting columns are zero
Member SoPlex::_reconstructSolutionRational (SolRational &sol, DataArray< SPxSolver::VarStatus > &basisStatusRows, DataArray< SPxSolver::VarStatus > &basisStatusCols, bool &stopped, bool &error, const Rational &denomBoundSquared)

we should compute them one by one so we can abort when encountering an infeasibility

we should compute them one by one so we can abort when encountering an infeasibility

we should compute them one by one so we can abort when encountering an infeasibility

Member SoPlex::_solveRational ()

implement row objectives with row representation

implement handling of row objectives in Cplex interface

this should be stored already earlier, possible switch use solRational above and solFeas here

set status to ABORT_VALUE if optimal solution exceeds objective limit

implement handling of row objectives in Cplex interface

this should be stored already earlier, possible switch use solRational above and solFeas here

set status to ABORT_VALUE if optimal solution exceeds objective limit

Member SoPlex::_solveRealForRational (bool fromscratch, VectorReal &primal, VectorReal &dual, DataArray< SPxSolver::VarStatus > &basisStatusRows, DataArray< SPxSolver::VarStatus > &basisStatusCols, bool &returnedBasis)

move to private helper methods

move to private helper methods

catch exception

move to private helper methods

catch exception

Member SoPlex::_syncLPReal (bool time=true)
try loading old basis
Member SoPlex::_transformFeasibility ()
exploit this case by returning without LP solving
Member SoPlex::_transformUnbounded ()
implement this without copying the objective function
Member soplex::reconstructSol (SolRational &solution)
make this a method of class SoPlex
Member SoPlex::Settings::Settings ()

which value?

define suitable values depending on Real type

define suitable values depending on Real type

define suitable values depending on Real type

define suitable values depending on Real type

define suitable values depending on Real type

Member SoPlex::SoPlex (const SoPlex &rhs)
improve performance by implementing a separate copy constructor
Member SoPlex::writeFileRational (const char *filename, const NameSet *rowNames=0, const NameSet *colNames=0, const DIdxSet *intvars=0) const
implement return value
Member SoPlex::writeFileReal (const char *filename, const NameSet *rowNames=0, const NameSet *colNames=0, const DIdxSet *intvars=0) const
implement return value
Member SPxBasis::changedCol (int)
is this correctly implemented?
Member SPxBasis::changedElement (int, int)
is this correctly implemented?
Member SPxBasis::changedRow (int)

Implement changedRow(), changedCol(), changedElement() in a more clever way. For instance, the basis won't be singular (but maybe infeasible) if the change doesn't affect the basis rows/columns.

is this correctly implemented?

is this correctly implemented?

Member SPxBasis::invalidate ()
is this correctly implemented?
Class SPxDevexPR
There seem to be problems with this pricer especially on the greenbe[ab] problems with the entering algorithm (row representation?).
Member SPxDevexPR::entered4 (SPxId id, int n)
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)
Member SPxDevexPR::setRep (SPxSolver::Representation)
suspicious: Shouldn't the relation between dim, coDim, Vecs, and CoVecs be influenced by the representation ?
File spxfileio.h
maybe rename this file (it is unrelated to spxfileio.cpp)
Class SPxHarrisRT
HarrisRT leads to cycling in dcmulti.sub.lp
Member SPxHarrisRT::degenerateEps () const
suspicious: *max is not set, but it is used (with the default setting *max=1) in selectLeave and selectEnter The question might be if max shouldn't be updated with themax?
Member SPxHarrisRT::maxDelta (Real *, Real *val, int num, const int *idx, const Real *upd, const Real *vec, const Real *low, const Real *up, Real epsilon) const
patch suggests using *max instead of themax
Member SPxHarrisRT::minDelta (Real *, Real *val, int num, const int *idx, const Real *upd, const Real *vec, const Real *low, const Real *up, Real epsilon) const

suspicious: *max is not set, but it is used (with the default setting *max=1) in selectLeave and selectEnter

patch suggests using *max instead of themax

patch suggests using *max instead of themax

Member SPxHybridPR::setType (SPxSolver::Type tp)
I changed from devex to steepest edge pricing here because of numerical difficulties, this should be investigated.
Member SPxLPBase< R >::addCols (const S *objValue, const S *lowerValues, const S *colValues, const int *colIndices, const int *colStarts, const int *colLengths, const int numCols, const int numValues, const S *upperValues)
implement the addition of new rows as in doAddCols()
Member SPxLPBase< R >::addRows (const S *lhsValues, const S *rowValues, const int *rowIndices, const int *rowStarts, const int *rowLengths, const int numRows, const int numValues, const S *rhsValues)
implement the addition of new columns as in doAddRows()
Member SPxLPBase< R >::read (std::istream &in, NameSet *rowNames=0, NameSet *colNames=0, DIdxSet *intVars=0)
Make sure the Id's in the NameSets are the same as in the LP.
Member SPxSolver::basisStatusToVarStatus (SPxBasis::Desc::Status stat) const
put the following basis methods near the variable status methods!
Member SPxSolver::changeMaxObj (int i, const Real &newVal)
Factorization remains valid, we do not need a reDim() pricing vectors should be recomputed.
Member SPxSolver::changeMaxObj (const Vector &newObj)
Factorization remains valid, we do not need a reDim() pricing vectors should be recomputed.
Member SPxSolver::changeObj (int i, const Real &newVal)
Factorization remains valid, we do not need a reDim() pricing vectors should be recomputed.
Member SPxSolver::changeObj (const Vector &newObj)
Factorization remains valid, we do not need a reDim() pricing vectors should be recomputed.
Member SPxSolver::changeRowObj (int i, const Real &newVal)
Factorization remains valid, we do not need a reDim() pricing vectors should be recomputed.
Member SPxSolver::changeRowObj (const Vector &newObj)
Factorization remains valid, we do not need a reDim() pricing vectors should be recomputed.
Member SPxSolver::computeFrhs ()
put this into a separate method
Member SPxSolver::enter (SPxId &id)
if shift() is not zero, we must not conclude primal unboundedness
Member SPxSolver::leave (int i)
if shift() is not zero we must not conclude unboundedness
Member SPxSolver::precisionReached (Real &newpricertol) const
check separately for ENTER and LEAVE algorithm
Member SPxSolver::setTerminationValue (Real value=infinity)
A first version for the termination value is implemented. Currently we check if no bound violations (shifting) is present. It might be even possible to use this termination value in case of bound violations (shifting) but in this case it is quite difficult to determine if we already reached the limit.
Member SPxSolver::solve ()

!= REGULAR is not enough. Also OPTIMAL/DUAL/PRIMAL should be tested and acted accordingly.

technically it would be ok to finish already when (priced && maxinfeas + shift() <= entertol()) is satisfied; maybe at least in the case when SoPlex keeps jumping back between ENTER and LEAVE always shifting (looping), we may relax this condition here; note also that unShift may increase shift() slightly due to roundoff errors

technically it would be ok to finish already when (priced && maxinfeas + shift() <= entertol()) is satisfied; maybe at least in the case when SoPlex keeps jumping back between ENTER and LEAVE always shifting (looping), we may relax this condition here; note also that unShift may increase shift() slightly due to roundoff errors

technically it would be ok to finish already when (priced && maxinfeas + shift() <= entertol()) is satisfied; maybe at least in the case when SoPlex keeps jumping back between ENTER and LEAVE always shifting (looping), we may relax this condition here; note also that unShift may increase shift() slightly due to roundoff errors

technically it would be ok to finish already when (priced && maxinfeas + shift() <= entertol()) is satisfied; maybe at least in the case when SoPlex keeps jumping back between ENTER and LEAVE always shifting (looping), we may relax this condition here; note also that unShift may increase shift() slightly due to roundoff errors

Member SPxSolver::Status
In spxchange, change the status to if (m_status > 0) m_status = REGULAR;
Member SPxSolver::testVecs ()
Error message "this shalt not be": shalt this be an assert (also below)?
Member SPxSolver::vector (const SPxId &p_id) const
The implementation does not exactly look like it will do what is promised in the describtion.
Member SPxSteepPR::selectLeaveX (Real tol)
this was an assert! is an assertion correct?
Member SPxWeightPR::computeRP (int start, int end)
TK04NOV98 here is a bug. solver()->rowVector(i).length() could be zero, so solver()->rowVector(i).length2() is also zero and we get an arithmetic exception.
Member SPxWeightST::setupWeights (SPxSolver &base)
The comments are wrong. The first is for dual simplex and the secound for primal one. Is anything else wrong? Also the values are nearly the same for both cases. Should this be ? Changed the values for r_fixed to 0 because of maros-r7. It is not clear why this makes a difference because all constraints in that instance are of equality type. Why is rowRight sometimes not set?
Member SSVectorBase< R >::multAdd (S xx, const SVectorBase< T > &vec)

SSVectorBase::multAdd() should be rewritten without pointer arithmetic.

SSVectorBase::multAdd() should be rewritten without pointer arithmetic.

SSVectorBase::multAdd() should be rewritten without pointer arithmetic.

Class SVectorBase< R >
SVectorBase should get a new implementation. There maybe a lot of memory lost due to padding the Nonzero structure. A better idea seems to be class SVectorBase { int size; int used; int* idx; R* val; }; which for several reasons could be faster or slower. If SVectorBase is changed, also DSVectorBase and SVSet have to be modified.
Class SVSetBase< R >::DLPSV
Check whether SVSetBase::DLPSV can be implemented as IdElement<SVectorBase>
Member SVSetBase< R >::ensureMem (int n, bool shortenLast=true)
use an independent parameter "memwastefactor" here
Class UnitVectorBase< R >

Several SVectorBase modification methods are still accessible for UnitVector. They might be used to change the vector.

UnitVectorBase memory management must be changed when SVectorBase is redesigned.

Member VectorBase< R >::get_ptr ()
check whether this non-const c-style access should indeed be public
Member VectorBase< R >::operator= (const SSVectorBase< S > &vec)
do we need this also in non-template version, because SSVectorBase can be automatically cast to VectorBase?