49 #define SOPLEX_HYPERPRICINGTHRESHOLD 5000 50 #define SOPLEX_HYPERPRICINGSIZE 100 51 #define SOPLEX_SPARSITYFACTOR 0.6 52 #define SOPLEX_DENSEROUNDS 5 53 #define SOPLEX_SPARSITY_TRADEOFF 0.8 56 #define SOPLEX_MAXNCLCKSKIPS 32 57 #define SOPLEX_SAFETYFACTOR 1e-2 58 #define SOPLEX_NINITCALLS 200 487 spxout = &newOutstream;
492 virtual void setTolerances(std::shared_ptr<Tolerances> newTolerances)
507 const std::shared_ptr<Tolerances>&
tolerances()
const 600 virtual bool read(std::istream& in,
NameSet* rowNames = 0,
629 virtual void clear();
649 const NameSet* rowNames,
const NameSet* colNames,
const bool cpxFormat =
false)
const;
657 const NameSet* rowNames = NULL,
const NameSet* colNames = NULL,
const bool cpxFormat =
false)
const;
673 virtual Status solve(
volatile bool* interrupt = NULL,
bool polish =
true);
687 polishObj = _polishObj;
713 m_nonbasicValue = 0.0;
714 m_nonbasicValueUpToDate =
false;
797 virtual void printDisplayLine(
const bool force =
false,
const bool forceHead =
false);
848 this->entertolscale = d;
853 this->leavetolscale = d;
881 assert(timerType == theTime->
type());
882 assert(timerType == multTimeSparse->
type());
883 assert(timerType == multTimeFull->
type());
884 assert(timerType == multTimeColwise->
type());
885 assert(timerType == multTimeUnsetup->
type());
910 sparsePricingFactor = fac;
936 storeBasisSimplexFreq = freq;
963 fullPerturbation = full;
968 return basis().getMatrixMetric(type);
1020 virtual void changeObj(
int i,
const R& newVal,
bool scale =
false);
1030 virtual void changeMaxObj(
int i,
const R& newVal,
bool scale =
false);
1040 virtual void changeRowObj(
int i,
const R& newVal,
bool scale =
false);
1058 virtual void changeLower(
int i,
const R& newLower,
bool scale =
false);
1070 virtual void changeUpper(
int i,
const R& newUpper,
bool scale =
false);
1079 bool scale =
false);
1081 virtual void changeBounds(
int i,
const R& newLower,
const R& newUpper,
bool scale =
false);
1094 virtual void changeLhs(
int i,
const R& newLhs,
bool scale =
false);
1106 virtual void changeRhs(
int i,
const R& newRhs,
bool scale =
false);
1115 bool scale =
false);
1117 virtual void changeRange(
int i,
const R& newLhs,
const R& newRhs,
bool scale =
false);
1120 virtual void changeRange(
SPxRowId p_id,
const R& p_newLhs,
const R& p_newRhs,
bool scale =
false)
1141 virtual void changeElement(
int i,
int j,
const R& val,
bool scale =
false);
1240 return (*thevectors)[i];
1248 ? (*thevectors)[this->
number(rid)]
1256 ? (*thevectors)[this->
number(cid)]
1284 return (*thecovectors)[i];
1291 ? (*thecovectors)[this->
number(rid)]
1299 ? (*thecovectors)[this->
number(cid)]
1661 theShift +=
SOPLEX_MAX(to - theUBbound[i], 0.0);
1669 theShift +=
SOPLEX_MAX(theLBbound[i] - to, 0.0);
1677 theShift +=
SOPLEX_MAX(to - (*theUbound)[i], 0.0);
1678 (*theUbound)[i] = to;
1685 theShift +=
SOPLEX_MAX((*theLbound)[i] - to, 0.0);
1686 (*theLbound)[i] = to;
1693 theShift +=
SOPLEX_MAX(to - (*theCoUbound)[i], 0.0);
1694 (*theCoUbound)[i] = to;
1701 theShift +=
SOPLEX_MAX((*theCoLbound)[i] - to, 0.0);
1702 (*theCoLbound)[i] = to;
1708 virtual R
shift()
const 1733 int start = 0,
int incr = 1);
1737 int start = 0,
int incr = 1);
1834 virtual bool noViols(R tol)
const;
1875 bool leave(
int i,
bool polish =
false);
1920 virtual void init();
1942 initialized =
false;
1947 virtual void reDim();
1986 R& leaveMax, R& leavebound,
int& leaveNum,
StableSum<R>& objChange);
1989 R& enterBound, R& newUBbound,
1993 R& enterUB, R& enterLB, R& enterVal, R& enterMax,
2118 const int colsSize = -1)
const;
2155 bool getDualNorms(
int& nnormsRow,
int& nnormsCol, R* norms)
const;
2158 bool setDualNorms(
int nnormsRow,
int nnormsCol, R* norms);
2166 theCumulativeTime = 0.0;
2296 std::stringstream s;
2297 s <<
basis().statistics()
2298 <<
"Solution time : " << std::setw(10) << std::fixed << std::setprecision(
2299 2) <<
time() << std::endl
2300 <<
"Iterations : " << std::setw(10) <<
iterations() << std::endl;
2383 #include "spxsolver.hpp" 2384 #include "spxsolve.hpp" 2385 #include "changesoplex.hpp" 2386 #include "leave.hpp" 2387 #include "enter.hpp" 2388 #include "spxshift.hpp" 2389 #include "spxbounds.hpp" 2390 #include "spxchangebasis.hpp" 2391 #include "spxvecs.hpp" 2392 #include "spxwritestate.hpp" 2393 #include "spxfileio.hpp" 2394 #include "spxquality.hpp" 2396 #endif // _SPXSOLVER_H_ const VectorBase< R > & rhs() const
Returns right hand side vector.
bool freePricer
true iff thepricer should be freed inside of object
virtual void qualConstraintViolation(R &maxviol, R &sumviol) const
get violation of constraints.
virtual void setBasisSolver(SLinSolver< R > *slu, const bool destroy=false)
setup linear solver to use. If destroy is true, slusolver will be freed in destructor.
Real theCumulativeTime
cumulative time spent in all calls to method solve()
Timer * multTimeColwise
time spent in setupPupdate(), columnwise multiplication
virtual void changeLower(SPxColId p_id, const R &p_newLower, bool scale=false)
R sumDualDegeneracy()
get the sum of dual degeneracy
void setup4solve(SSVectorBase< R > *p_y, SSVectorBase< R > *p_rhs)
Setup vectors to be solved within Simplex loop.
void calculateProblemRanges()
determine ranges of problem values for bounds, sides and objective to assess numerical difficulties ...
virtual void changeRange(const VectorBase< R > &newLhs, const VectorBase< R > &newRhs, bool scale=false)
virtual bool terminate()
Termination criterion.
virtual void qualRedCostViolation(R &maxviol, R &sumviol) const
get violation of optimality criterion.
const SVectorBase< R > & vector(int i) const
i 'th vector.
Representation
LP basis representation.
VectorBase< R > low
vector of lower bounds.
SSVectorBase< R > * solveVector2
when 2 systems are to be solved at a time; typically for speepest edge weights
void scaleTolerances(R d)
int dualIterations()
return number of iterations done with primal algorithm
nothing known about basis status (possibly due to a singular basis in transformed problem) ...
solve() aborted due to time limit.
Bound flipping ratio test ("long step dual") for SoPlex.Class SPxBoundFlippingRT provides an implemen...
SPxRowId rId(int n) const
Returns the row identifier for row n.
variable fixed to identical bounds.
bool updateNonbasicValue(R objChange)
bool m_nonbasicValueUpToDate
true, if the stored objValue is up to date
bool isId(const SPxId &p_id) const
Is p_id an SPxId ?
void setEnterBound4Col(int, int)
virtual void changeRow(int i, const LPRowBase< R > &newRow, bool scale=false)
virtual void setupPupdate(void)
SPxColId colId(int i) const
ColId of i 'th column.
void resetCumulativeTime()
reset cumulative time counter to zero.
R epsilon() const
values are considered to be 0.
const SPxRatioTester< R > * ratiotester() const
return loaded SPxRatioTester.
SPxPricer< R > * thepricer
void shiftUPbound(int i, R to)
shift i 'th upBound to to.
const VectorBase< R > & upper() const
Returns upper bound vector.
virtual void changeLhs(const VectorBase< R > &newLhs, bool scale=false)
const VectorBase< R > & coPrhs() const
Right-hand side vector for coPvec.
UpdateVector< R > & fVec() const
feasibility vector.
maximize number of basic slack variables, i.e. more variables on bounds
Timer * multTimeSparse
time spent in setupPupdate() exploiting sparsity
virtual Status solve(volatile bool *interrupt=NULL, bool polish=true)
solve loaded LP.
VectorBase< R > * theCoLbound
Lower bound for covars.
Representation rep() const
return the current basis representation.
VarStatus getBasisRowStatus(int row) const
gets basis status for a single row
R dualDegenSum
the sum of the dual degeneracy percentage
VectorBase< R > theLBbound
Lower Basic Feasibility bound.
Timer * multTimeFull
time spent in setupPupdate() ignoring sparsity
Real time() const
time spent in last call to method solve().
Dense vector.Class VectorBase provides dense linear algebra vectors. Internally, VectorBase wraps std...
virtual void getLeaveVals(int i, typename SPxBasisBase< R >::Desc::Status &leaveStat, SPxId &leaveId, R &leaveMax, R &leavebound, int &leaveNum, StableSum< R > &objChange)
bool performSolutionPolishing()
Timer::TYPE timerType
type of timer (user or wallclock)
R leavetolscale
factor to temporarily decrease the leaving tolerance
variable set to its lower bound.
virtual void changeLower(const VectorBase< R > &newLower, bool scale=false)
const std::shared_ptr< Tolerances > & tolerances() const
returns current tolerances
virtual R shift() const
total current shift amount.
void computeLeaveCoPrhs4Col(int i, int n)
virtual R maxInfeas() const
maximal infeasibility of basis
virtual void computeLeaveCoPrhs()
compute theCoPrhs for leaving Simplex.
const VectorBase< R > & ucBound() const
void computeLeaveCoPrhs4Row(int i, int n)
virtual void changeRow(SPxRowId p_id, const LPRowBase< R > &p_newRow, bool scale=false)
void shiftUBbound(int i, R to)
shift i 'th ubBound to to.
int enterCycles
the number of degenerate steps during the entering algorithm
void computeFtest()
compute basis feasibility test vector.
VectorBase< R > coWeights
store dual norms
Random numbers.Class Random provides random Real variables, i.e. a value variable that gives another ...
virtual void perturbMinLeave(void)
void scaleEntertol(R d)
scale the entering tolerance
Sequential object-oriented SimPlex.SPxSolverBase is an LP solver class using the revised Simplex algo...
minimize number of basic slack variables, i.e. more variables in between bounds
virtual void computeEnterCoPrhs()
compute theCoPrhs for entering Simplex.
void resetClockStats()
resets clock average statistics
virtual Real terminationTime() const
return time limit.
void setType(Type tp)
set LEAVE or ENTER algorithm.
free variable fixed to zero.
bool isBasic(typename SPxBasisBase< R >::Desc::Status stat) const
does stat describe a basic index ?
SPxSolverBase< Real > SPxSolver
int primalCount
number of primal iterations
UpdateVector< R > & coPvec() const
copricing vector.
R objrange
absolute range of all objective coefficients in the problem
Simplex basis.Consider the linear program as provided from class SPxLP: where , and ...
int primalDegeneratePivots()
get number of primal degenerate pivots
SSVectorBase< R > * coSolveVector3
when 3 systems are to be solved at a time; typically reserved for bound flipping ratio test (basic so...
DIdxSet updateViols
store indices that were changed in the previous iteration and must be checked in hyper pricing ...
Dynamic sparse vectors.Class DSVectorBase implements dynamic sparse vectors, i.e. SVectorBases with a...
int enterDegenCand
the number of degenerate candidates in the entering algorithm
void getRhs(VectorBase< R > &p_rhs) const
copy rhs value VectorBase<R> to p_rhs.
const VectorBase< R > & lcBound() const
SPxRatioTester< R > * theratiotester
void invalidateBasis()
invalidates the basis, triggers refactorization
Safe arrays of arbitrary types.Class Array provides safe arrays of arbitrary type. Array elements are accessed just like ordinary C++ array elements by means of the index operator[](). Safety is provided by.
void setRep()
sets descriptor representation according to loaded LP.
int remainingRoundsEnterCo
int printBasisMetric
printing the current basis metric in the log (-1: off, 0: condition estimate, 1: trace, 2: determinant, 3: condition)
int subversion() const
return the internal subversion of SPxSolverBase as number
VectorBase< R > theURbound
Upper Row Feasibility bound.
virtual void addedCols(int n)
void setup4solve2(SSVectorBase< R > *p_y2, SSVectorBase< R > *p_rhs2)
Setup vectors to be solved within Simplex loop.
int number(const SPxRowId &id) const
Returns the row number of the row with identifier id.
const LPRowSetBase< R > & rows() const
return const lp's rows if available.
virtual Status getPrimalSol(VectorBase< R > &vector) const
get solution vector for primal variables.
Abstract ratio test base class.Class SPxRatioTester is the virtual base class for computing the ratio...
Real maxTime
maximum allowed time.
virtual void perturbMaxEnter(void)
perturb basis bounds.
const LPRowSetBase< R > * lprowset() const
Returns the LP as an LPRowSetBase.
bool enter(SPxId &id, bool polish=false)
const VectorBase< R > & test() const
Violations of pVec.
SoPlex start basis generation base class.SPxStarter is the virtual base class for classes generating ...
bool m_pricingViolUpToDate
true, if the stored violation is up to date
void setIntegralityInformation(int ncols, int *intInfo)
pass integrality information about the variables to the solver
int dualDegeneratePivots()
get number of dual degenerate pivots
DataArray< VarStatus > & getOldBasisStatusRows()
int remainingRoundsLeave
number of dense rounds/refactorizations until sparsePricing is enabled again
void setLeaveBound4Row(int i, int n)
Timer * multTimeUnsetup
time spent in setupPupdate() w/o sparsity information
void computePrimalray4Row(R direction)
virtual void init()
intialize data structures.
std::shared_ptr< Tolerances > _tolerances
const SVSetBase< R > * thevectors
the LP vectors according to representation
virtual Status getDualSol(VectorBase< R > &vector) const
get current solution VectorBase<R> for dual variables.
void computeDualfarkas4Row(R direction, SPxId enterId)
virtual void perturbMinEnter(void)
Ids for LP columns.Class SPxColId provides DataKeys for the column indices of an SPxLP.
void setRedCost(VectorBase< R > &p_vector)
virtual void getEnterVals2(int leaveIdx, R enterMax, R &leaveBound, StableSum< R > &objChange)
void setTiming(Timer::TYPE ttype)
set timing type
virtual R value()
current objective value.
bool leave(int i, bool polish=false)
VectorBase< R > theCoTest
virtual void changeMaxObj(const VectorBase< R > &newObj, bool scale=false)
virtual void changeCol(SPxColId p_id, const LPColBase< R > &p_newCol, bool scale=false)
const VectorBase< R > & ubBound() const
upper bound for fVec.
Pricing thePricing
full or partial pricing.
R objLimit
< the number of calls to the method isTimeLimitReached()
SPxStatus status() const
returns current SPxStatus.
SolutionPolish polishObj
objective of solution polishing
Sparse Linear Solver virtual base class.Class SLinSolver provides a class for solving sparse linear s...
VectorBase< R > up
vector of upper bounds.
R entertol() const
feasibility tolerance maintained by ratio test during ENTER algorithm.
virtual void doRemoveCol(int i)
void clearDualBounds(typename SPxBasisBase< R >::Desc::Status, R &, R &) const
don't perform modifications on optimal basis
void shiftLBbound(int i, R to)
shift i 'th lbBound to to.
virtual const SVectorBase< R > * enterVector(const SPxId &p_id)
Get pointer to the id 'th vector.
R theShift
sum of all shifts applied to any bound.
virtual void unInit()
uninitialize data structures.
bool fullPerturbation
whether to perturb the entire problem or just the bounds relevant for the current pivot ...
No Problem has been loaded.
SSVectorBase< R > * solveVector3rhs
when 3 systems are to be solved at a time; typically reserved for bound flipping ratio test (basic so...
Random random
The random number generator used throughout the whole computation. Its seed can be modified...
SPxColId cId(int n) const
Returns the column identifier for column n.
Saving LPs in a form suitable for SoPlex.
nothing known on loaded problem.
bool isInitialized() const
has the internal data been initialized?
bool m_pricingViolCoUpToDate
true, if the stored violation in coDim is up to date
SSVectorBase< R > * solveVector2rhs
when 2 systems are to be solved at a time; typically for speepest edge weights
LP has been solved to optimality.
void setSparsePricingFactor(R fac)
Semi sparse vector.This class implements semi-sparse vectors. Such are VectorBases where the indices ...
DataArray< VarStatus > & getOldBasisStatusCols()
int numCycle() const
actual number of degenerate simplex steps encountered so far.
void shiftUCbound(int i, R to)
shift i 'th ucBound to to.
SPxBasisBase< R >::Desc::Status varStatusToBasisStatusCol(int col, VarStatus stat) const
converts VarStatus to basis status for columns
bool hyperPricingLeave
true if hyper sparse pricing is turned on in the leaving Simplex
const SPxPricer< R > * pricer() const
return loaded SPxPricer.
void updateFtest()
update basis feasibility test vector.
bool sparsePricingEnter
true if sparsePricing is turned on in the entering Simplex for slack variables
virtual void setStarter(SPxStarter< R > *starter, const bool destroy=false)
setup starting basis generator to use. If destroy is true, starter will be freed in destructor...
const VectorBase< R > & fRhs() const
right-hand side vector for fVec
void setSolverStatus(typename SPxSolverBase< R >::Status stat)
setting the solver status external from the solve loop.
SPxSolverBase< R > & operator=(const SPxSolverBase< R > &base)
assignment operator
virtual void loadBasis(const typename SPxBasisBase< R >::Desc &)
set a start basis.
virtual void getLeaveVals2(R leaveMax, SPxId enterId, R &enterBound, R &newUBbound, R &newLBbound, R &newCoPrhs, StableSum< R > &objChange)
Generic Ids for LP rows or columns.Both SPxColIds and SPxRowIds may be treated uniformly as SPxIds: ...
Fast shifting ratio test.Class SPxFastRT is an implementation class of SPxRatioTester providing fast ...
SPxBasisBase< R >::Desc::Status varStatusToBasisStatusRow(int row, VarStatus stat) const
converts VarStatus to basis status for rows
R lastShift
for forcing feasibility.
bool isConsistent() const
check consistency.
solve() aborted due to detection of cycling.
SPxSense
Optimization sense.
SPxStarter< R > * thestarter
const Desc & desc() const
void setDual(VectorBase< R > &p_vector)
void computePrimalray4Col(R direction, SPxId enterId)
VarStatus basisStatusToVarStatus(typename SPxBasisBase< R >::Desc::Status stat) const
converts basis status to VarStatus
solve() aborted due to objective limit.
DataArray< int > integerVariables
supplementary variable information, 0: continous variable, 1: integer variable
LP is primal infeasible or unbounded.
bool weightsAreSetup
are the dual norms already set up?
Status getResult(R *value=0, VectorBase< R > *primal=0, VectorBase< R > *slacks=0, VectorBase< R > *dual=0, VectorBase< R > *reduCost=0)
get all results of last solve.
virtual void doPupdate(void)
virtual Status getPrimalray(VectorBase< R > &vector) const
get primal ray in case of unboundedness.
int leaveCount
number of LEAVE iterations
R m_pricingViolCo
maximal feasibility violation of current solution in coDim
virtual void reDim()
reset dimensions of vectors according to loaded LP.
SPxBasisBase< R >::Desc::Status covarStatus(int i) const
Status of i 'th covariable.
SPxId coId(int i) const
id of i 'th covector.
const VectorBase< R > & fTest() const
Violations of fVec.
void setMetricInformation(int type)
print basis metric within the usual output
int m_maxCycle
maximum steps before cycling is detected.
SPxSense spxSense() const
Returns the optimization sense.
void useFullPerturbation(bool full)
perturb entire problem or only the bounds relevant to the current pivot
const SPxBasisBase< R > & basis() const
Return current basis.
Dense VectorBase<R> with semi-sparse VectorBase<R> for updates.
std::ostream & operator<<(std::ostream &s, const VectorBase< R > &vec)
Output operator.
virtual R objValue()
get objective value of current solution.
Timer::TYPE getTiming()
set timing type
void setSolvingForBoosted(bool value)
void computeCoTest()
compute coTest vector.
void shiftLPbound(int i, R to)
shift i 'th lpBound to to.
const VectorBase< R > & coTest() const
violations of coPvec.
void scaleLeavetol(R d)
scale the leaving tolerance
virtual void changeRhs(SPxRowId p_id, const R &p_newRhs, bool scale=false)
void localAddRows(int start)
int totalboundflips
total number of bound flips
virtual void reinitializeVecs()
setup all vecs fresh
Wrapper for several output streams. A verbosity level is used to decide which stream to use and wheth...
virtual void changeCol(int i, const LPColBase< R > &newCol, bool scale=false)
std::string statistics() const
returns statistical information in form of a string.
int polishIterations()
return number of iterations done with primal algorithm
void computeEnterCoPrhs4Row(int i, int n)
int version() const
return the version of SPxSolverBase as number like 123 for 1.2.3
UpdateVector< R > primVec
primal vector
R sumPrimalDegeneracy()
get the sum of primal degeneracy
int multColwiseCalls
number of products, columnwise multiplication
const VectorBase< R > & lpBound() const
virtual bool readBasisFile(const char *filename, const NameSet *rowNames, const NameSet *colNames)
SSVectorBase< R > * coSolveVector2rhs
when 2 systems are to be solved at a time; typically for speepest edge weights
int nClckSkipsLeft
remaining number of times the clock can be safely skipped
void getNdualNorms(int &nnormsRow, int &nnormsCol) const
get number of dual norms
R leavetol() const
feasibility tolerance maintained by ratio test during LEAVE algorithm.
LP has been proven to be primal unbounded.
int info
user information to store values -1, 0, +1
virtual void doRemoveRows(int perm[])
int polishCount
number of solution polishing iterations
int multFullCalls
number of products ignoring sparsity
virtual void changeElement(SPxRowId rid, SPxColId cid, const R &val, bool scale=false)
const VectorBase< R > & lhs() const
Returns left hand side vector.
static Timer * switchTimer(Timer *timer, Timer::TYPE ttype)
bool isColBasic(int i) const
is the i 'th column vector basic ?
void forceRecompNonbasicValue()
void setBasis(const VarStatus rows[], const VarStatus cols[])
set the lp solver's basis.
void setStoreBasisFreqForBoosting(int freq)
void perturbMax(const UpdateVector< R > &vec, VectorBase< R > &low, VectorBase< R > &up, R eps, R delta, int start=0, int incr=1)
Abstract pricer base class.Class SPxPricer is a pure virtual class defining the interface for pricer ...
Dense Vector with semi-sparse Vector for updatesIn many algorithms vectors are updated in every itera...
bool isBasic(const SPxRowId &rid) const
is the rid 'th vector basic ?
variable set to its upper bound.
VectorBase< R > * theFrhs
R boundrange
absolute range of all bounds in the problem
UpdateVector< R > * theRPvec
row pricing vector
Dynamic index set.Class DIdxSet provides dynamic IdxSet in the sense, that no restrictions are posed ...
R getDegeneracyLevel(VectorBase< R > degenvec)
get level of dual degeneracy
const SVSetBase< R > * thecovectors
the LP coVectors according to representation
void setup4coSolve2(SSVectorBase< R > *p_z, SSVectorBase< R > *p_rhs)
Setup vectors to be cosolved within Simplex loop.
DataArray< VarStatus > oldBasisStatusCols
They don't have setters because only the internal simplex method is meant to fill them...
virtual Real time() const =0
UpdateVector< R > & pVec() const
pricing vector.
virtual void changeRhsStatus(int i, R newRhs, R oldRhs=0.0)
void setMemFactor(R f)
set refactor threshold for memory growth in current factor update compared to the last factorization ...
DSVectorBase< R > dualFarkas
stores dual farkas proof in case of infeasibility
virtual void addedRows(int n)
R siderange
absolute range of all side in the problem
bool sparsePricingLeave
These values enable or disable sparse pricing.
void initRep(Representation p_rep)
initialize ROW or COLUMN representation.
virtual void changeObj(const VectorBase< R > &newObj, bool scale=false)
scale determines whether the new data needs to be scaled according to the existing LP (persistent sca...
SOPLEX_THREADLOCAL const Real infinity
void setTolerances(std::shared_ptr< Tolerances > &tolerances)
set tolerances
bool initialized
true, if all vectors are setup.
bool hyperPricingEnter
true if hyper sparse pricing is turned on in the entering Simplex
virtual bool writeBasisFile(const char *filename, const NameSet *rowNames, const NameSet *colNames, const bool cpxFormat=false) const
SPxSolverBase(Type type=LEAVE, Representation rep=ROW, Timer::TYPE ttype=Timer::USER_TIME)
default constructor.
(In)equality for LPs.Class LPRowBase provides constraints for linear programs in the form where a is...
bool freeRatioTester
true iff theratiotester should be freed inside of object
virtual void clearRowObjs()
void setStatus(SPxStatus stat)
sets basis SPxStatus to stat.
SSVectorBase< R > * solveVector3
when 3 systems are to be solved at a time; typically reserved for bound flipping ratio test (basic so...
UpdateVector< R > * theCPvec
column pricing vector
void setOutstream(SPxOut &newOutstream)
void setEnterBound4Row(int, int)
virtual Status getDualfarkas(VectorBase< R > &vector) const
get dual farkas proof of infeasibility.
Type type() const
return current Type.
Pricing pricing() const
return current Pricing.
R m_nonbasicValue
nonbasic part of current objective value
virtual R getBasisMetric(int type)
Debugging, floating point type and parameter definitions.
virtual void factorize()
Factorize basis matrix.
Set of strings.Class NameSet implements a symbol or name table. It allows to store or remove names (i...
virtual void setTester(SPxRatioTester< R > *tester, const bool destroy=false)
setup ratio-tester to use. If destroy is true, tester will be freed in destructor.
bool getDualNorms(int &nnormsRow, int &nnormsCol, R *norms) const
get dual norms
int maxCycle() const
maximum number of degenerate simplex steps before we detect cycling.
VectorBase< R > weights
dual pricing norms
int boundFlips() const
get number of bound flips.
virtual void changeRowObj(const VectorBase< R > &newObj, bool scale=false)
void computeFrhs()
compute feasibility vector from scratch.
bool isRowBasic(int i) const
is the i 'th row vector basic ?
VectorBase< R > * theCoPrhs
VectorBase< R > * theUbound
Upper bound for vars.
virtual Status getRedCostSol(VectorBase< R > &vector) const
get vector of reduced costs.
virtual void changeBounds(const VectorBase< R > &newLower, const VectorBase< R > &newUpper, bool scale=false)
virtual void setTerminationTime(Real time=infinity)
set time limit.
UpdateVector< R > addVec
storage for thePvec = &addVec
bool isCoId(const SPxId &p_id) const
Is p_id a CoId.
R delta() const
guaranteed primal and dual bound violation for optimal solution, returning the maximum of floatingPoi...
const LPColSet & cols() const
return const lp's cols if available.
Everything should be within this namespace.
virtual void doRemoveCols(int perm[])
Basis is singular, numerical troubles?
SPxRowId rowId(int i) const
RowId of i 'th inequality.
int m_numViol
number of violations of current solution
const VectorBase< R > & lbBound() const
lower bound for fVec.
Array< UnitVectorBase< R > > unitVecs
array of unit vectors
virtual void setLeaveBounds()
void setLeaveBound4Col(int i, int n)
virtual void ungetEnterVal(SPxId enterId, typename SPxBasisBase< R >::Desc::Status enterStat, R leaveVal, const SVectorBase< R > &vec, StableSum< R > &objChange)
int maxIters
maximum allowed iterations.
void computeEnterCoPrhs4Col(int i, int n)
VectorBase< R > theLRbound
Lower Row Feasibility bound.
void setPrimalBounds()
setup feasibility bounds for entering algorithm
columnwise representation.
virtual void changeUpper(const VectorBase< R > &newUpper, bool scale=false)
Saving LPs in a form suitable for SoPlex.Class SPxLPBase provides the data structures required for sa...
void computeTest()
compute test VectorBase<R> in ENTERing Simplex.
virtual void setTerminationIter(int iteration=-1)
set iteration limit.
virtual bool writeState(const char *filename, const NameSet *rowNames=NULL, const NameSet *colNames=NULL, const bool cpxFormat=false) const
Set of LP columns.Class LPColSetBase implements a set of LPColBase%s. Unless for memory limitations...
void setNonzeroFactor(R f)
set refactor threshold for nonzeros in last factorized basis matrix compared to updated basis matrix ...
virtual void changeSense(typename SPxLPBase< R >::SPxSense sns)
virtual void clearUpdateVecs(void)
int multSparseCalls
number of products exploiting sparsity
virtual void clearRowObjs()
Clears row objective function values for all rows.
DataArray< int > isInfeasible
0: index not violated, 1: index violated, 2: index violated and among candidate list ...
void localAddCols(int start)
UpdateVector< R > dualVec
dual vector
virtual void changeRange(SPxRowId p_id, const R &p_newLhs, const R &p_newRhs, bool scale=false)
Save arrays of arbitrary types.
bool isCoBasic(int i) const
is the i 'th covector basic ?
bool isBasic(int i) const
is the i 'th vector basic ?
void shiftFvec()
Perform initial shifting to optain an feasible or pricable basis.
virtual R terminationValue() const
return objective limit.
virtual void changeRowObj(SPxRowId p_id, const R &p_newVal, bool scale=false)
virtual bool precisionReached(R &newpricertol) const
is the solution precise enough, or should we increase delta() ?
void getUpper(VectorBase< R > &p_up) const
copy upper bound VectorBase<R> to p_up.
bool sparsePricingEnterCo
true if sparsePricing is turned on in the entering Simplex
DSVectorBase< R > primalRay
stores primal ray in case of unboundedness
Saving LPs in a form suitable for SoPlex.
const LPColSetBase< R > * lpcolset() const
Returns the LP as an LPColSetBase.
void updateTest()
recompute test vector.
Real getMaxTime()
the maximum runtime
void perturbMin(const UpdateVector< R > &vec, VectorBase< R > &low, VectorBase< R > &up, R eps, R delta, int start=0, int incr=1)
void unscaleLPandReloadBasis()
unscales the LP and reloads the basis
virtual void changeElement(int i, int j, const R &val, bool scale=false)
virtual void changeObj(SPxColId p_id, const R &p_newVal, bool scale=false)
overloading a virtual function
bool isTimeLimitReached(const bool forceCheck=false)
returns whether current time limit is reached; call to time() may be skipped unless forceCheck is tru...
virtual void changeUpperStatus(int i, R newUpper, R oldLower=0.0)
void hyperPricing(bool h)
enable or disable hyper sparse pricing
Status m_status
status of algorithm.
Status getBasis(VarStatus rows[], VarStatus cols[], const int rowsSize=-1, const int colsSize=-1) const
get current basis, and return solver status.
SPxBasisBase< R >::Desc::Status varStatus(int i) const
Status of i 'th variable.
Timer * theTime
time spent in last call to method solve()
void setFillFactor(R f)
set refactor threshold for fill-in in current factor update compared to fill-in in last factorization...
void getLower(VectorBase< R > &p_low) const
copy lower bound VectorBase<R> to p_low.
bool isSPxRowId() const
is id a row id?
Set of LP rows.Class LPRowSetBase implements a set of LPRowBase%s. Unless for memory limitations...
int storeBasisSimplexFreq
number of simplex pivots -1 to perform before storing stable basis
virtual int terminationIter() const
return iteration limit.
int coDim() const
codimension.
int getMaxIters()
the maximum number of iterations
SolutionPolish getSolutionPolishing()
return objective of solution polishing
virtual void changeUpper(SPxColId p_id, const R &p_newUpper, bool scale=false)
overloading virtual function
virtual void printDisplayLine(const bool force=false, const bool forceHead=false)
print display line of flying table
void getLhs(VectorBase< R > &p_lhs) const
copy lhs value VectorBase<R> to p_lhs.
bool isValid() const
returns TRUE iff the id is a valid column or row identifier.
void setDisplayFreq(int freq)
set display frequency
virtual void changeRhs(const VectorBase< R > &newRhs, bool scale=false)
virtual void reLoad()
reload LP.
R m_pricingViol
maximal feasibility violation of current solution
void setPrimal(VectorBase< R > &p_vector)
int primalIterations()
return number of iterations done with primal algorithm
bool solvingForBoosted
is this solver involved in a higher precision solving scheme?
SPxLPBase< R >::SPxSense sense() const
optimization sense.
Type theType
entering or leaving algortihm.
virtual void setEnterBounds()
UpdateVector< R > * theFvec
virtual void setTolerances(std::shared_ptr< Tolerances > newTolerances)
set the _tolerances member variable
int iterations() const
get number of iterations of current solution.
void updateCoTest()
recompute coTest vector.
virtual void changeLhs(SPxRowId p_id, const R &p_newLhs, bool scale=false)
VectorBase< R > theUCbound
Upper Column Feasibility bound.
void setSlacks(VectorBase< R > &p_vector)
int iteration() const
returns number of basis changes since last load().
VectorBase< R > dualRhs
rhs VectorBase<R> for computing the dual vector
virtual void loadLP(const SPxLPBase< R > &LP, bool initSlackBasis=true)
copy LP.
VectorBase< R > * theLbound
Lower bound for vars.
virtual void setPricer(SPxPricer< R > *pricer, const bool destroy=false)
setup pricer to use. If destroy is true, pricer will be freed in destructor.
R nonbasicValue()
Compute part of objective value.
Status status() const
Status of solution process.
VectorBase< R > theUBbound
Upper Basic Feasibility bound.
#define SOPLEX_SUBVERSION
Sparse vectors.Class SVectorBase provides packed sparse vectors. Such are a sparse vectors...
UpdateVector< R > * thePvec
virtual void computeFrhsXtra()
int boundflips
number of performed bound flips
R sparsePricingFactor
enable sparse pricing when viols < factor * dim()
Ids for LP rows.Class SPxRowId provides DataKeys for the row indices of an SPxLP. ...
virtual void rejectLeave(int leaveNum, SPxId leaveId, typename SPxBasisBase< R >::Desc::Status leaveStat, const SVectorBase< R > *newVec=0)
UpdateVector< R > * theCoPvec
virtual void getEnterVals(SPxId id, R &enterTest, R &enterUB, R &enterLB, R &enterVal, R &enterMax, R &enterPric, typename SPxBasisBase< R >::Desc::Status &enterStat, R &enterRO, StableSum< R > &objChange)
virtual void changeMaxObj(SPxColId p_id, const R &p_newVal, bool scale=false)
overloading a virtual function
virtual void unShift(void)
remove shift as much as possible.
SPxBasisBase< R >::SPxStatus getBasisStatus() const
gets basis status
SPxOut * spxout
message handler
void setBasisStatus(typename SPxBasisBase< R >::SPxStatus stat)
set the lp solver's basis status.
VarStatus getBasisColStatus(int col) const
gets basis status for a single column
void shiftPvec()
Perform initial shifting to optain an feasible or pricable basis.
virtual void qualSlackViolation(R &maxviol, R &sumviol) const
get the residuum |Ax-b|.
solve() aborted due to iteration limit.
int getDisplayFreq()
get display frequency
const SLinSolver< R > * slinSolver() const
return loaded SLinSolver.
VectorBase< R > primRhs
rhs VectorBase<R> for computing the primal vector
virtual void qualBoundViolation(R &maxviol, R &sumviol) const
get violations of bounds.
virtual void perturbMaxLeave(void)
perturb nonbasic bounds.
virtual Status getSlacks(VectorBase< R > &vector) const
get VectorBase<R> of slack variables.
VectorBase< R > theLCbound
Lower Column Feasibility bound.
SPxStarter< R > * starter() const
return current starter.
virtual void doRemoveRow(int i)
bool freeStarter
true iff thestarter should be freed inside of object
const VectorBase< R > & upBound() const
bool recomputedVectors
flag to perform clean up step to reduce numerical errors only once
SolutionPolish
objective for solution polishing
int enterCount
number of ENTER iterations
DIdxSet infeasibilitiesCo
Representation theRep
row or column representation.
void setup4coSolve(SSVectorBase< R > *p_y, SSVectorBase< R > *p_rhs)
Setup vectors to be cosolved within Simplex loop.
virtual void rejectEnter(SPxId enterId, R enterTest, typename SPxBasisBase< R >::Desc::Status enterStat)
virtual void clear()
clear all data in solver.
DataArray< int > isInfeasibleCo
0: index not violated, 1: index violated, 2: index violated and among candidate list ...
R primalDegenSum
the sum of the primal degeneracy percentage
void computeFrhs2(VectorBase< R > &, VectorBase< R > &)
LP has a usable Basis (maybe LP is changed).
SSVectorBase< R > * coSolveVector3rhs
when 3 systems are to be solved at a time; typically reserved for bound flipping ratio test (basic so...
int dim() const
dimension of basis matrix.
SSVectorBase< R > * coSolveVector2
when 2 systems are to be solved at a time; typically for speepest edge weights
bool isBasisValid(DataArray< VarStatus > rows, DataArray< VarStatus > cols)
check a given basis for validity.
int m_numCycle
actual number of degenerate steps so far.
const SVectorBase< R > & unitVector(int i) const
return i 'th unit vector.
void shiftLCbound(int i, R to)
shift i 'th lcBound to to.
void setSolutionPolishing(SolutionPolish _polishObj)
set objective of solution polishing (0: off, 1: max_basic_slack, 2: min_basic_slack) ...
Wrapper for the system time query methods.
void setPricing(Pricing pr)
set FULL or PARTIAL pricing.
int num() const
Current number of SVectorBases.
virtual bool noViols(R tol) const
check for violations above tol and immediately return false w/o checking the remaining values ...
const VectorBase< R > & lower() const
Returns (internal and possibly scaled) lower bound vector.
bool isBasic(const SPxColId &cid) const
is the cid 'th vector basic ?
LP column.Class LPColBase provides a datatype for storing the column of an LP a the form similar to ...
Sparse vector set.Class SVSetBase provides a set of sparse vectors SVectorBase. All SVectorBases in a...
virtual void changeLhsStatus(int i, R newLhs, R oldLhs=0.0)
int leaveCycles
the number of degenerate steps during the leaving algorithm
int multUnsetupCalls
number of products w/o sparsity information
R entertolscale
factor to temporarily decrease the entering tolerance
virtual bool read(std::istream &in, NameSet *rowNames=0, NameSet *colNames=0, DIdxSet *intVars=0)
read LP from input stream.
virtual void changeLowerStatus(int i, R newLower, R oldLower=0.0)
bool setDualNorms(int nnormsRow, int nnormsCol, R *norms)
set dual norms
void computeDualfarkas4Col(R direction)
LP has been proven to be primal infeasible.
void computePvec()
compute entire pVec().
int leaveDegenCand
the number of degenerate candidates in the leaving algorithm
const SVectorBase< R > & coVector(int i) const
i 'th covector of LP.
virtual void setTerminationValue(R value=R(infinity))
set objective limit.
SPxId id(int i) const
id of i 'th vector.
DataArray< VarStatus > oldBasisStatusRows
stored stable basis met before a simplex pivot (used to warm start the solver)
virtual TYPE type()=0
return type of timer
VectorBase< R > * theCoUbound
Upper bound for covars.
bool isValid() const
returns TRUE, iff the DataKey is valid.
virtual void computeFrhs1(const VectorBase< R > &, const VectorBase< R > &)
Real cumulativeTime() const
cumulative time spent in all calls to method solve().
LP has beed solved to optimality but unscaled solution contains violations.