Scippy

SoPlex

Sequential object-oriented simPlex

SPxSolverBase< R > Class Template Reference

Sequential object-oriented SimPlex.SPxSolverBase is an LP solver class using the revised Simplex algorithm. It provides two basis representations, namely a column basis and a row basis (see Representation). For both representations, a primal and dual algorithm is available (see Type). More...

#include <spxbasis.h>

Public Types

Data Types
enum  Representation { ROW = -1, COLUMN = 1 }
 LP basis representation. More...
 
enum  Type { ENTER = -1, LEAVE = 1 }
 Algorithmic type. More...
 
enum  Pricing { FULL, PARTIAL }
 Pricing type. More...
 
enum  DecompStatus { FINDSTARTBASIS = 0, DONTFINDSTARTBASIS = 1 }
 Improved dual simplex status. More...
 
enum  VarStatus {
  ON_UPPER, ON_LOWER, FIXED, ZERO,
  BASIC, UNDEFINED
}
 
enum  Status {
  ERROR = -15, NO_RATIOTESTER = -14, NO_PRICER = -13, NO_SOLVER = -12,
  NOT_INIT = -11, ABORT_EXDECOMP = -10, ABORT_DECOMP = -9, ABORT_CYCLING = -8,
  ABORT_TIME = -7, ABORT_ITER = -6, ABORT_VALUE = -5, SINGULAR = -4,
  NO_PROBLEM = -3, REGULAR = -2, RUNNING = -1, UNKNOWN = 0,
  OPTIMAL = 1, UNBOUNDED = 2, INFEASIBLE = 3, INForUNBD = 4,
  OPTIMAL_UNSCALED_VIOLATIONS = 5
}
 
enum  SolutionPolish { POLISH_OFF, POLISH_INTEGRALITY, POLISH_FRACTIONALITY }
 objective for solution polishing More...
 
- Public Types inherited from SPxLPBase< R >
enum  SPxSense { MAXIMIZE = 1, MINIMIZE = -1 }
 Optimization sense. More...
 

Public Member Functions

void setOutstream (SPxOut &newOutstream)
 
void setNonzeroFactor (R f)
 set refactor threshold for nonzeros in last factorized basis matrix compared to updated basis matrix More...
 
void setFillFactor (R f)
 set refactor threshold for fill-in in current factor update compared to fill-in in last factorization More...
 
void setMemFactor (R f)
 set refactor threshold for memory growth in current factor update compared to the last factorization More...
 
UpdateVector< R > & fVec () const
 feasibility vector. More...
 
const VectorBase< R > & fRhs () const
 right-hand side vector for fVec More...
 
const VectorBase< R > & ubBound () const
 upper bound for fVec. More...
 
VectorBase< R > & ubBound ()
 upper bound for fVec, writable. More...
 
const VectorBase< R > & lbBound () const
 lower bound for fVec. More...
 
VectorBase< R > & lbBound ()
 lower bound for fVec, writable. More...
 
const VectorBase< R > & fTest () const
 Violations of fVec. More...
 
UpdateVector< R > & coPvec () const
 copricing vector. More...
 
const VectorBase< R > & coPrhs () const
 Right-hand side vector for coPvec. More...
 
const VectorBase< R > & ucBound () const
 
VectorBase< R > & ucBound ()
 upper bound for coPvec. More...
 
const VectorBase< R > & lcBound () const
 
VectorBase< R > & lcBound ()
 lower bound for coPvec. More...
 
const VectorBase< R > & coTest () const
 violations of coPvec. More...
 
UpdateVector< R > & pVec () const
 pricing vector. More...
 
const VectorBase< R > & upBound () const
 
VectorBase< R > & upBound ()
 upper bound for pVec. More...
 
const VectorBase< R > & lpBound () const
 
VectorBase< R > & lpBound ()
 lower bound for pVec. More...
 
const VectorBase< R > & test () const
 Violations of pVec. More...
 
computePvec (int i)
 compute and return pVec()[i]. More...
 
void computePvec ()
 compute entire pVec(). More...
 
computeTest (int i)
 compute and return test()[i] in ENTERing Simplex. More...
 
void computeTest ()
 compute test VectorBase<R> in ENTERing Simplex. More...
 
void testVecs ()
 
Access
int version () const
 return the version of SPxSolverBase as number like 123 for 1.2.3 More...
 
int subversion () const
 return the internal subversion of SPxSolverBase as number More...
 
Representation rep () const
 return the current basis representation. More...
 
Type type () const
 return current Type. More...
 
Pricing pricing () const
 return current Pricing. More...
 
SPxStarter< R > * starter () const
 return current starter. More...
 
Setup

Before solving an LP with an instance of SPxSolverBase, the following steps must be performed:

  1. Load the LP by copying an external LP or reading it from an input stream.
  2. Setup the pricer to use by loading an SPxPricer object (if not already done in a previous call).
  3. Setup the ratio test method to use by loading an SPxRatioTester object (if not already done in a previous call).
  4. Setup the linear system solver to use by loading an SLinSolver object (if not already done in a previous call).
  5. Optionally setup an start basis generation method by loading an SPxStarter object.
  6. Optionally setup a start basis by loading a SPxBasisBase<R>::Desc object.
  7. Optionally switch to another basis Representation by calling method setRep().
  8. Optionally switch to another algorithm Type by calling method setType().

Now the solver is ready for execution. If the loaded LP is to be solved again from scratch, this can be done with method reLoad(). Finally, clear() removes the LP from the solver.

virtual bool read (std::istream &in, NameSet *rowNames=0, NameSet *colNames=0, DIdxSet *intVars=0)
 read LP from input stream. More...
 
virtual void loadLP (const SPxLPBase< R > &LP, bool initSlackBasis=true)
 copy LP. More...
 
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. More...
 
virtual void setPricer (SPxPricer< R > *pricer, const bool destroy=false)
 setup pricer to use. If destroy is true, pricer will be freed in destructor. More...
 
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. More...
 
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. More...
 
virtual void loadBasis (const typename SPxBasisBase< R >::Desc &)
 set a start basis. More...
 
void initRep (Representation p_rep)
 initialize ROW or COLUMN representation. More...
 
void setRep (Representation p_rep)
 switch to ROW or COLUMN representation if not already used. More...
 
void setType (Type tp)
 set LEAVE or ENTER algorithm. More...
 
void setPricing (Pricing pr)
 set FULL or PARTIAL pricing. More...
 
void setDecompStatus (DecompStatus decomp_stat)
 turn on or off the improved dual simplex. More...
 
virtual void reLoad ()
 reload LP. More...
 
virtual void clear ()
 clear all data in solver. More...
 
void unscaleLPandReloadBasis ()
 unscales the LP and reloads the basis More...
 
void invalidateBasis ()
 invalidates the basis, triggers refactorization More...
 
virtual bool readBasisFile (const char *filename, const NameSet *rowNames, const NameSet *colNames)
 
virtual bool writeBasisFile (const char *filename, const NameSet *rowNames, const NameSet *colNames, const bool cpxFormat=false) const
 
virtual bool writeState (const char *filename, const NameSet *rowNames=NULL, const NameSet *colNames=NULL, const bool cpxFormat=false) const
 
Solving LPs
virtual Status solve (volatile bool *interrupt=NULL)
 solve loaded LP. More...
 
void performSolutionPolishing ()
 
void setSolutionPolishing (SolutionPolish _polishObj)
 set objective of solution polishing (0: off, 1: max_basic_slack, 2: min_basic_slack) More...
 
SolutionPolish getSolutionPolishing ()
 return objective of solution polishing More...
 
Status status () const
 Status of solution process. More...
 
virtual R value ()
 current objective value. More...
 
bool updateNonbasicValue (R objChange)
 
void forceRecompNonbasicValue ()
 
virtual Status getPrimalSol (VectorBase< R > &vector) const
 get solution vector for primal variables. More...
 
virtual Status getSlacks (VectorBase< R > &vector) const
 get VectorBase<R> of slack variables. More...
 
virtual Status getDualSol (VectorBase< R > &vector) const
 get current solution VectorBase<R> for dual variables. More...
 
virtual Status getRedCostSol (VectorBase< R > &vector) const
 get vector of reduced costs. More...
 
virtual Status getPrimalray (VectorBase< R > &vector) const
 get primal ray in case of unboundedness. More...
 
virtual Status getDualfarkas (VectorBase< R > &vector) const
 get dual farkas proof of infeasibility. More...
 
virtual void printDisplayLine (const bool force=false, const bool forceHead=false)
 print display line of flying table More...
 
virtual bool terminate ()
 Termination criterion. More...
 
Control Parameters
epsilon () const
 values \(|x| < \epsilon\) are considered to be 0. More...
 
entertol () const
 feasibility tolerance maintained by ratio test during ENTER algorithm. More...
 
leavetol () const
 feasibility tolerance maintained by ratio test during LEAVE algorithm. More...
 
feastol () const
 allowed primal feasibility tolerance. More...
 
opttol () const
 allowed optimality, i.e., dual feasibility tolerance. More...
 
delta () const
 guaranteed primal and dual bound violation for optimal solution, returning the maximum of feastol() and opttol(), i.e., the less tight tolerance. More...
 
void setFeastol (R d)
 set parameter feastol. More...
 
void setOpttol (R d)
 set parameter opttol. More...
 
void setDelta (R d)
 set parameter delta, i.e., set feastol and opttol to same value. More...
 
void setTiming (Timer::TYPE ttype)
 set timing type More...
 
Timer::TYPE getTiming ()
 set timing type More...
 
void setDisplayFreq (int freq)
 set display frequency More...
 
int getDisplayFreq ()
 get display frequency More...
 
void setMetricInformation (int type)
 print basis metric within the usual output More...
 
void setSparsePricingFactor (R fac)
 
void hyperPricing (bool h)
 enable or disable hyper sparse pricing More...
 
int maxCycle () const
 maximum number of degenerate simplex steps before we detect cycling. More...
 
int numCycle () const
 actual number of degenerate simplex steps encountered so far. More...
 
void useFullPerturbation (bool full)
 perturb entire problem or only the bounds relevant to the current pivot More...
 
virtual R getBasisMetric (int type)
 
Modification
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 scaling) More...
 
virtual void changeObj (int i, const R &newVal, bool scale=false)
 
virtual void changeObj (SPxColId p_id, const R &p_newVal, bool scale=false)
 overloading a virtual function More...
 
virtual void changeMaxObj (const VectorBase< R > &newObj, bool scale=false)
 
virtual void changeMaxObj (int i, const R &newVal, bool scale=false)
 
virtual void changeMaxObj (SPxColId p_id, const R &p_newVal, bool scale=false)
 overloading a virtual function More...
 
virtual void changeRowObj (const VectorBase< R > &newObj, bool scale=false)
 
virtual void changeRowObj (int i, const R &newVal, bool scale=false)
 
virtual void changeRowObj (SPxRowId p_id, const R &p_newVal, bool scale=false)
 
virtual void clearRowObjs ()
 
virtual void changeLowerStatus (int i, R newLower, R oldLower=0.0)
 
virtual void changeLower (const VectorBase< R > &newLower, bool scale=false)
 
virtual void changeLower (int i, const R &newLower, bool scale=false)
 
virtual void changeLower (SPxColId p_id, const R &p_newLower, bool scale=false)
 
virtual void changeUpperStatus (int i, R newUpper, R oldLower=0.0)
 
virtual void changeUpper (const VectorBase< R > &newUpper, bool scale=false)
 
virtual void changeUpper (int i, const R &newUpper, bool scale=false)
 
virtual void changeUpper (SPxColId p_id, const R &p_newUpper, bool scale=false)
 overloading virtual function More...
 
virtual void changeBounds (const VectorBase< R > &newLower, const VectorBase< R > &newUpper, bool scale=false)
 
virtual void changeBounds (int i, const R &newLower, const R &newUpper, bool scale=false)
 
virtual void changeBounds (SPxColId p_id, const R &p_newLower, const R &p_newUpper, bool scale=false)
 
virtual void changeLhsStatus (int i, R newLhs, R oldLhs=0.0)
 
virtual void changeLhs (const VectorBase< R > &newLhs, bool scale=false)
 
virtual void changeLhs (int i, const R &newLhs, bool scale=false)
 
virtual void changeLhs (SPxRowId p_id, const R &p_newLhs, bool scale=false)
 
virtual void changeRhsStatus (int i, R newRhs, R oldRhs=0.0)
 
virtual void changeRhs (const VectorBase< R > &newRhs, bool scale=false)
 
virtual void changeRhs (int i, const R &newRhs, bool scale=false)
 
virtual void changeRhs (SPxRowId p_id, const R &p_newRhs, bool scale=false)
 
virtual void changeRange (const VectorBase< R > &newLhs, const VectorBase< R > &newRhs, bool scale=false)
 
virtual void changeRange (int i, const R &newLhs, const R &newRhs, bool scale=false)
 
virtual void changeRange (SPxRowId p_id, const R &p_newLhs, const R &p_newRhs, bool scale=false)
 
virtual void changeRow (int i, const LPRowBase< R > &newRow, bool scale=false)
 
virtual void changeRow (SPxRowId p_id, const LPRowBase< R > &p_newRow, bool scale=false)
 
virtual void changeCol (int i, const LPColBase< R > &newCol, bool scale=false)
 
virtual void changeCol (SPxColId p_id, const LPColBase< R > &p_newCol, bool scale=false)
 
virtual void changeElement (int i, int j, const R &val, bool scale=false)
 
virtual void changeElement (SPxRowId rid, SPxColId cid, const R &val, bool scale=false)
 
virtual void changeSense (typename SPxLPBase< R >::SPxSense sns)
 
Dimension and codimension
int dim () const
 dimension of basis matrix. More...
 
int coDim () const
 codimension. More...
 
Variables and Covariables

Class SPxLPBase<R> introduces SPxIds to identify row or column data of an LP. SPxSolverBase uses this concept to access data with respect to the chosen representation.

SPxId id (int i) const
 id of i 'th vector. More...
 
SPxId coId (int i) const
 id of i 'th covector. More...
 
bool isId (const SPxId &p_id) const
 Is p_id an SPxId ? More...
 
bool isCoId (const SPxId &p_id) const
 Is p_id a CoId. More...
 
Vectors and Covectors
const SVectorBase< R > & vector (int i) const
 i 'th vector. More...
 
const SVectorBase< R > & vector (const SPxRowId &rid) const
 
const SVectorBase< R > & vector (const SPxColId &cid) const
 
const SVectorBase< R > & vector (const SPxId &p_id) const
 VectorBase<R> associated to p_id. More...
 
const SVectorBase< R > & coVector (int i) const
 i 'th covector of LP. More...
 
const SVectorBase< R > & coVector (const SPxRowId &rid) const
 
const SVectorBase< R > & coVector (const SPxColId &cid) const
 
const SVectorBase< R > & coVector (const SPxId &p_id) const
 coVector associated to p_id. More...
 
const SVectorBase< R > & unitVector (int i) const
 return i 'th unit vector. More...
 
Variable status

The Simplex basis assigns a Status to each variable and covariable. Depending on the representation, the status indicates that the corresponding vector is in the basis matrix or not.

SPxBasisBase< R >::Desc::Status varStatus (int i) const
 Status of i 'th variable. More...
 
SPxBasisBase< R >::Desc::Status covarStatus (int i) const
 Status of i 'th covariable. More...
 
bool isBasic (typename SPxBasisBase< R >::Desc::Status stat) const
 does stat describe a basic index ? More...
 
bool isBasic (const SPxId &p_id) const
 is the p_id 'th vector basic ? More...
 
bool isBasic (const SPxRowId &rid) const
 is the rid 'th vector basic ? More...
 
bool isBasic (const SPxColId &cid) const
 is the cid 'th vector basic ? More...
 
bool isRowBasic (int i) const
 is the i 'th row vector basic ? More...
 
bool isColBasic (int i) const
 is the i 'th column vector basic ? More...
 
bool isBasic (int i) const
 is the i 'th vector basic ? More...
 
bool isCoBasic (int i) const
 is the i 'th covector basic ? More...
 
Shifting

The task of the ratio test (implemented in SPxRatioTester classes) is to select a variable for the basis update, such that the basis remains priced (i.e. both, the pricing and copricing vectors satisfy their bounds) or feasible (i.e. the feasibility vector satisfies its bounds). However, this can lead to numerically instable basis matrices or – after accumulation of various errors – even to a singular basis matrix.

The key to overcome this problem is to allow the basis to become "a bit" infeasible or unpriced, in order provide a better choice for the ratio test to select a stable variable. This is equivalent to enlarging the bounds by a small amount. This is referred to as shifting.

These methods serve for shifting feasibility bounds, either in order to maintain numerical stability or initially for computation of phase 1. The sum of all shifts applied to any bound is stored in theShift.

The following methods are used to shift individual bounds. They are mainly intended for stable implenentations of SPxRatioTester.

void shiftFvec ()
 Perform initial shifting to optain an feasible or pricable basis. More...
 
void shiftPvec ()
 Perform initial shifting to optain an feasible or pricable basis. More...
 
void shiftUBbound (int i, R to)
 shift i 'th ubBound to to. More...
 
void shiftLBbound (int i, R to)
 shift i 'th lbBound to to. More...
 
void shiftUPbound (int i, R to)
 shift i 'th upBound to to. More...
 
void shiftLPbound (int i, R to)
 shift i 'th lpBound to to. More...
 
void shiftUCbound (int i, R to)
 shift i 'th ucBound to to. More...
 
void shiftLCbound (int i, R to)
 shift i 'th lcBound to to. More...
 
void testBounds () const
 
virtual R shift () const
 total current shift amount. More...
 
virtual void unShift (void)
 remove shift as much as possible. More...
 
virtual void qualConstraintViolation (R &maxviol, R &sumviol) const
 get violation of constraints. More...
 
virtual void qualBoundViolation (R &maxviol, R &sumviol) const
 get violations of bounds. More...
 
virtual void qualSlackViolation (R &maxviol, R &sumviol) const
 get the residuum |Ax-b|. More...
 
virtual void qualRedCostViolation (R &maxviol, R &sumviol) const
 get violation of optimality criterion. More...
 
SPxRowId rowId (int i) const
 RowId of i 'th inequality. More...
 
SPxColId colId (int i) const
 ColId of i 'th column. More...
 
 SPxSolverBase (Type type=LEAVE, Representation rep=ROW, Timer::TYPE ttype=Timer::USER_TIME)
 default constructor. More...
 
virtual ~SPxSolverBase ()
 
bool isConsistent () const
 check consistency. More...
 
SPxSolverBase< R > & operator= (const SPxSolverBase< R > &base)
 assignment operator More...
 
 SPxSolverBase (const SPxSolverBase< R > &base)
 copy constructor More...
 
- Public Member Functions inherited from SPxLPBase< R >
void setOutstream (SPxOut &newOutstream)
 
void unscaleLP ()
 unscales the lp and clears basis More...
 
bool isScaled () const
 Returns true if and only if the LP is scaled. More...
 
void setScalingInfo (bool scaled)
 set whether the LP is scaled or not More...
 
int nRows () const
 Returns number of rows in LP. More...
 
int nCols () const
 Returns number of columns in LP. More...
 
int nNzos () const
 Returns number of nonzeros in LP. More...
 
virtual R minAbsNzo (bool unscaled=true) const
 Absolute smallest non-zero element in (possibly scaled) LP. More...
 
virtual R maxAbsNzo (bool unscaled=true) const
 Absolute biggest non-zero element in (in rational case possibly scaled) LP. More...
 
void getRow (int i, LPRowBase< R > &row) const
 Gets i 'th row. More...
 
void getRow (const SPxRowId &id, LPRowBase< R > &row) const
 Gets row with identifier id. More...
 
void getRows (int start, int end, LPRowSetBase< R > &set) const
 Gets rows start, ... end. More...
 
const SVectorBase< R > & rowVector (int i) const
 Gets row vector of row i. More...
 
const SVectorBase< R > & rowVector (const SPxRowId &id) const
 Gets row vector of row with identifier id. More...
 
void getRowVectorUnscaled (int i, DSVectorBase< R > &vec) const
 Gets unscaled row vector of row i. More...
 
const VectorBase< R > & rhs () const
 Returns right hand side vector. More...
 
const R & rhs (int i) const
 Returns right hand side of row number i. More...
 
const R & rhs (const SPxRowId &id) const
 Returns right hand side of row with identifier id. More...
 
void getRhs (VectorBase< R > &vec) const
 Gets (internal and possibly scaled) right hand side vector. More...
 
void getRhsUnscaled (VectorBase< R > &vec) const
 Gets unscaled right hand side vector. More...
 
rhsUnscaled (int i) const
 Returns unscaled right hand side of row number i. More...
 
rhsUnscaled (const SPxRowId &id) const
 Returns unscaled right hand side of row with identifier id. More...
 
const VectorBase< R > & lhs () const
 Returns left hand side vector. More...
 
const R & lhs (int i) const
 Returns left hand side of row number i. More...
 
const R & lhs (const SPxRowId &id) const
 Returns left hand side of row with identifier id. More...
 
void getRowObj (VectorBase< R > &prowobj) const
 Gets row objective function vector. More...
 
rowObj (int i) const
 
rowObj (const SPxRowId &id) const
 Returns row objective function value of row with identifier id. More...
 
const VectorBase< R > & maxRowObj () const
 
const R & maxRowObj (int i) const
 
const R & maxRowObj (const SPxRowId &id) const
 Returns row objective function value of row with identifier id. More...
 
void getLhsUnscaled (VectorBase< R > &vec) const
 Returns unscaled left hand side vector. More...
 
lhsUnscaled (int i) const
 Returns unscaled left hand side of row number i. More...
 
lhsUnscaled (const SPxRowId &id) const
 Returns left hand side of row with identifier id. More...
 
LPRowBase< R >::Type rowType (int i) const
 Returns the inequality type of the i'th LPRow. More...
 
LPRowBase< R >::Type rowType (const SPxRowId &id) const
 Returns the inequality type of the row with identifier key. More...
 
void getCol (int i, LPColBase< R > &col) const
 Gets i 'th column. More...
 
void getCol (const SPxColId &id, LPColBase< R > &col) const
 Gets column with identifier id. More...
 
void getCols (int start, int end, LPColSetBase< R > &set) const
 Gets columns start, ..., end. More...
 
const SVectorBase< R > & colVector (int i) const
 Returns column vector of column i. More...
 
const SVectorBase< R > & colVector (const SPxColId &id) const
 Returns column vector of column with identifier id. More...
 
void getColVectorUnscaled (int i, DSVectorBase< R > &vec) const
 Gets column vector of column i. More...
 
void getColVectorUnscaled (const SPxColId &id, DSVectorBase< R > &vec) const
 Gets column vector of column with identifier id. More...
 
void getObjUnscaled (VectorBase< R > &pobj) const
 Gets unscaled objective vector. More...
 
void getObj (VectorBase< R > &pobj) const
 Gets objective vector. More...
 
obj (int i) const
 Returns objective value of column i. More...
 
obj (const SPxColId &id) const
 Returns objective value of column with identifier id. More...
 
objUnscaled (int i) const
 Returns unscaled objective value of column i. More...
 
objUnscaled (const SPxColId &id) const
 Returns unscaled objective value of column with identifier id. More...
 
const VectorBase< R > & maxObj () const
 Returns objective vector for maximization problem. More...
 
const R & maxObj (int i) const
 Returns objective value of column i for maximization problem. More...
 
const R & maxObj (const SPxColId &id) const
 Returns objective value of column with identifier id for maximization problem. More...
 
void maxObjUnscaled (VectorBase< R > &vec) const
 Returns unscaled objective vector for maximization problem. More...
 
maxObjUnscaled (int i) const
 Returns unscaled objective value of column i for maximization problem. More...
 
maxObjUnscaled (const SPxColId &id) const
 Returns unscaled objective value of column with identifier id for maximization problem. More...
 
const VectorBase< R > & upper () const
 Returns upper bound vector. More...
 
const R & upper (int i) const
 Returns upper bound of column i. More...
 
const R & upper (const SPxColId &id) const
 Returns upper bound of column with identifier id. More...
 
void getUpperUnscaled (VectorBase< R > &vec) const
 Gets unscaled upper bound vector. More...
 
upperUnscaled (int i) const
 Returns unscaled upper bound of column i. More...
 
upperUnscaled (const SPxColId &id) const
 Returns unscaled upper bound of column with identifier id. More...
 
const VectorBase< R > & lower () const
 Returns (internal and possibly scaled) lower bound vector. More...
 
const R & lower (int i) const
 Returns (internal and possibly scaled) lower bound of column i. More...
 
const R & lower (const SPxColId &id) const
 Returns (internal and possibly scaled) lower bound of column with identifier id. More...
 
void getLowerUnscaled (VectorBase< R > &vec) const
 Gets unscaled lower bound vector. More...
 
lowerUnscaled (int i) const
 Returns unscaled lower bound of column i. More...
 
lowerUnscaled (const SPxColId &id) const
 Returns unscaled lower bound of column with identifier id. More...
 
SPxSense spxSense () const
 Returns the optimization sense. More...
 
const R & objOffset () const
 Returns the objective function value offset. More...
 
int number (const SPxRowId &id) const
 Returns the row number of the row with identifier id. More...
 
int number (const SPxColId &id) const
 Returns the column number of the column with identifier id. More...
 
int number (const SPxId &id) const
 Returns the row or column number for identifier id. More...
 
bool has (const SPxRowId &id) const
 Returns the row number of the row with identifier id. More...
 
bool has (const SPxColId &id) const
 Returns the column number of the column with identifier id. More...
 
bool has (const SPxId &id) const
 Returns the row or column number for identifier id. More...
 
SPxRowId rId (int n) const
 Returns the row identifier for row n. More...
 
SPxColId cId (int n) const
 Returns the column identifier for column n. More...
 
virtual void addRow (const LPRowBase< R > &row, bool scale=false)
 
virtual void addRow (const R &lhsValue, const SVectorBase< R > &rowVec, const R &rhsValue, bool scale=false)
 
template<class S >
void addRow (const S *lhsValue, const S *rowValues, const int *rowIndices, int rowSize, const S *rhsValue)
 
virtual void addRow (SPxRowId &id, const LPRowBase< R > &row, bool scale=false)
 Adds row to LPRowSetBase. More...
 
virtual void addRows (const LPRowSetBase< R > &pset, bool scale=false)
 
template<class S >
void 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)
 
virtual void addRows (SPxRowId id[], const LPRowSetBase< R > &set, bool scale=false)
 adds all LPRowBases of pset to LPRowSetBase. More...
 
virtual void addCol (const LPColBase< R > &col, bool scale=false)
 
virtual void addCol (const R &objValue, const R &lowerValue, const SVectorBase< R > &colVec, const R &upperValue, bool scale=false)
 
template<class S >
void addCol (const S *objValue, const S *lowerValue, const S *colValues, const int *colIndices, int colSize, const S *upperValue)
 
virtual void addCol (SPxColId &id, const LPColBase< R > &col, bool scale=false)
 Adds col to LPColSetVBase. More...
 
virtual void addCols (const LPColSetBase< R > &pset, bool scale=false)
 
template<class S >
void 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)
 
virtual void addCols (SPxColId id[], const LPColSetBase< R > &set, bool scale=false)
 Adds all LPColBases of set to LPColSetBase. More...
 
virtual void removeRow (int i)
 Removes i 'th row. More...
 
virtual void removeRow (SPxRowId id)
 Removes row with identifier id. More...
 
virtual void removeRows (int perm[])
 Removes multiple rows. More...
 
virtual void removeRows (SPxRowId id[], int n, int perm[]=0)
 
virtual void removeRows (int nums[], int n, int perm[]=0)
 Removes n LPRowBases. More...
 
virtual void removeRowRange (int start, int end, int perm[]=0)
 Removes rows from start to end (including both). More...
 
virtual void removeCol (int i)
 Removes i 'th column. More...
 
virtual void removeCol (SPxColId id)
 Removes column with identifier id. More...
 
virtual void removeCols (int perm[])
 Removes multiple columns. More...
 
virtual void removeCols (SPxColId id[], int n, int perm[]=0)
 
virtual void removeCols (int nums[], int n, int perm[]=0)
 Removes n LPCols. More...
 
virtual void removeColRange (int start, int end, int perm[]=0)
 Removes columns from start to end (including both). More...
 
virtual bool readLPF (std::istream &in, NameSet *rowNames=0, NameSet *colNames=0, DIdxSet *intVars=0)
 Reads LP in LP format from input stream in. More...
 
virtual bool readMPS (std::istream &in, NameSet *rowNames=0, NameSet *colNames=0, DIdxSet *intVars=0)
 Reads an LP in MPS format from input stream in. More...
 
virtual bool readFile (const char *filename, NameSet *rowNames=0, NameSet *colNames=0, DIdxSet *intVars=0)
 Reads LP from a file. More...
 
virtual void writeLPF (std::ostream &out, const NameSet *rowNames, const NameSet *colNames, const DIdxSet *p_intvars=0) const
 
virtual void writeMPS (std::ostream &out, const NameSet *rowNames, const NameSet *colNames, const DIdxSet *p_intvars=0) const
 Writes a file in MPS format to out. More...
 
virtual void writeFileLPBase (const char *filename, const NameSet *rowNames=0, const NameSet *colNames=0, const DIdxSet *p_intvars=0) const
 Write loaded LP to filename. More...
 
void printProblemStatistics (std::ostream &os)
 
template<class S >
void changeObj (int i, const S *newVal)
 changes i 'th objective vector element to newVal. More...
 
template<class S >
void changeMaxObj (int i, const S *newVal)
 changes i 'th objective vector element to newVal. More...
 
template<class S >
void changeLower (int i, const S *newLower)
 changes i 'th lower bound to newLower. More...
 
template<class S >
void changeUpper (int i, const S *newUpper)
 Changes i 'th upper bound to newUpper. More...
 
template<class S >
void changeBounds (int i, const S *newLower, const S *newUpper)
 Changes bounds of column i to newLower and newUpper. More...
 
template<class S >
void changeLhs (int i, const S *newLhs)
 Changes i 'th left hand side value to newLhs. More...
 
template<class S >
void changeRange (int i, const S *newLhs, const S *newRhs)
 Changes left and right hand side of row i. More...
 
template<class S >
void changeElement (int i, int j, const S *val)
 Changes LP element (i, j) to val. More...
 
virtual void changeSense (SPxSense sns)
 Changes optimization sense to sns. More...
 
template<typename T >
void changeObjOffset (const T &o)
 
virtual void computePrimalActivity (const VectorBase< R > &primal, VectorBase< R > &activity, const bool unscaled=true) const
 Computes activity of the rows for a given primal vector; activity does not need to be zero. More...
 
virtual void addPrimalActivity (const SVectorBase< R > &primal, VectorBase< R > &activity) const
 Updates activity of the rows for a given primal vector; activity does not need to be zero. More...
 
virtual void computeDualActivity (const VectorBase< R > &dual, VectorBase< R > &activity, const bool unscaled=true) const
 Computes "dual" activity of the columns for a given dual vector, i.e., y^T A; activity does not need to be zero. More...
 
virtual void addDualActivity (const SVectorBase< R > &dual, VectorBase< R > &activity) const
 Updates "dual" activity of the columns for a given dual vector, i.e., y^T A; activity does not need to be zero. More...
 
virtual void subDualActivity (const VectorBase< R > &dual, VectorBase< R > &activity) const
 Updates "dual" activity of the columns for a given dual vector, i.e., y^T A; activity does not need to be zero. More...
 
virtual void buildDualProblem (SPxLPBase< R > &dualLP, SPxRowId primalRowIds[]=0, SPxColId primalColIds[]=0, SPxRowId dualRowIds[]=0, SPxColId dualColIds[]=0, int *nprimalrows=0, int *nprimalcols=0, int *ndualrows=0, int *ndualcols=0)
 Building the dual problem from a given LP. More...
 
bool isConsistent () const
 Consistency check. More...
 
 SPxLPBase ()
 Default constructor. More...
 
virtual ~SPxLPBase ()
 Destructor. More...
 
 SPxLPBase (const SPxLPBase< R > &old)
 Copy constructor. More...
 
template<class S >
 SPxLPBase (const SPxLPBase< S > &old)
 Copy constructor. More...
 
SPxLPBase< R > & operator= (const SPxLPBase< R > &old)
 Assignment operator. More...
 
template<class S >
SPxLPBase< R > & operator= (const SPxLPBase< S > &old)
 Assignment operator. More...
 

Public Attributes

Random random
 The random number generator used throughout the whole computation. Its seed can be modified. More...
 
DIdxSet infeasibilities
 
DIdxSet infeasibilitiesCo
 
DIdxSet updateViols
 store indices that were changed in the previous iteration and must be checked in hyper pricing More...
 
DIdxSet updateViolsCo
 
DataArray< int > isInfeasible
 0: index not violated, 1: index violated, 2: index violated and among candidate list More...
 
DataArray< int > isInfeasibleCo
 0: index not violated, 1: index violated, 2: index violated and among candidate list More...
 
bool sparsePricingLeave
 These values enable or disable sparse pricing. More...
 
bool sparsePricingEnter
 true if sparsePricing is turned on in the entering Simplex for slack variables More...
 
bool sparsePricingEnterCo
 true if sparsePricing is turned on in the entering Simplex More...
 
bool hyperPricingLeave
 true if hyper sparse pricing is turned on in the leaving Simplex More...
 
bool hyperPricingEnter
 true if hyper sparse pricing is turned on in the entering Simplex More...
 
int remainingRoundsLeave
 number of dense rounds/refactorizations until sparsePricing is enabled again More...
 
int remainingRoundsEnter
 
int remainingRoundsEnterCo
 
VectorBase< R > weights
 dual pricing norms More...
 
VectorBase< R > coWeights
 store dual norms More...
 
bool weightsAreSetup
 are the dual norms already set up? More...
 
TimermultTimeSparse
 time spent in setupPupdate() exploiting sparsity More...
 
TimermultTimeFull
 time spent in setupPupdate() ignoring sparsity More...
 
TimermultTimeColwise
 time spent in setupPupdate(), columnwise multiplication More...
 
TimermultTimeUnsetup
 time spent in setupPupdate() w/o sparsity information More...
 
int multSparseCalls
 number of products exploiting sparsity More...
 
int multFullCalls
 number of products ignoring sparsity More...
 
int multColwiseCalls
 number of products, columnwise multiplication More...
 
int multUnsetupCalls
 number of products w/o sparsity information More...
 
SPxOutspxout
 message handler More...
 
DataArray< int > integerVariables
 supplementary variable information, 0: continous variable, 1: integer variable More...
 
- Public Attributes inherited from SPxLPBase< R >
SPxOutspxout
 

Protected Member Functions

Precision
virtual bool precisionReached (R &newpricertol) const
 is the solution precise enough, or should we increase delta() ? More...
 
void calculateProblemRanges ()
 determine ranges of problem values for bounds, sides and objective to assess numerical difficulties More...
 
Protected helpers
virtual void addedRows (int n)
 
virtual void addedCols (int n)
 
virtual void doRemoveRow (int i)
 
virtual void doRemoveRows (int perm[])
 
virtual void doRemoveCol (int i)
 
virtual void doRemoveCols (int perm[])
 
void clearDualBounds (typename SPxBasisBase< R >::Desc::Status, R &, R &) const
 
void setDualColBounds ()
 
void setDualRowBounds ()
 
void setPrimalBounds ()
 setup feasibility bounds for entering algorithm More...
 
void setEnterBound4Col (int, int)
 
void setEnterBound4Row (int, int)
 
virtual void setEnterBounds ()
 
void setLeaveBound4Row (int i, int n)
 
void setLeaveBound4Col (int i, int n)
 
virtual void setLeaveBounds ()
 
void computePrimalray4Col (R direction, SPxId enterId)
 
void computePrimalray4Row (R direction)
 
void computeDualfarkas4Col (R direction)
 
void computeDualfarkas4Row (R direction, SPxId enterId)
 
- Protected Member Functions inherited from SPxLPBase< R >
R & rhs_w (int i)
 Returns right hand side of row i. More...
 
R & lhs_w (int i)
 Returns left hand side of row i. More...
 
R & maxRowObj_w (int i)
 Returns objective function value of row i. More...
 
R & maxObj_w (int i)
 Returns objective value of column i for maximization problem. More...
 
R & upper_w (int i)
 Returns upper bound of column i. More...
 
R & lower_w (int i)
 Returns lower bound of column i. More...
 
const LPRowSetBase< R > * lprowset () const
 Returns the LP as an LPRowSetBase. More...
 
const LPColSetBase< R > * lpcolset () const
 Returns the LP as an LPColSetBase. More...
 
void added2Set (SVSetBase< R > &set, const SVSetBase< R > &addset, int n)
 
- Protected Member Functions inherited from LPRowSetBase< R >
const SVSetBase< R > * rowSet () const
 Returns the complete SVSet. More...
 
int num () const
 Returns the number of LPRowBases in LPRowSetBase. More...
 
int max () const
 Returns the maximum number of LPRowBases that fit. More...
 
const VectorBase< R > & lhs () const
 Returns the vector of lhs values. More...
 
VectorBase< R > & lhs_w ()
 Returns the vector of lhs values. More...
 
const R & lhs (int i) const
 Returns the lhs of the i 'th LPRowBase. More...
 
R & lhs_w (int i)
 Returns the lhs of the i 'th LPRowBase. More...
 
const R & lhs (const DataKey &k) const
 Returns the lhs of the LPRowBase with DataKey k in LPRowSetBase. More...
 
R & lhs_w (const DataKey &k)
 Returns the lhs of the LPRowBase with DataKey k in LPRowSetBase. More...
 
const VectorBase< R > & rhs () const
 Returns the vector of rhs values. More...
 
VectorBase< R > & rhs_w ()
 Returns the vector of rhs values (writeable). More...
 
const R & rhs (int i) const
 Returns the rhs of the i 'th LPRowBase. More...
 
R & rhs_w (int i)
 Returns the rhs of the i 'th LPRowBase (writeable). More...
 
const R & rhs (const DataKey &k) const
 Returns the rhs of the LPRowBase with DataKey k in LPRowSetBase. More...
 
R & rhs_w (const DataKey &k)
 Returns the rhs of the LPRowBase with DataKey k in LPRowSetBase (writeable). More...
 
const VectorBase< R > & obj () const
 Returns the vector of objective coefficients. More...
 
VectorBase< R > & obj_w ()
 Returns the vector of objective coefficients (writeable). More...
 
const R & obj (int i) const
 Returns the objective coefficient of the i 'th LPRowBase. More...
 
R & obj_w (int i)
 Returns the objective coefficient of the i 'th LPRowBase (writeable). More...
 
const R & obj (const DataKey &k) const
 Returns the objective coefficient of the LPRowBase with DataKey k in LPRowSetBase. More...
 
R & obj_w (const DataKey &k)
 Returns the objective coefficient of the LPRowBase with DataKey k in LPRowSetBase (writeable). More...
 
SVectorBase< R > & rowVector_w (int i)
 Returns a writable rowVector of the i 'th LPRowBase. More...
 
const SVectorBase< R > & rowVector (int i) const
 Returns the rowVector of the i 'th LPRowBase. More...
 
SVectorBase< R > & rowVector_w (const DataKey &k)
 Returns a writable rowVector of the LPRowBase with DataKey k. More...
 
const SVectorBase< R > & rowVector (const DataKey &k) const
 Returns the rowVector of the LPRowBase with DataKey k. More...
 
LPRowBase< R >::Type type (int i) const
 Returns the inequalitiy type of the i 'th LPRowBase. More...
 
LPRowBase< R >::Type type (const DataKey &k) const
 Returns the inequality type of the LPRowBase with DataKey k. More...
 
void setType (int i, typename LPRowBase< R >::Type t)
 Changes the inequality type of row i to type. More...
 
const R & value (int i) const
 Returns the value of the i'th LPRowBase. More...
 
const R & value (const DataKey &k) const
 Returns the value of the LPRowBase with DataKey k. More...
 
DataKey key (int i) const
 Returns the DataKey of the i 'th LPRowBase in LPRowSetBase. More...
 
int number (const DataKey &k) const
 Returns the number of the LPRowBase with DataKey k in LPRowSetBase. More...
 
bool has (const DataKey &k) const
 does DataKey k belong to LPRowSetBase ? More...
 
void add (const LPRowBase< R > &row)
 
void add (DataKey &pkey, const LPRowBase< R > &prow)
 Adds row to LPRowSetBase. More...
 
void add (const R &plhs, const SVectorBase< R > &prowVector, const R &prhs, const R &pobj=0, const int &pscaleExp=0)
 Adds LPRowBase consisting of left hand side lhs, row vector rowVector, and right hand side rhs to LPRowSetBase. More...
 
template<class S >
void add (const S *lhsValue, const S *rowValues, const int *rowIndices, int rowSize, const S *rhsValue, const S *objValue=0)
 Adds LPRowBase consisting of left hand side lhs, row vector rowVector, and right hand side rhs to LPRowSetBase. More...
 
template<class S >
void add (DataKey &newkey, const S *lhsValue, const S *rowValues, const int *rowIndices, int rowSize, const S *rhsValue, const S *objValue=0)
 Adds LPRowBase consisting of left hand side lhs, row vector rowVector, and right hand side rhs to LPRowSetBase, with DataKey key. More...
 
void add (DataKey &newkey, const R &newlhs, const SVectorBase< R > &newrowVector, const R &newrhs, const R &newobj=0, const int &newscaleExp=0)
 Adds LPRowBase consisting of left hand side lhs, row vector rowVector, and right hand side rhs to LPRowSetBase, with DataKey key. More...
 
void add (const LPRowSetBase< R > &newset)
 
void add (DataKey keys[], const LPRowSetBase< R > &set)
 Adds all LPRowBases of set to LPRowSetBase. More...
 
void xtend (int n, int newmax)
 Extends row n to fit newmax nonzeros. More...
 
void xtend (const DataKey &pkey, int pnewmax)
 Extends row with DataKey key to fit newmax nonzeros. More...
 
void add2 (const DataKey &k, int n, const int idx[], const R val[])
 Adds n nonzero (idx, val)-pairs to rowVector with DataKey k. More...
 
void add2 (int i, int n, const int idx[], const R val[])
 Adds n nonzero (idx, val)-pairs to i 'th rowVector. More...
 
template<class S >
void add2 (int i, int n, const int idx[], const S val[])
 Adds n nonzero (idx, val)-pairs to i 'th rowVector. More...
 
SVectorBase< R > & create (int pnonzeros=0, const R &plhs=0, const R &prhs=1, const R &pobj=0, const int &pscaleExp=0)
 Creates new LPRowBase with specified parameters and returns a reference to its row vector. More...
 
SVectorBase< R > & create (DataKey &newkey, int nonzeros=0, const R &newlhs=0, const R &newrhs=1, const R &newobj=0, const int &newscaleExp=0)
 Creates new LPRowBase with specified parameters and returns a reference to its row vector. More...
 
void remove (int i)
 Removes i 'th LPRowBase. More...
 
void remove (const DataKey &k)
 Removes LPRowBase with DataKey k. More...
 
void remove (int perm[])
 Removes multiple LPRowBases. More...
 
void remove (const int nums[], int n)
 Removes n LPRowBases with row numbers given by nums. More...
 
void remove (const int nums[], int n, int *perm)
 Removes n LPRowBases with row numbers given by nums, Stores permutation of row indices in perm. More...
 
void clear ()
 Removes all LPRowBases. More...
 
void reMax (int newmax=0)
 Reallocates memory to be able to store newmax LPRowBases. More...
 
int memSize () const
 Returns number of used nonzero entries. More...
 
int memMax () const
 Returns length of nonzero memory. More...
 
void memRemax (int newmax)
 Reallocates memory to be able to store newmax nonzeros. More...
 
void memPack ()
 Garbage collection in nonzero memory. More...
 
bool isConsistent () const
 Checks consistency. More...
 
 LPRowSetBase (int pmax=-1, int pmemmax=-1)
 Default constructor. More...
 
LPRowSetBase< R > & operator= (const LPRowSetBase< R > &rs)
 Assignment operator. More...
 
template<class S >
LPRowSetBase< R > & operator= (const LPRowSetBase< S > &rs)
 Assignment operator. More...
 
 LPRowSetBase (const LPRowSetBase< R > &rs)
 Copy constructor. More...
 
template<class S >
 LPRowSetBase (const LPRowSetBase< S > &rs)
 Copy constructor. More...
 
virtual ~LPRowSetBase ()
 Destructor. More...
 
- Protected Member Functions inherited from SVSetBase< R >
void add (const SVectorBase< R > &svec)
 Adds svec to the set. More...
 
void add (DataKey &nkey, const SVectorBase< R > &svec)
 Adds svec to SVSetBase. More...
 
template<class S >
void add (DataKey &nkey, const S *rowValues, const int *rowIndices, int rowSize)
 Adds svec to SVSetBase. More...
 
void add (const SVectorBase< R > svec[], int n)
 Adds all n SVectorBases in the array svec to the set. More...
 
void add (DataKey nkey[], const SVectorBase< R > svec[], int n)
 Adds n SVectorBases to SVSetBase. More...
 
template<class S >
void add (const SVSetBase< S > &pset)
 Adds all SVectorBases in pset to SVSetBase. More...
 
template<class S >
void add (DataKey nkey[], const SVSetBase< S > &pset)
 Adds all SVectorBases of pset to SVSetBase. More...
 
SVectorBase< R > * create (int idxmax=0)
 Creates new SVectorBase in set. More...
 
SVectorBase< R > * create (DataKey &nkey, int idxmax=-1)
 Creates new SVectorBase in set. More...
 
void xtend (SVectorBase< R > &svec, int newmax)
 Extends svec to fit newmax nonzeros. More...
 
void add2 (SVectorBase< R > &svec, int idx, R val)
 Adds nonzero (idx, val) to svec of this SVSetBase. More...
 
void add2 (SVectorBase< R > &svec, int n, const int idx[], const R val[])
 Adds n nonzeros to svec of this SVSetBase. More...
 
template<class S >
void add2 (SVectorBase< R > &svec, int n, const int idx[], const S val[])
 Adds n nonzeros to svec of this SVSetBase. More...
 
void remove (const DataKey &removekey)
 Removes the vector with key removekey from the set. More...
 
void remove (int removenum)
 Removes the vector with number removenum from the set. More...
 
void remove (const SVectorBase< R > *svec)
 Removes one SVectorBase from set. More...
 
void remove (int perm[])
 Removes multiple elements. More...
 
void remove (const DataKey keys[], int n)
 Removes n SVectorBases from set. More...
 
void remove (const int nums[], int n)
 Removes n SVectorBases from set. More...
 
void remove (const DataKey keys[], int n, int *perm)
 
void remove (const int nums[], int n, int *perm)
 
void clear (int minNewSize=-1)
 Removes all SVectorBases from set. More...
 
SVectorBase< R > & operator[] (int n)
 Gets SVectorBase by number, writeable. More...
 
const SVectorBase< R > & operator[] (int n) const
 Gets SVectorBase by number. More...
 
SVectorBase< R > & operator[] (const DataKey &k)
 Gets SVectorBase by DataKey, writeable. More...
 
const SVectorBase< R > & operator[] (const DataKey &k) const
 Gets SVectorBase by DataKey. More...
 
int num () const
 Current number of SVectorBases. More...
 
int max () const
 Current maximum number of SVectorBases. More...
 
DataKey key (int n) const
 Gets DataKey of vector number. More...
 
DataKey key (const SVectorBase< R > *svec) const
 Gets DataKey of SVectorBase. More...
 
int number (const DataKey &k) const
 Gets vector number of DataKey. More...
 
int number (const SVectorBase< R > *svec) const
 Gets vector number of SVectorBase. More...
 
bool has (const DataKey &k) const
 True iff SVSetBase contains a SVectorBase for DataKey k. More...
 
bool has (int n) const
 True iff SVSetBase contains a SVectorBase for vector number n. More...
 
bool has (const SVectorBase< R > *svec) const
 Is an SVectorBase in the set? More...
 
int memSize () const
 Used nonzero memory. More...
 
int memMax () const
 Length of nonzero memory. More...
 
void memRemax (int newmax)
 Reset length of nonzero memory. More...
 
void memPack ()
 Garbage collection in nonzero memory. More...
 
void reMax (int newmax=0)
 Resets maximum number of SVectorBases. More...
 
bool isConsistent () const
 Consistency check. More...
 
 SVSetBase (int pmax=-1, int pmemmax=-1, double pfac=1.1, double pmemFac=1.2)
 Default constructor. More...
 
virtual ~SVSetBase ()
 Destructor. More...
 
SVSetBase< R > & operator= (const SVSetBase< R > &rhs)
 Assignment operator. More...
 
template<class S >
SVSetBase< R > & operator= (const SVSetBase< S > &rhs)
 Assignment operator. More...
 
 SVSetBase (const SVSetBase< R > &old)
 Copy constructor. More...
 
template<class S >
 SVSetBase (const SVSetBase< S > &old)
 Copy constructor. More...
 
- Protected Member Functions inherited from ClassArray< Nonzero< R > >
Nonzero< R > & operator[] (int n)
 Reference to n 'th element. More...
 
const Nonzero< R > & operator[] (int n) const
 Reference to n 'th const element. More...
 
Nonzero< R > & last ()
 Reference to last element. More...
 
const Nonzero< R > & last () const
 Reference to last const element. More...
 
Nonzero< R > * get_ptr ()
 Gets a C pointer to the data. More...
 
const Nonzero< R > * get_const_ptr () const
 Gets a const C pointer to the data. More...
 
void append (const Nonzero< R > &t)
 Appends element t. More...
 
void append (int n, const Nonzero< R > t[])
 Appends n elements from t. More...
 
void append (const ClassArray< Nonzero< R > > &t)
 Appends all elements from t. More...
 
void insert (int i, int n)
 Inserts n uninitialized elements before i 'th element. More...
 
void insert (int i, int n, const Nonzero< R > t[])
 Inserts n elements from t before i 'the element. More...
 
void insert (int i, const ClassArray< Nonzero< R > > &t)
 Inserts all elements from t before i 'th element. More...
 
void remove (int n=0, int m=1)
 Removes m elements starting at n. More...
 
void removeLast (int m=1)
 Removes m last elements. More...
 
void clear ()
 Removes all elements. More...
 
int size () const
 Returns number of elements. More...
 
void reSize (int newsize)
 Resets size to newsize. More...
 
int max () const
 Returns maximum number of elements. More...
 
ptrdiff_t reMax (int newMax=1, int newSize=-1)
 Resets maximum number of elements. More...
 
ClassArrayoperator= (const ClassArray &rhs)
 Assignment operator. More...
 
bool isConsistent () const
 Consistency check. More...
 
 ClassArray (const ClassArray &old)
 Copy constructor. More...
 
 ClassArray (int p_size=0, int p_max=0, double p_fac=1.2)
 Default constructor. More...
 
virtual ~ClassArray ()
 Destructor. More...
 
- Protected Member Functions inherited from LPColSetBase< R >
const SVSetBase< R > * colSet () const
 Returns the complete SVSetBase. More...
 
int num () const
 Returns the number of LPColBases currently in LPColSetBase. More...
 
int max () const
 Returns maximum number of LPColBases currently fitting into LPColSetBase. More...
 
const VectorBase< R > & maxObj () const
 
VectorBase< R > & maxObj_w ()
 Returns vector of objective values w.r.t. maximization. More...
 
const R & maxObj (int i) const
 
R & maxObj_w (int i)
 Returns objective value (w.r.t. maximization) of i 'th LPColBase in LPColSetBase. More...
 
const R & maxObj (const DataKey &k) const
 
R & maxObj_w (const DataKey &k)
 Returns objective value (w.r.t. maximization) of LPColBase with DataKey k in LPColSetBase. More...
 
const VectorBase< R > & lower () const
 
VectorBase< R > & lower_w ()
 Returns vector of lower bound values. More...
 
const R & lower (int i) const
 
R & lower_w (int i)
 Returns lower bound of i 'th LPColBase in LPColSetBase. More...
 
const R & lower (const DataKey &k) const
 
R & lower_w (const DataKey &k)
 Returns lower bound of LPColBase with DataKey k in LPColSetBase. More...
 
const VectorBase< R > & upper () const
 
VectorBase< R > & upper_w ()
 Returns vector of upper bound values. More...
 
const R & upper (int i) const
 
R & upper_w (int i)
 Returns upper bound of i 'th LPColBase in LPColSetBase. More...
 
const R & upper (const DataKey &k) const
 
R & upper_w (const DataKey &k)
 Returns upper bound of LPColBase with DataKey k in LPColSetBase. More...
 
SVectorBase< R > & colVector_w (int i)
 
const SVectorBase< R > & colVector (int i) const
 Returns colVector of i 'th LPColBase in LPColSetBase. More...
 
SVectorBase< R > & colVector_w (const DataKey &k)
 Returns writeable colVector of LPColBase with DataKey k in LPColSetBase. More...
 
const SVectorBase< R > & colVector (const DataKey &k) const
 Returns colVector of LPColBase with DataKey k in LPColSetBase. More...
 
DataKey key (int i) const
 Returns DataKey of i 'th LPColBase in LPColSetBase. More...
 
int number (const DataKey &k) const
 Returns number of LPColBase with DataKey k in LPColSetBase. More...
 
bool has (const DataKey &k) const
 Does DataKey k belong to LPColSetBase ? More...
 
void add (const LPColBase< R > &pcol)
 
void add (DataKey &pkey, const LPColBase< R > &pcol)
 Adds p pcol to LPColSetBase. More...
 
void add (const R &pobj, const R &plower, const SVectorBase< R > &pcolVector, const R &pupper, const int &pscaleExp=0)
 
void add (DataKey &newkey, const R &obj, const R &newlower, const SVectorBase< R > &newcolVector, const R &newupper, const int &newscaleExp=0)
 Adds LPColBase consisting of objective value obj, lower bound lower, column vector colVector and upper bound upper to LPColSetBase. More...
 
template<class S >
void add (const S *obj, const S *lowerValue, const S *colValues, const int *colIndices, int colSize, const S *upperValue)
 Adds LPColBase consisting of left hand side lhs, column vector colVector, and right hand side rhs to LPColSetBase. More...
 
template<class S >
void add (DataKey &newkey, const S *objValue, const S *lowerValue, const S *colValues, const int *colIndices, int colSize, const S *upperValue)
 Adds LPColBase consisting of left hand side lhs, column vector colVector, and right hand side rhs to LPColSetBase, with DataKey key. More...
 
void add (const LPColSetBase< R > &newset)
 
void add (DataKey keys[], const LPColSetBase< R > &newset)
 Adds all LPColBases of set to LPColSetBase. More...
 
void xtend (int n, int newmax)
 Extends column n to fit newmax nonzeros. More...
 
void xtend (const DataKey &pkey, int pnewmax)
 Extends column with DataKey key to fit newmax nonzeros. More...
 
void add2 (const DataKey &k, int n, const int idx[], const R val[])
 
void add2 (int i, int n, const int idx[], const R val[])
 Adds n nonzero (idx, val)-pairs to i 'th colVector. More...
 
template<class S >
void add2 (int i, int n, const int idx[], const S val[])
 Adds n nonzero (idx, val)-pairs to i 'th colVector. More...
 
SVectorBase< R > & create (int pnonzeros=0, const R &pobj=1, const R &plw=0, const R &pupp=1, const int &pscaleExp=0)
 
SVectorBase< R > & create (DataKey &newkey, int nonzeros=0, const R &obj=1, const R &newlow=0, const R &newup=1, const int &newscaleExp=0)
 Creates new LPColBase with specified arguments and returns a reference to its column vector. More...
 
void remove (int i)
 Removes i 'th LPColBase. More...
 
void remove (const DataKey &k)
 Removes LPColBase with DataKey k. More...
 
void remove (int perm[])
 Removes multiple elements. More...
 
void remove (const int nums[], int n)
 Removes LPColBases with numbers nums, where n is the length of the array nums. More...
 
void remove (const int nums[], int n, int *perm)
 Removes LPColBases with numbers nums, where n is the length of the array nums, and stores the index permutation in array perm. More...
 
void clear ()
 Removes all LPColBases from the set. More...
 
void reMax (int newmax=0)
 Reallocates memory to be able to store newmax LPColBases. More...
 
int memSize () const
 Returns used nonzero memory. More...
 
int memMax () const
 Returns length of nonzero memory. More...
 
void memRemax (int newmax)
 Resets length of nonzero memory. More...
 
void memPack ()
 Garbage collection in nonzero memory. More...
 
bool isConsistent () const
 Checks consistency. More...
 
 LPColSetBase (int pmax=-1, int pmemmax=-1)
 Default constructor. More...
 
LPColSetBase< R > & operator= (const LPColSetBase< R > &rs)
 Assignment operator. More...
 
template<class S >
LPColSetBase< R > & operator= (const LPColSetBase< S > &rs)
 Assignment operator. More...
 
 LPColSetBase (const LPColSetBase< R > &rs)
 Copy constructor. More...
 
template<class S >
 LPColSetBase (const LPColSetBase< S > &rs)
 Copy constructor. More...
 
virtual ~LPColSetBase ()
 Destructor. More...
 
- Protected Member Functions inherited from SPxBasisBase< R >
void loadMatrixVecs ()
 loads matrix according to the SPxIds stored in theBaseId. More...
 
void reDim ()
 resizes internal arrays. More...
 
void setRep ()
 sets descriptor representation according to loaded LP. More...
 
SPxStatus status () const
 returns current SPxStatus. More...
 
void setStatus (SPxStatus stat)
 sets basis SPxStatus to stat. More...
 
void setMaxUpdates (int maxUp)
 change maximum number of iterations until a refactorization is performed More...
 
int getMaxUpdates () const
 returns maximum number of updates before a refactorization is performed More...
 
const Descdesc () const
 
Descdesc ()
 returns current basis Descriptor. More...
 
Desc::Status dualColStatus (int i) const
 dual Status for the i'th column variable of the loaded LP. More...
 
Desc::Status dualStatus (const SPxColId &id) const
 dual Status for the column variable with ID id of the loaded LP. More...
 
Desc::Status dualRowStatus (int i) const
 dual Status for the i'th row variable of the loaded LP. More...
 
Desc::Status dualStatus (const SPxRowId &id) const
 dual Status for the row variable with ID id of the loaded LP. More...
 
Desc::Status dualStatus (const SPxId &id) const
 dual Status for the variable with ID id of the loaded LP. More...
 
SPxIdbaseId (int i)
 
SPxId baseId (int i) const
 returns the Id of the i'th basis vector. More...
 
const SVectorBase< R > & baseVec (int i) const
 returns the i'th basic vector. More...
 
SPxId lastEntered () const
 returns SPxId of last VectorBase<R> included to the basis. More...
 
SPxId lastLeft () const
 returns SPxId of last vector that left the basis. More...
 
int lastIndex () const
 returns index in basis where last update was done. More...
 
int lastUpdate () const
 returns number of basis changes since last refactorization. More...
 
int iteration () const
 returns number of basis changes since last load(). More...
 
int prevIteration () const
 returns the number of iterations prior to the last break in execution More...
 
int lastDegenCheck () const
 returns the number of iterations since the last degeneracy check More...
 
SPxSolverBase< R > * solver () const
 returns loaded solver. More...
 
VectorBase< R > & multBaseWith (VectorBase< R > &x) const
 Basis-vector product. More...
 
void multBaseWith (SSVectorBase< R > &x, SSVectorBase< R > &result) const
 Basis-vector product. More...
 
VectorBase< R > & multWithBase (VectorBase< R > &x) const
 Vector-basis product. More...
 
void multWithBase (SSVectorBase< R > &x, SSVectorBase< R > &result) const
 VectorBase<R>-basis product. More...
 
condition (int maxiters=10, R tolerance=1e-6)
 
getEstimatedCondition ()
 
getExactCondition ()
 
getMatrixMetric (int type=0)
 
stability () const
 returns the stability of the basis matrix. More...
 
void solve (VectorBase< R > &x, const VectorBase< R > &rhs)
 
void solve (SSVectorBase< R > &x, const SVectorBase< R > &rhs)
 
void solve4update (SSVectorBase< R > &x, const SVectorBase< R > &rhs)
 solves linear system with basis matrix. More...
 
void solve4update (SSVectorBase< R > &x, VectorBase< R > &y, const SVectorBase< R > &rhsx, SSVectorBase< R > &rhsy)
 solves two systems in one call. More...
 
void solve4update (SSVectorBase< R > &x, SSVectorBase< R > &y, const SVectorBase< R > &rhsx, SSVectorBase< R > &rhsy)
 solves two systems in one call using only sparse data structures More...
 
void solve4update (SSVectorBase< R > &x, VectorBase< R > &y, VectorBase< R > &y2, const SVectorBase< R > &rhsx, SSVectorBase< R > &rhsy, SSVectorBase< R > &rhsy2)
 solves three systems in one call. More...
 
void solve4update (SSVectorBase< R > &x, SSVectorBase< R > &y, SSVectorBase< R > &y2, const SVectorBase< R > &rhsx, SSVectorBase< R > &rhsy, SSVectorBase< R > &rhsy2)
 solves three systems in one call using only sparse data structures More...
 
void coSolve (VectorBase< R > &x, const VectorBase< R > &rhs)
 Cosolves linear system with basis matrix. More...
 
void coSolve (SSVectorBase< R > &x, const SVectorBase< R > &rhs)
 Sparse version of coSolve. More...
 
void coSolve (SSVectorBase< R > &x, VectorBase< R > &y, const SVectorBase< R > &rhsx, SSVectorBase< R > &rhsy)
 solves two systems in one call. More...
 
void coSolve (SSVectorBase< R > &x, SSVectorBase< R > &y, const SVectorBase< R > &rhsx, SSVectorBase< R > &rhsy)
 Sparse version of solving two systems in one call. More...
 
void coSolve (SSVectorBase< R > &x, VectorBase< R > &y, VectorBase< R > &z, const SVectorBase< R > &rhsx, SSVectorBase< R > &rhsy, SSVectorBase< R > &rhsz)
 solves three systems in one call. May be improved by using just one pass through the basis. More...
 
void coSolve (SSVectorBase< R > &x, SSVectorBase< R > &y, SSVectorBase< R > &z, const SVectorBase< R > &rhsx, SSVectorBase< R > &rhsy, SSVectorBase< R > &rhsz)
 Sparse version of solving three systems in one call. More...
 
void addedRows (int n)
 inform SPxBasisBase, that n new rows had been added. More...
 
void removedRow (int i)
 inform SPxBasisBase that row i had been removed. More...
 
void removedRows (const int perm[])
 inform SPxBasisBase that rows in perm with negative entry were removed. More...
 
void addedCols (int n)
 inform SPxBasisBase that n new columns had been added. More...
 
void removedCol (int i)
 inform SPxBasisBase that column i had been removed. More...
 
void removedCols (const int perm[])
 inform SPxBasisBase that columns in perm with negative entry were removed. More...
 
void changedRow (int)
 inform SPxBasisBase that a row had been changed. More...
 
void changedCol (int)
 inform SPxBasisBase that a column had been changed. More...
 
void changedElement (int, int)
 inform SPxBasisBase that a matrix entry had been changed. More...
 
virtual void change (int i, SPxId &id, const SVectorBase< R > *enterVec, const SSVectorBase< R > *eta=0)
 performs basis update. More...
 
virtual bool readBasis (std::istream &in, const NameSet *rowNames, const NameSet *colNames)
 
virtual void writeBasis (std::ostream &os, const NameSet *rownames, const NameSet *colnames, const bool cpxFormat=false) const
 
virtual void printMatrix () const
 
void printMatrixMTX (int number)
 
virtual bool isDescValid (const Desc &ds)
 checks if a Descriptor is valid for the current LP w.r.t. its bounds More...
 
virtual void loadDesc (const Desc &)
 sets up basis. More...
 
virtual void loadBasisSolver (SLinSolver< R > *solver, const bool destroy=false)
 sets up linear solver to use. More...
 
virtual void load (SPxSolverBase< R > *lp, bool initSlackBasis=true)
 loads the LP lp to the basis. More...
 
virtual void unLoad ()
 unloads the LP from the basis. More...
 
void invalidate ()
 invalidates actual basis. More...
 
void restoreInitialBasis ()
 Restores initial basis. More...
 
void dump ()
 output basis entries. More...
 
bool isConsistent () const
 consistency check. More...
 
Real getTotalUpdateTime () const
 time spent in updates More...
 
int getTotalUpdateCount () const
 number of updates performed More...
 
std::string statistics () const
 returns statistical information in form of a string. More...
 
void setOutstream (SPxOut &newOutstream)
 
 SPxBasisBase (Timer::TYPE ttype=Timer::USER_TIME)
 default constructor. More...
 
 SPxBasisBase (const SPxBasisBase< R > &old)
 copy constructor More...
 
SPxBasisBase< R > & operator= (const SPxBasisBase< R > &rhs)
 assignment operator More...
 
virtual ~SPxBasisBase ()
 destructor. More...
 

Protected Attributes

Protected data
Array< UnitVectorBase< R > > unitVecs
 array of unit vectors More...
 
const SVSetBase< R > * thevectors
 the LP vectors according to representation More...
 
const SVSetBase< R > * thecovectors
 the LP coVectors according to representation More...
 
VectorBase< R > primRhs
 rhs VectorBase<R> for computing the primal vector More...
 
UpdateVector< R > primVec
 primal vector More...
 
VectorBase< R > dualRhs
 rhs VectorBase<R> for computing the dual vector More...
 
UpdateVector< R > dualVec
 dual vector More...
 
UpdateVector< R > addVec
 storage for thePvec = &addVec More...
 
VectorBase< R > theURbound
 Upper Row Feasibility bound. More...
 
VectorBase< R > theLRbound
 Lower Row Feasibility bound. More...
 
VectorBase< R > theUCbound
 Upper Column Feasibility bound. More...
 
VectorBase< R > theLCbound
 Lower Column Feasibility bound. More...
 
VectorBase< R > theUBbound
 Upper Basic Feasibility bound. More...
 
VectorBase< R > theLBbound
 Lower Basic Feasibility bound. More...
 
VectorBase< R > * theFrhs
 
UpdateVector< R > * theFvec
 
VectorBase< R > * theCoPrhs
 
UpdateVector< R > * theCoPvec
 
UpdateVector< R > * thePvec
 
UpdateVector< R > * theRPvec
 row pricing vector More...
 
UpdateVector< R > * theCPvec
 column pricing vector More...
 
VectorBase< R > * theUbound
 Upper bound for vars. More...
 
VectorBase< R > * theLbound
 Lower bound for vars. More...
 
VectorBase< R > * theCoUbound
 Upper bound for covars. More...
 
VectorBase< R > * theCoLbound
 Lower bound for covars. More...
 
VectorBase< R > theCoTest
 
VectorBase< R > theTest
 
DSVectorBase< R > primalRay
 stores primal ray in case of unboundedness More...
 
DSVectorBase< R > dualFarkas
 stores dual farkas proof in case of infeasibility More...
 
int leaveCount
 number of LEAVE iterations More...
 
int enterCount
 number of ENTER iterations More...
 
int primalCount
 number of primal iterations More...
 
int polishCount
 number of solution polishing iterations More...
 
int boundflips
 number of performed bound flips More...
 
int totalboundflips
 total number of bound flips More...
 
int enterCycles
 the number of degenerate steps during the entering algorithm More...
 
int leaveCycles
 the number of degenerate steps during the leaving algorithm More...
 
int enterDegenCand
 the number of degenerate candidates in the entering algorithm More...
 
int leaveDegenCand
 the number of degenerate candidates in the leaving algorithm More...
 
primalDegenSum
 the sum of the primal degeneracy percentage More...
 
dualDegenSum
 the sum of the dual degeneracy percentage More...
 
SPxPricer< R > * thepricer
 
SPxRatioTester< R > * theratiotester
 
SPxStarter< R > * thestarter
 
boundrange
 absolute range of all bounds in the problem More...
 
siderange
 absolute range of all side in the problem More...
 
objrange
 absolute range of all objective coefficients in the problem More...
 
- Protected Attributes inherited from LPRowSetBase< R >
DataArray< int > scaleExp
 row scaling factors (stored as bitshift) More...
 
- Protected Attributes inherited from ClassArray< Nonzero< R > >
int thesize
 number of used elements in array data More...
 
int themax
 the length of array data and More...
 
Nonzero< R > * data
 the array of elements More...
 
double memFactor
 memory extension factor. More...
 
- Protected Attributes inherited from LPColSetBase< R >
DataArray< int > scaleExp
 column scaling factors (stored as bitshift) More...
 
- Protected Attributes inherited from SPxBasisBase< R >
SPxSolverBase< R > * theLP
 the LP More...
 
DataArray< SPxIdtheBaseId
 SPxIds of basic vectors. More...
 
DataArray< const SVectorBase< R > *> matrix
 pointers to the vectors of the basis matrix. More...
 
bool matrixIsSetup
 true iff the pointers in matrix are set up correctly. More...
 
SLinSolver< R > * factor
 
bool factorized
 true iff factor = matrix \(^{-1}\). More...
 
int maxUpdates
 number of updates before refactorization. More...
 
nonzeroFactor
 allowed increase of nonzeros before refactorization. More...
 
fillFactor
 allowed increase in relative fill before refactorization More...
 
memFactor
 allowed total increase in memory consumption before refactorization More...
 
int iterCount
 number of calls to change() since last manipulation More...
 
int lastIterCount
 number of calls to change() before halting the simplex More...
 
int iterDegenCheck
 number of calls to change() since last degeneracy check More...
 
int updateCount
 number of calls to change() since last factorize() More...
 
int totalUpdateCount
 number of updates More...
 
int nzCount
 number of nonzeros in basis matrix More...
 
int lastMem
 memory needed after last fresh factorization More...
 
lastFill
 fill ratio that occured during last factorization More...
 
int lastNzCount
 number of nonzeros in basis matrix after last fresh factorization More...
 
TimertheTime
 time spent in updates More...
 
Timer::TYPE timerType
 type of timer (user or wallclock) More...
 
SPxId lastin
 lastEntered(): variable entered the base last More...
 
SPxId lastout
 lastLeft(): variable left the base last More...
 
int lastidx
 lastIndex(): basis index where last update was done More...
 
minStab
 minimum stability More...
 

Private Member Functions

Private helpers
void localAddRows (int start)
 
void localAddCols (int start)
 
void setPrimal (VectorBase< R > &p_vector)
 
void setSlacks (VectorBase< R > &p_vector)
 
void setDual (VectorBase< R > &p_vector)
 
void setRedCost (VectorBase< R > &p_vector)
 
Perturbation
void perturbMin (const UpdateVector< R > &vec, VectorBase< R > &low, VectorBase< R > &up, R eps, R delta, int start=0, int incr=1)
 
void perturbMax (const UpdateVector< R > &vec, VectorBase< R > &low, VectorBase< R > &up, R eps, R delta, int start=0, int incr=1)
 
perturbMin (const UpdateVector< R > &uvec, VectorBase< R > &low, VectorBase< R > &up, R eps, R delta, const typename SPxBasisBase< R >::Desc::Status *stat, int start, int incr)
 
perturbMax (const UpdateVector< R > &uvec, VectorBase< R > &low, VectorBase< R > &up, R eps, R delta, const typename SPxBasisBase< R >::Desc::Status *stat, int start, int incr)
 

Private Attributes

friend SPxFastRT< R >
 
friend SPxBoundFlippingRT< R >
 
Private data
Type theType
 entering or leaving algortihm. More...
 
Pricing thePricing
 full or partial pricing. More...
 
Representation theRep
 row or column representation. More...
 
SolutionPolish polishObj
 objective of solution polishing More...
 
TimertheTime
 time spent in last call to method solve() More...
 
Timer::TYPE timerType
 type of timer (user or wallclock) More...
 
Real theCumulativeTime
 cumulative time spent in all calls to method solve() More...
 
int maxIters
 maximum allowed iterations. More...
 
Real maxTime
 maximum allowed time. More...
 
int nClckSkipsLeft
 remaining number of times the clock can be safely skipped More...
 
long nCallsToTimelim
 
objLimit
 < the number of calls to the method isTimeLimitReached() More...
 
Status m_status
 status of algorithm. More...
 
m_nonbasicValue
 nonbasic part of current objective value More...
 
bool m_nonbasicValueUpToDate
 true, if the stored objValue is up to date More...
 
m_pricingViol
 maximal feasibility violation of current solution More...
 
bool m_pricingViolUpToDate
 true, if the stored violation is up to date More...
 
m_pricingViolCo
 maximal feasibility violation of current solution in coDim More...
 
bool m_pricingViolCoUpToDate
 true, if the stored violation in coDim is up to date More...
 
int m_numViol
 number of violations of current solution More...
 
m_entertol
 feasibility tolerance maintained during entering algorithm More...
 
m_leavetol
 feasibility tolerance maintained during leaving algorithm More...
 
theShift
 sum of all shifts applied to any bound. More...
 
lastShift
 for forcing feasibility. More...
 
int m_maxCycle
 maximum steps before cycling is detected. More...
 
int m_numCycle
 actual number of degenerate steps so far. More...
 
bool initialized
 true, if all vectors are setup. More...
 
SSVectorBase< R > * solveVector2
 when 2 systems are to be solved at a time; typically for speepest edge weights More...
 
SSVectorBase< R > * solveVector2rhs
 when 2 systems are to be solved at a time; typically for speepest edge weights More...
 
SSVectorBase< R > * solveVector3
 when 3 systems are to be solved at a time; typically reserved for bound flipping ratio test (basic solution will be modified!) More...
 
SSVectorBase< R > * solveVector3rhs
 when 3 systems are to be solved at a time; typically reserved for bound flipping ratio test (basic solution will be modified!) More...
 
SSVectorBase< R > * coSolveVector2
 when 2 systems are to be solved at a time; typically for speepest edge weights More...
 
SSVectorBase< R > * coSolveVector2rhs
 when 2 systems are to be solved at a time; typically for speepest edge weights More...
 
SSVectorBase< R > * coSolveVector3
 when 3 systems are to be solved at a time; typically reserved for bound flipping ratio test (basic solution will be modified!) More...
 
SSVectorBase< R > * coSolveVector3rhs
 when 3 systems are to be solved at a time; typically reserved for bound flipping ratio test (basic solution will be modified!) More...
 
bool freePricer
 true iff thepricer should be freed inside of object More...
 
bool freeRatioTester
 true iff theratiotester should be freed inside of object More...
 
bool freeStarter
 true iff thestarter should be freed inside of object More...
 
int instableLeaveNum
 
bool instableLeave
 
instableLeaveVal
 
SPxId instableEnterId
 
bool instableEnter
 
instableEnterVal
 
bool recomputedVectors
 flag to perform clean up step to reduce numerical errors only once More...
 
int displayLine
 
int displayFreq
 
sparsePricingFactor
 enable sparse pricing when viols < factor * dim() More...
 
bool getStartingDecompBasis
 flag to indicate whether the simplex is solved to get the starting improved dual simplex basis More...
 
bool computeDegeneracy
 
int degenCompIterOffset
 the number of iterations performed before the degeneracy level is computed More...
 
int decompIterationLimit
 the maximum number of iterations before the decomposition simplex is aborted. More...
 
bool fullPerturbation
 whether to perturb the entire problem or just the bounds relevant for the current pivot More...
 
int printBasisMetric
 printing the current basis metric in the log (-1: off, 0: condition estimate, 1: trace, 2: determinant, 3: condition) More...
 

The Simplex Loop

We now present a set of methods that may be usefull when implementing own SPxPricer or SPxRatioTester classes. Here is, how SPxSolverBase will call methods from its loaded SPxPricer and SPxRatioTester.

For the entering Simplex:

  1. SPxPricer::selectEnter()
  2. SPxRatioTester::selectLeave()
  3. SPxPricer::entered4()

For the leaving Simplex:

  1. SPxPricer::selectLeave()
  2. SPxRatioTester::selectEnter()
  3. SPxPricer::left4()
void setup4solve (SSVectorBase< R > *p_y, SSVectorBase< R > *p_rhs)
 Setup vectors to be solved within Simplex loop. More...
 
void setup4solve2 (SSVectorBase< R > *p_y2, SSVectorBase< R > *p_rhs2)
 Setup vectors to be solved within Simplex loop. More...
 
void setup4coSolve (SSVectorBase< R > *p_y, SSVectorBase< R > *p_rhs)
 Setup vectors to be cosolved within Simplex loop. More...
 
void setup4coSolve2 (SSVectorBase< R > *p_z, SSVectorBase< R > *p_rhs)
 Setup vectors to be cosolved within Simplex loop. More...
 
virtual R maxInfeas () const
 maximal infeasibility of basis More...
 
virtual bool noViols (R tol) const
 check for violations above tol and immediately return false w/o checking the remaining values More...
 
const SPxBasisBase< R > & basis () const
 Return current basis. More...
 
SPxBasisBase< R > & basis ()
 
const SPxPricer< R > * pricer () const
 return loaded SPxPricer. More...
 
const SLinSolver< R > * slinSolver () const
 return loaded SLinSolver. More...
 
const SPxRatioTester< R > * ratiotester () const
 return loaded SPxRatioTester. More...
 
virtual void factorize ()
 Factorize basis matrix. More...
 
bool leave (int i, bool polish=false)
 
bool enter (SPxId &id, bool polish=false)
 
coTest (int i, typename SPxBasisBase< R >::Desc::Status stat) const
 test coVector i with status stat. More...
 
void computeCoTest ()
 compute coTest vector. More...
 
void updateCoTest ()
 recompute coTest vector. More...
 
test (int i, typename SPxBasisBase< R >::Desc::Status stat) const
 test VectorBase<R> i with status stat. More...
 
void updateTest ()
 recompute test vector. More...
 
void computeFtest ()
 compute basis feasibility test vector. More...
 
void updateFtest ()
 update basis feasibility test vector. More...
 

Parallelization

In this section we present the methods, that are provided in order to allow a parallel version to be implemented as a derived class, thereby inheriting most of the code of SPxSolverBase.

Initialization
These methods are used to setup all the vectors used in the Simplex loop, that where described in the previous sectios.
bool isInitialized () const
 has the internal data been initialized? More...
 
void resetClockStats ()
 resets clock average statistics More...
 
virtual void unInit ()
 uninitialize data structures. More...
 
virtual void reinitializeVecs ()
 setup all vecs fresh More...
 
virtual void reDim ()
 reset dimensions of vectors according to loaded LP. More...
 
void computeFrhs ()
 compute feasibility vector from scratch. More...
 
virtual void computeFrhsXtra ()
 
virtual void computeFrhs1 (const VectorBase< R > &, const VectorBase< R > &)
 
void computeFrhs2 (VectorBase< R > &, VectorBase< R > &)
 
virtual void computeEnterCoPrhs ()
 compute theCoPrhs for entering Simplex. More...
 
void computeEnterCoPrhs4Row (int i, int n)
 
void computeEnterCoPrhs4Col (int i, int n)
 
virtual void computeLeaveCoPrhs ()
 compute theCoPrhs for leaving Simplex. More...
 
void computeLeaveCoPrhs4Row (int i, int n)
 
void computeLeaveCoPrhs4Col (int i, int n)
 
nonbasicValue ()
 Compute part of objective value. More...
 
virtual const SVectorBase< R > * enterVector (const SPxId &p_id)
 Get pointer to the id 'th vector. More...
 
virtual void getLeaveVals (int i, typename SPxBasisBase< R >::Desc::Status &leaveStat, SPxId &leaveId, R &leaveMax, R &leavebound, int &leaveNum, StableSum< R > &objChange)
 
virtual void getLeaveVals2 (R leaveMax, SPxId enterId, R &enterBound, R &newUBbound, R &newLBbound, R &newCoPrhs, StableSum< R > &objChange)
 
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 getEnterVals2 (int leaveIdx, R enterMax, R &leaveBound, StableSum< R > &objChange)
 
virtual void ungetEnterVal (SPxId enterId, typename SPxBasisBase< R >::Desc::Status enterStat, R leaveVal, const SVectorBase< R > &vec, StableSum< R > &objChange)
 
virtual void rejectEnter (SPxId enterId, R enterTest, typename SPxBasisBase< R >::Desc::Status enterStat)
 
virtual void rejectLeave (int leaveNum, SPxId leaveId, typename SPxBasisBase< R >::Desc::Status leaveStat, const SVectorBase< R > *newVec=0)
 
virtual void setupPupdate (void)
 
virtual void doPupdate (void)
 
virtual void clearUpdateVecs (void)
 
virtual void perturbMinEnter (void)
 
virtual void perturbMaxEnter (void)
 perturb basis bounds. More...
 
virtual void perturbMinLeave (void)
 
virtual void perturbMaxLeave (void)
 perturb nonbasic bounds. More...
 
virtual void init ()
 intialize data structures. More...
 
VarStatus basisStatusToVarStatus (typename SPxBasisBase< R >::Desc::Status stat) const
 converts basis status to VarStatus More...
 
SPxBasisBase< R >::Desc::Status varStatusToBasisStatusRow (int row, VarStatus stat) const
 converts VarStatus to basis status for rows More...
 
SPxBasisBase< R >::Desc::Status varStatusToBasisStatusCol (int col, VarStatus stat) const
 converts VarStatus to basis status for columns More...
 
virtual void setTerminationTime (Real time=infinity)
 set time limit. More...
 
virtual Real terminationTime () const
 return time limit. More...
 
virtual void setTerminationIter (int iteration=-1)
 set iteration limit. More...
 
virtual int terminationIter () const
 return iteration limit. More...
 
virtual void setTerminationValue (R value=R(infinity))
 set objective limit. More...
 
virtual R terminationValue () const
 return objective limit. More...
 
virtual R objValue ()
 get objective value of current solution. More...
 
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. More...
 
VarStatus getBasisRowStatus (int row) const
 gets basis status for a single row More...
 
VarStatus getBasisColStatus (int col) const
 gets basis status for a single column More...
 
Status getBasis (VarStatus rows[], VarStatus cols[], const int rowsSize=-1, const int colsSize=-1) const
 get current basis, and return solver status. More...
 
SPxBasisBase< R >::SPxStatus getBasisStatus () const
 gets basis status More...
 
bool isBasisValid (DataArray< VarStatus > rows, DataArray< VarStatus > cols)
 check a given basis for validity. More...
 
void setBasis (const VarStatus rows[], const VarStatus cols[])
 set the lp solver's basis. More...
 
void setBasisStatus (typename SPxBasisBase< R >::SPxStatus stat)
 set the lp solver's basis status. More...
 
void setSolverStatus (typename SPxSolverBase< R >::Status stat)
 setting the solver status external from the solve loop. More...
 
getDegeneracyLevel (VectorBase< R > degenvec)
 get level of dual degeneracy More...
 
void getNdualNorms (int &nnormsRow, int &nnormsCol) const
 get number of dual norms More...
 
bool getDualNorms (int &nnormsRow, int &nnormsCol, R *norms) const
 get dual norms More...
 
bool setDualNorms (int nnormsRow, int nnormsCol, R *norms)
 set dual norms More...
 
void setIntegralityInformation (int ncols, int *intInfo)
 pass integrality information about the variables to the solver More...
 
void resetCumulativeTime ()
 reset cumulative time counter to zero. More...
 
int boundFlips () const
 get number of bound flips. More...
 
int dualDegeneratePivots ()
 get number of dual degenerate pivots More...
 
int primalDegeneratePivots ()
 get number of primal degenerate pivots More...
 
sumDualDegeneracy ()
 get the sum of dual degeneracy More...
 
sumPrimalDegeneracy ()
 get the sum of primal degeneracy More...
 
int iterations () const
 get number of iterations of current solution. More...
 
int primalIterations ()
 return number of iterations done with primal algorithm More...
 
int dualIterations ()
 return number of iterations done with primal algorithm More...
 
int polishIterations ()
 return number of iterations done with primal algorithm More...
 
Real time () const
 time spent in last call to method solve(). More...
 
bool isTimeLimitReached (const bool forceCheck=false)
 returns whether current time limit is reached; call to time() may be skipped unless forceCheck is true More...
 
Real getMaxTime ()
 the maximum runtime More...
 
Real cumulativeTime () const
 cumulative time spent in all calls to method solve(). More...
 
int getMaxIters ()
 the maximum number of iterations More...
 
const LPRowSetBase< R > & rows () const
 return const lp's rows if available. More...
 
const LPColSetcols () const
 return const lp's cols if available. More...
 
void getLower (VectorBase< R > &p_low) const
 copy lower bound VectorBase<R> to p_low. More...
 
void getUpper (VectorBase< R > &p_up) const
 copy upper bound VectorBase<R> to p_up. More...
 
void getLhs (VectorBase< R > &p_lhs) const
 copy lhs value VectorBase<R> to p_lhs. More...
 
void getRhs (VectorBase< R > &p_rhs) const
 copy rhs value VectorBase<R> to p_rhs. More...
 
SPxLPBase< R >::SPxSense sense () const
 optimization sense. More...
 
std::string statistics () const
 returns statistical information in form of a string. More...
 
DecompStatus getDecompStatus () const
 returns whether a basis needs to be found for the improved dual simplex More...
 
void setComputeDegenFlag (bool computeDegen)
 sets whether the degeneracy is computed at each iteration More...
 
bool getComputeDegeneracy () const
 returns whether the degeneracy is computed in each iteration More...
 
void setDegenCompOffset (int iterOffset)
 sets the offset for the number of iterations before the degeneracy is computed More...
 
int getDegenCompOffset () const
 gets the offset for the number of iterations before the degeneracy is computed More...
 
void setDecompIterationLimit (int iterationLimit)
 sets the iteration limit for the decomposition simplex initialisation More...
 
int getDecompIterationLimit () const
 returns the iteration limit for the decomposition simplex initialisation More...
 

Additional Inherited Members

- Protected Types inherited from SPxBasisBase< R >
enum  SPxStatus {
  NO_PROBLEM = -2, SINGULAR = -1, REGULAR = 0, DUAL = 1,
  PRIMAL = 2, OPTIMAL = 3, UNBOUNDED = 4, INFEASIBLE = 5
}
 basis status. More...
 

Detailed Description

template<class R>
class soplex::SPxSolverBase< R >

Sequential object-oriented SimPlex.

SPxSolverBase is an LP solver class using the revised Simplex algorithm. It provides two basis representations, namely a column basis and a row basis (see Representation). For both representations, a primal and dual algorithm is available (see Type).

In addition, SPxSolverBase can be customized with various respects:

SPxSolverBase is derived from SPxLPBase<R> that is used to store the LP to be solved. Hence, the LPs solved with SPxSolverBase have the general format

\[ \begin{array}{rl} \hbox{max} & \mbox{maxObj}^T x \\ \hbox{s.t.} & \mbox{lhs} \le Ax \le \mbox{rhs} \\ & \mbox{low} \le x \le \mbox{up} \end{array} \]

Also, SPxLPBase<R> provide all manipulation methods for the LP. They allow SPxSolverBase to be used within cutting plane algorithms.

Definition at line 49 of file spxbasis.h.

Member Enumeration Documentation

◆ DecompStatus

Improved dual simplex status.

The improved dual simplex requires a starting basis to perform the problem partitioning. This flag sets the status of the improved dual simplex to indicate whether the starting basis must be found or not.

Enumerator
FINDSTARTBASIS 

Starting basis has not been found yet.

DONTFINDSTARTBASIS 

Starting basis has been found and the simplex can be executed as normal.

Definition at line 192 of file spxsolver.h.

◆ Pricing

enum Pricing

Pricing type.

In case of the ENTERing Simplex algorithm, for performance reasons it may be advisable not to compute and maintain up to date vectors pVec() and test() and instead compute only some of its elements explicitely. This is controled by the Pricing type.

Enumerator
FULL 

Full pricing.

If FULL pricing in selected for the ENTERing Simplex, vectors pVec() and test() are kept up to date by SPxSolverBase. An SPxPricer only needs to select an Id such that the test() or coTest() value is < 0.

PARTIAL 

Partial pricing.

When PARTIAL pricing in selected for the ENTERing Simplex, vectors pVec() and test() are not set up and updated by SPxSolverBase. However, vectors coPvec() and coTest() are still kept up to date by SPxSolverBase. An SPxPricer object needs to compute the values for pVec() and test() itself in order to select an appropriate pivot with test() < 0. Methods computePvec(i) and computeTest(i) will assist the used to do so. Note that it may be feasible for a pricer to return an Id with test() > 0; such will be rejected by SPxSolverBase.

Definition at line 163 of file spxsolver.h.

◆ Representation

LP basis representation.

Solving LPs with the Simplex algorithm requires the definition of a basis. A basis can be defined as a set of column vectors or a set of row vectors building a nonsingular matrix. We will refer to the first case as the columnwise representation and the latter case will be called the rowwise representation.

Type Representation determines the representation of SPxSolverBase, i.e. a columnwise (COLUMN == 1) or rowwise (ROW == -1) one.

Enumerator
ROW 

rowwise representation.

COLUMN 

columnwise representation.

Definition at line 116 of file spxsolver.h.

◆ SolutionPolish

objective for solution polishing

Enumerator
POLISH_OFF 

don't perform modifications on optimal basis

POLISH_INTEGRALITY 

maximize number of basic slack variables, i.e. more variables on bounds

POLISH_FRACTIONALITY 

minimize number of basic slack variables, i.e. more variables in between bounds

Definition at line 239 of file spxsolver.h.

◆ Status

enum Status
Todo:
In spxchange, change the status to if (m_status > 0) m_status = REGULAR;
Enumerator
ERROR 

an error occured.

NO_RATIOTESTER 

No ratiotester loaded.

NO_PRICER 

No pricer loaded.

NO_SOLVER 

No linear solver loaded.

NOT_INIT 

not initialised error

ABORT_EXDECOMP 

solve() aborted to exit decomposition simplex

ABORT_DECOMP 

solve() aborted due to commence decomposition simplex

ABORT_CYCLING 

solve() aborted due to detection of cycling.

ABORT_TIME 

solve() aborted due to time limit.

ABORT_ITER 

solve() aborted due to iteration limit.

ABORT_VALUE 

solve() aborted due to objective limit.

SINGULAR 

Basis is singular, numerical troubles?

NO_PROBLEM 

No Problem has been loaded.

REGULAR 

LP has a usable Basis (maybe LP is changed).

RUNNING 

algorithm is running

UNKNOWN 

nothing known on loaded problem.

OPTIMAL 

LP has been solved to optimality.

UNBOUNDED 

LP has been proven to be primal unbounded.

INFEASIBLE 

LP has been proven to be primal infeasible.

INForUNBD 

LP is primal infeasible or unbounded.

OPTIMAL_UNSCALED_VIOLATIONS 

LP has beed solved to optimality but unscaled solution contains violations.

Definition at line 213 of file spxsolver.h.

◆ Type

enum Type

Algorithmic type.

SPxSolverBase uses the reviesed Simplex algorithm to solve LPs. Mathematically, one distinguishes the primal from the dual algorihm. Algorithmically, these relate to the two types ENTER or LEAVE. How they relate, depends on the chosen basis representation. This is desribed by the following table:

 ENTER LEAVE
ROW DUAL PRIMAL
COLUMNPRIMALDUAL
Enumerator
ENTER 

Entering Simplex.

The Simplex loop for the entering Simplex can be sketched as follows:

  • Pricing : Select a variable to ENTER the basis.
  • Ratio-Test : Select variable to LEAVE the basis such that the basis remains feasible.
  • Perform the basis update.
LEAVE 

Leaving Simplex.

The Simplex loop for the leaving Simplex can be sketched as follows:

  • Pricing: Select a variable to LEAVE the basis.
  • Ratio-Test: Select variable to ENTER the basis such that the basis remains priced.
  • Perform the basis update.

Definition at line 135 of file spxsolver.h.

◆ VarStatus

enum VarStatus
Enumerator
ON_UPPER 

variable set to its upper bound.

ON_LOWER 

variable set to its lower bound.

FIXED 

variable fixed to identical bounds.

ZERO 

free variable fixed to zero.

BASIC 

variable is basic.

UNDEFINED 

nothing known about basis status (possibly due to a singular basis in transformed problem)

Definition at line 200 of file spxsolver.h.

Constructor & Destructor Documentation

◆ SPxSolverBase() [1/2]

SPxSolverBase ( Type  type = LEAVE,
Representation  rep = ROW,
Timer::TYPE  ttype = Timer::USER_TIME 
)
explicit

default constructor.

Constructors / destructors

◆ ~SPxSolverBase()

virtual ~SPxSolverBase ( )
virtual

◆ SPxSolverBase() [2/2]

SPxSolverBase ( const SPxSolverBase< R > &  base)

copy constructor

Member Function Documentation

◆ addedCols()

virtual void addedCols ( int  n)
protectedvirtual

Reimplemented from SPxLPBase< R >.

◆ addedRows()

virtual void addedRows ( int  n)
protectedvirtual

Reimplemented from SPxLPBase< R >.

◆ basis() [1/2]

const SPxBasisBase<R>& basis ( ) const

Return current basis.

Note
The basis can be used to solve linear systems or use any other of its (const) methods. It is, however, encuraged to use methods setup4solve() and setup4coSolve() for solving systems, since this is likely to have perfomance advantages.

Definition at line 1809 of file spxsolver.h.

◆ basis() [2/2]

SPxBasisBase<R>& basis ( )

Definition at line 1814 of file spxsolver.h.

◆ basisStatusToVarStatus()

VarStatus basisStatusToVarStatus ( typename SPxBasisBase< R >::Desc::Status  stat) const
protected

converts basis status to VarStatus

Todo:
put the following basis methods near the variable status methods!

◆ boundFlips()

int boundFlips ( ) const

get number of bound flips.

Definition at line 2137 of file spxsolver.h.

◆ calculateProblemRanges()

void calculateProblemRanges ( )
protected

determine ranges of problem values for bounds, sides and objective to assess numerical difficulties

◆ changeBounds() [1/3]

virtual void changeBounds ( const VectorBase< R > &  newLower,
const VectorBase< R > &  newUpper,
bool  scale = false 
)
virtual

Reimplemented from SPxLPBase< R >.

Referenced by SPxSolverBase< R >::changeBounds().

◆ changeBounds() [2/3]

virtual void changeBounds ( int  i,
const R &  newLower,
const R &  newUpper,
bool  scale = false 
)
virtual

Reimplemented from SPxLPBase< R >.

◆ changeBounds() [3/3]

virtual void changeBounds ( SPxColId  p_id,
const R &  p_newLower,
const R &  p_newUpper,
bool  scale = false 
)
virtual

◆ changeCol() [1/2]

virtual void changeCol ( int  i,
const LPColBase< R > &  newCol,
bool  scale = false 
)
virtual

Reimplemented from SPxLPBase< R >.

◆ changeCol() [2/2]

virtual void changeCol ( SPxColId  p_id,
const LPColBase< R > &  p_newCol,
bool  scale = false 
)
virtual

Reimplemented from SPxLPBase< R >.

Definition at line 1103 of file spxsolver.h.

◆ changeElement() [1/2]

virtual void changeElement ( int  i,
int  j,
const R &  val,
bool  scale = false 
)
virtual

Reimplemented from SPxLPBase< R >.

◆ changeElement() [2/2]

virtual void changeElement ( SPxRowId  rid,
SPxColId  cid,
const R &  val,
bool  scale = false 
)
virtual

Reimplemented from SPxLPBase< R >.

Definition at line 1111 of file spxsolver.h.

◆ changeLhs() [1/3]

virtual void changeLhs ( const VectorBase< R > &  newLhs,
bool  scale = false 
)
virtual

Reimplemented from SPxLPBase< R >.

Referenced by SPxSolverBase< R >::changeBounds().

◆ changeLhs() [2/3]

virtual void changeLhs ( int  i,
const R &  newLhs,
bool  scale = false 
)
virtual

Reimplemented from SPxLPBase< R >.

◆ changeLhs() [3/3]

virtual void changeLhs ( SPxRowId  p_id,
const R &  p_newLhs,
bool  scale = false 
)
virtual

Reimplemented from SPxLPBase< R >.

Definition at line 1064 of file spxsolver.h.

◆ changeLhsStatus()

virtual void changeLhsStatus ( int  i,
newLhs,
oldLhs = 0.0 
)
virtual

◆ changeLower() [1/3]

virtual void changeLower ( const VectorBase< R > &  newLower,
bool  scale = false 
)
virtual

Reimplemented from SPxLPBase< R >.

◆ changeLower() [2/3]

virtual void changeLower ( int  i,
const R &  newLower,
bool  scale = false 
)
virtual

Reimplemented from SPxLPBase< R >.

◆ changeLower() [3/3]

virtual void changeLower ( SPxColId  p_id,
const R &  p_newLower,
bool  scale = false 
)
virtual

Reimplemented from SPxLPBase< R >.

Definition at line 1028 of file spxsolver.h.

◆ changeLowerStatus()

virtual void changeLowerStatus ( int  i,
newLower,
oldLower = 0.0 
)
virtual

◆ changeMaxObj() [1/3]

virtual void changeMaxObj ( const VectorBase< R > &  newObj,
bool  scale = false 
)
virtual

Reimplemented from SPxLPBase< R >.

◆ changeMaxObj() [2/3]

virtual void changeMaxObj ( int  i,
const R &  newVal,
bool  scale = false 
)
virtual

Reimplemented from SPxLPBase< R >.

◆ changeMaxObj() [3/3]

virtual void changeMaxObj ( SPxColId  p_id,
const R &  p_newVal,
bool  scale = false 
)
virtual

overloading a virtual function

Reimplemented from SPxLPBase< R >.

Definition at line 1000 of file spxsolver.h.

◆ changeObj() [1/3]

virtual void changeObj ( const VectorBase< R > &  newObj,
bool  scale = false 
)
virtual

scale determines whether the new data needs to be scaled according to the existing LP (persistent scaling)

Reimplemented from SPxLPBase< R >.

◆ changeObj() [2/3]

virtual void changeObj ( int  i,
const R &  newVal,
bool  scale = false 
)
virtual

Reimplemented from SPxLPBase< R >.

◆ changeObj() [3/3]

virtual void changeObj ( SPxColId  p_id,
const R &  p_newVal,
bool  scale = false 
)
virtual

overloading a virtual function

Reimplemented from SPxLPBase< R >.

Definition at line 990 of file spxsolver.h.

◆ changeRange() [1/3]

virtual void changeRange ( const VectorBase< R > &  newLhs,
const VectorBase< R > &  newRhs,
bool  scale = false 
)
virtual

Reimplemented from SPxLPBase< R >.

◆ changeRange() [2/3]

virtual void changeRange ( int  i,
const R &  newLhs,
const R &  newRhs,
bool  scale = false 
)
virtual

Reimplemented from SPxLPBase< R >.

◆ changeRange() [3/3]

virtual void changeRange ( SPxRowId  p_id,
const R &  p_newLhs,
const R &  p_newRhs,
bool  scale = false 
)
virtual

Reimplemented from SPxLPBase< R >.

Definition at line 1087 of file spxsolver.h.

◆ changeRhs() [1/3]

virtual void changeRhs ( const VectorBase< R > &  newRhs,
bool  scale = false 
)
virtual

Reimplemented from SPxLPBase< R >.

◆ changeRhs() [2/3]

virtual void changeRhs ( int  i,
const R &  newRhs,
bool  scale = false 
)
virtual

Reimplemented from SPxLPBase< R >.

◆ changeRhs() [3/3]

virtual void changeRhs ( SPxRowId  p_id,
const R &  p_newRhs,
bool  scale = false 
)
virtual

Reimplemented from SPxLPBase< R >.

Definition at line 1076 of file spxsolver.h.

◆ changeRhsStatus()

virtual void changeRhsStatus ( int  i,
newRhs,
oldRhs = 0.0 
)
virtual

◆ changeRow() [1/2]

virtual void changeRow ( int  i,
const LPRowBase< R > &  newRow,
bool  scale = false 
)
virtual

Reimplemented from SPxLPBase< R >.

◆ changeRow() [2/2]

virtual void changeRow ( SPxRowId  p_id,
const LPRowBase< R > &  p_newRow,
bool  scale = false 
)
virtual

Reimplemented from SPxLPBase< R >.

Definition at line 1095 of file spxsolver.h.

◆ changeRowObj() [1/3]

virtual void changeRowObj ( const VectorBase< R > &  newObj,
bool  scale = false 
)
virtual

Reimplemented from SPxLPBase< R >.

◆ changeRowObj() [2/3]

virtual void changeRowObj ( int  i,
const R &  newVal,
bool  scale = false 
)
virtual

Reimplemented from SPxLPBase< R >.

◆ changeRowObj() [3/3]

virtual void changeRowObj ( SPxRowId  p_id,
const R &  p_newVal,
bool  scale = false 
)
virtual

Reimplemented from SPxLPBase< R >.

Definition at line 1010 of file spxsolver.h.

◆ changeSense()

virtual void changeSense ( typename SPxLPBase< R >::SPxSense  sns)
virtual

◆ changeUpper() [1/3]

virtual void changeUpper ( const VectorBase< R > &  newUpper,
bool  scale = false 
)
virtual

Reimplemented from SPxLPBase< R >.

◆ changeUpper() [2/3]

virtual void changeUpper ( int  i,
const R &  newUpper,
bool  scale = false 
)
virtual

Reimplemented from SPxLPBase< R >.

◆ changeUpper() [3/3]

virtual void changeUpper ( SPxColId  p_id,
const R &  p_newUpper,
bool  scale = false 
)
virtual

overloading virtual function

Reimplemented from SPxLPBase< R >.

Definition at line 1040 of file spxsolver.h.

◆ changeUpperStatus()

virtual void changeUpperStatus ( int  i,
newUpper,
oldLower = 0.0 
)
virtual

◆ clear()

virtual void clear ( )
virtual

clear all data in solver.

Reimplemented from SPxLPBase< R >.

◆ clearDualBounds()

void clearDualBounds ( typename SPxBasisBase< R >::Desc::Status  ,
R &  ,
R &   
) const
protected

The following methods serve for initializing the bounds for dual or primal Simplex algorithm of entering or leaving type.

◆ clearRowObjs()

virtual void clearRowObjs ( )
virtual

Reimplemented from SPxLPBase< R >.

Definition at line 1015 of file spxsolver.h.

◆ clearUpdateVecs()

virtual void clearUpdateVecs ( void  )
protectedvirtual

◆ coDim()

int coDim ( ) const

codimension.

Definition at line 1128 of file spxsolver.h.

◆ coId()

SPxId coId ( int  i) const

id of i 'th covector.

The i 'th coId() is the i 'th SPxColId for a rowwise and the i 'th SPxRowId for a columnwise basis represenation. Hence, 0 <= i < dim().

Definition at line 1165 of file spxsolver.h.

References SPxLPBase< R >::cId(), SPxSolverBase< R >::isId(), and SPxLPBase< R >::rId().

Referenced by SPxSolverBase< R >::id().

◆ colId()

SPxColId colId ( int  i) const

ColId of i 'th column.

Definition at line 2330 of file spxsolver.h.

◆ cols()

const LPColSet& cols ( ) const

return const lp's cols if available.

Definition at line 2226 of file spxsolver.h.

◆ computeCoTest()

void computeCoTest ( )
private

compute coTest vector.

◆ computeDualfarkas4Col()

void computeDualfarkas4Col ( direction)
protected

◆ computeDualfarkas4Row()

void computeDualfarkas4Row ( direction,
SPxId  enterId 
)
protected

◆ computeEnterCoPrhs()

virtual void computeEnterCoPrhs ( )
protectedvirtual

compute theCoPrhs for entering Simplex.

◆ computeEnterCoPrhs4Col()

void computeEnterCoPrhs4Col ( int  i,
int  n 
)
protected

◆ computeEnterCoPrhs4Row()

void computeEnterCoPrhs4Row ( int  i,
int  n 
)
protected

◆ computeFrhs()

void computeFrhs ( )
protected

compute feasibility vector from scratch.

◆ computeFrhs1()

virtual void computeFrhs1 ( const VectorBase< R > &  ,
const VectorBase< R > &   
)
protectedvirtual

◆ computeFrhs2()

void computeFrhs2 ( VectorBase< R > &  ,
VectorBase< R > &   
)
protected

◆ computeFrhsXtra()

virtual void computeFrhsXtra ( )
protectedvirtual

◆ computeFtest()

void computeFtest ( )
private

compute basis feasibility test vector.

◆ computeLeaveCoPrhs()

virtual void computeLeaveCoPrhs ( )
protectedvirtual

compute theCoPrhs for leaving Simplex.

◆ computeLeaveCoPrhs4Col()

void computeLeaveCoPrhs4Col ( int  i,
int  n 
)
protected

◆ computeLeaveCoPrhs4Row()

void computeLeaveCoPrhs4Row ( int  i,
int  n 
)
protected

◆ computePrimalray4Col()

void computePrimalray4Col ( direction,
SPxId  enterId 
)
protected

Compute the primal ray or the farkas proof in case of unboundedness or infeasibility.

◆ computePrimalray4Row()

void computePrimalray4Row ( direction)
protected

◆ computePvec() [1/2]

R computePvec ( int  i)

compute and return pVec()[i].

◆ computePvec() [2/2]

void computePvec ( )

compute entire pVec().

◆ computeTest() [1/2]

R computeTest ( int  i)

compute and return test()[i] in ENTERing Simplex.

◆ computeTest() [2/2]

void computeTest ( )

compute test VectorBase<R> in ENTERing Simplex.

◆ coPrhs()

const VectorBase<R>& coPrhs ( ) const

Right-hand side vector for coPvec.

The vector coPvec is computed by solving a linear system with the basis matrix and coPrhs as the right-hand side vector. For column basis representation, coPrhs is build up of the objective vector elements of all basic variables. For a row basis, it consists of the tight bounds of all basic constraints.

Definition at line 1459 of file spxsolver.h.

◆ coPvec()

UpdateVector<R>& coPvec ( ) const

copricing vector.

The copricing vector coPvec along with the pricing vector pVec are used for pricing in the ENTERing Simplex algorithm, i.e. one variable is selected, that violates its bounds. In contrast to this, the LEAVEing Simplex algorithm keeps both vectors within their bounds.

Definition at line 1446 of file spxsolver.h.

◆ coTest() [1/2]

const VectorBase<R>& coTest ( ) const

violations of coPvec.

In entering Simplex pricing selects checks vectors coPvec() and pVec() for violation of its bounds. coTest() contains the violations for coPvec() which are indicated by a negative value. That is, if coTest()[i] < 0, the i 'th element of coPvec() is violated by -coTest()[i].

Definition at line 1513 of file spxsolver.h.

◆ coTest() [2/2]

R coTest ( int  i,
typename SPxBasisBase< R >::Desc::Status  stat 
) const
private

test coVector i with status stat.

◆ covarStatus()

SPxBasisBase<R>::Desc::Status covarStatus ( int  i) const

Status of i 'th covariable.

Definition at line 1305 of file spxsolver.h.

◆ coVector() [1/4]

const SVectorBase<R>& coVector ( int  i) const

i 'th covector of LP.

Returns
a reference to the i 'th, 0 <= i < dim(), covector of the loaded LP (with respect to the chosen representation).

Definition at line 1249 of file spxsolver.h.

◆ coVector() [2/4]

const SVectorBase<R>& coVector ( const SPxRowId rid) const

Definition at line 1254 of file spxsolver.h.

◆ coVector() [3/4]

const SVectorBase<R>& coVector ( const SPxColId cid) const

Definition at line 1262 of file spxsolver.h.

◆ coVector() [4/4]

const SVectorBase<R>& coVector ( const SPxId p_id) const

coVector associated to p_id.

Returns
a reference to the covector of the loaded LP corresponding to p_id (with respect to the chosen representation). If p_id is a coid, a covector of the constraint matrix is returned, otherwise the corresponding unit vector is returned.

Definition at line 1276 of file spxsolver.h.

◆ cumulativeTime()

Real cumulativeTime ( ) const

cumulative time spent in all calls to method solve().

Definition at line 2208 of file spxsolver.h.

◆ delta()

R delta ( ) const

guaranteed primal and dual bound violation for optimal solution, returning the maximum of feastol() and opttol(), i.e., the less tight tolerance.

Definition at line 845 of file spxsolver.h.

◆ dim()

int dim ( ) const

dimension of basis matrix.

Definition at line 1123 of file spxsolver.h.

◆ doPupdate()

virtual void doPupdate ( void  )
protectedvirtual

◆ doRemoveCol()

virtual void doRemoveCol ( int  i)
protectedvirtual

Reimplemented from SPxLPBase< R >.

◆ doRemoveCols()

virtual void doRemoveCols ( int  perm[])
protectedvirtual

Reimplemented from SPxLPBase< R >.

◆ doRemoveRow()

virtual void doRemoveRow ( int  i)
protectedvirtual

Reimplemented from SPxLPBase< R >.

◆ doRemoveRows()

virtual void doRemoveRows ( int  perm[])
protectedvirtual

Reimplemented from SPxLPBase< R >.

◆ dualDegeneratePivots()

int dualDegeneratePivots ( )

get number of dual degenerate pivots

Definition at line 2143 of file spxsolver.h.

◆ dualIterations()

int dualIterations ( )

return number of iterations done with primal algorithm

Definition at line 2180 of file spxsolver.h.

◆ enter()

bool enter ( SPxId id,
bool  polish = false 
)
private

let id enter the basis and manage leaving of another one.

Returns
false if LP is unbounded/infeasible.

◆ entertol()

R entertol ( ) const

feasibility tolerance maintained by ratio test during ENTER algorithm.

Definition at line 815 of file spxsolver.h.

◆ enterVector()

virtual const SVectorBase<R>* enterVector ( const SPxId p_id)
protectedvirtual

Get pointer to the id 'th vector.

Definition at line 1944 of file spxsolver.h.

◆ epsilon()

R epsilon ( ) const

values \(|x| < \epsilon\) are considered to be 0.

if you want another value for epsilon, use Param::setEpsilon().

Definition at line 810 of file spxsolver.h.

◆ factorize()

virtual void factorize ( )
virtual

Factorize basis matrix.

Exceptions
SPxStatusExceptionif loaded matrix is singular

Reimplemented from SPxBasisBase< R >.

◆ feastol()

R feastol ( ) const

allowed primal feasibility tolerance.

Definition at line 829 of file spxsolver.h.

◆ forceRecompNonbasicValue()

void forceRecompNonbasicValue ( )

Definition at line 696 of file spxsolver.h.

◆ fRhs()

const VectorBase<R>& fRhs ( ) const

right-hand side vector for fVec

The feasibility vector is computed by solving a linear system with the basis matrix. The right-hand side vector of this system is referred to as feasibility, right-hand side vector fRhs().

For a row basis, fRhs() is the objective vector (ignoring shifts). For a column basis, it is the sum of all nonbasic vectors scaled by the factor of their bound.

Definition at line 1384 of file spxsolver.h.

◆ fTest()

const VectorBase<R>& fTest ( ) const

Violations of fVec.

For the leaving Simplex algorithm, pricing involves selecting a variable from fVec that violates its bounds that is to leave the basis. When a SPxPricer is called to select such a leaving variable, fTest() contains the vector of violations: For fTest()[i] < 0, the i 'th basic variable violates one of its bounds by the given value. Otherwise no bound is violated.

Definition at line 1433 of file spxsolver.h.

◆ fVec()

UpdateVector<R>& fVec ( ) const

feasibility vector.

This method return the feasibility vector. If it satisfies its bound, the basis is called feasible (independently of the chosen representation). The feasibility vector has dimension dim().

For the entering Simplex, fVec is kept within its bounds. In contrast to this, the pricing of the leaving Simplex selects an element of fVec, that violates its bounds.

Definition at line 1371 of file spxsolver.h.

◆ getBasis()

Status getBasis ( VarStatus  rows[],
VarStatus  cols[],
const int  rowsSize = -1,
const int  colsSize = -1 
) const

get current basis, and return solver status.

◆ getBasisColStatus()

VarStatus getBasisColStatus ( int  col) const

gets basis status for a single column

◆ getBasisMetric()

virtual R getBasisMetric ( int  type)
virtual

Definition at line 933 of file spxsolver.h.

◆ getBasisRowStatus()

VarStatus getBasisRowStatus ( int  row) const

gets basis status for a single row

◆ getBasisStatus()

SPxBasisBase<R>::SPxStatus getBasisStatus ( ) const

gets basis status

Definition at line 2088 of file spxsolver.h.

◆ getComputeDegeneracy()

bool getComputeDegeneracy ( ) const

returns whether the degeneracy is computed in each iteration

Definition at line 2289 of file spxsolver.h.

◆ getDecompIterationLimit()

int getDecompIterationLimit ( ) const

returns the iteration limit for the decomposition simplex initialisation

Definition at line 2315 of file spxsolver.h.

◆ getDecompStatus()

DecompStatus getDecompStatus ( ) const

returns whether a basis needs to be found for the improved dual simplex

Definition at line 2273 of file spxsolver.h.

◆ getDegenCompOffset()

int getDegenCompOffset ( ) const

gets the offset for the number of iterations before the degeneracy is computed

Definition at line 2303 of file spxsolver.h.

◆ getDegeneracyLevel()

R getDegeneracyLevel ( VectorBase< R >  degenvec)

get level of dual degeneracy

◆ getDisplayFreq()

int getDisplayFreq ( )

get display frequency

Definition at line 887 of file spxsolver.h.

◆ getDualfarkas()

virtual Status getDualfarkas ( VectorBase< R > &  vector) const
virtual

get dual farkas proof of infeasibility.

Exceptions
SPxStatusExceptionif no problem loaded

◆ getDualNorms()

bool getDualNorms ( int &  nnormsRow,
int &  nnormsCol,
R *  norms 
) const

get dual norms

◆ getDualSol()

virtual Status getDualSol ( VectorBase< R > &  vector) const
virtual

get current solution VectorBase<R> for dual variables.

This method returns the Status of the basis. If it is REGULAR or better, the VectorBase<R> of dual variables of the current basis will be copied to the argument vector. Hence, VectorBase<R> must be of dimension nRows().

Warning
Even though mathematically, each range constraint would account for two dual variables (one for each inequaility), only nRows() dual variables are setup via the following construction: Given a range constraint, there are three possible situations:
  • None of its inequalities is tight: The dual variables for both are 0. However, when shifting (see below) occurs, it may be set to a value other than 0, which models a perturbed objective vector.
  • Both of its inequalities are tight: In this case the range constraint models an equality and we adopt the standard definition.
  • One of its inequalities is tight while the other is not: In this case only the dual variable for the tight constraint is given with the standard definition, while the other constraint is implicitely set to 0.
Exceptions
SPxStatusExceptionif no problem loaded

◆ getEnterVals()

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

◆ getEnterVals2()

virtual void getEnterVals2 ( int  leaveIdx,
enterMax,
R &  leaveBound,
StableSum< R > &  objChange 
)
protectedvirtual

◆ getLeaveVals()

virtual void getLeaveVals ( int  i,
typename SPxBasisBase< R >::Desc::Status leaveStat,
SPxId leaveId,
R &  leaveMax,
R &  leavebound,
int &  leaveNum,
StableSum< R > &  objChange 
)
protectedvirtual

◆ getLeaveVals2()

virtual void getLeaveVals2 ( leaveMax,
SPxId  enterId,
R &  enterBound,
R &  newUBbound,
R &  newLBbound,
R &  newCoPrhs,
StableSum< R > &  objChange 
)
protectedvirtual

◆ getLhs()

void getLhs ( VectorBase< R > &  p_lhs) const

copy lhs value VectorBase<R> to p_lhs.

Definition at line 2243 of file spxsolver.h.

◆ getLower()

void getLower ( VectorBase< R > &  p_low) const

copy lower bound VectorBase<R> to p_low.

Definition at line 2232 of file spxsolver.h.

◆ getMaxIters()

int getMaxIters ( )

the maximum number of iterations

Definition at line 2214 of file spxsolver.h.

◆ getMaxTime()

Real getMaxTime ( )

the maximum runtime

Definition at line 2202 of file spxsolver.h.

◆ getNdualNorms()

void getNdualNorms ( int &  nnormsRow,
int &  nnormsCol 
) const

get number of dual norms

◆ getPrimalray()

virtual Status getPrimalray ( VectorBase< R > &  vector) const
virtual

get primal ray in case of unboundedness.

Exceptions
SPxStatusExceptionif no problem loaded

◆ getPrimalSol()

virtual Status getPrimalSol ( VectorBase< R > &  vector) const
virtual

get solution vector for primal variables.

This method returns the Status of the basis. If it is REGULAR or better, the primal solution vector of the current basis will be copied to the argument vector. Hence, vector must be of dimension nCols().

Exceptions
SPxStatusExceptionif not initialized

◆ getRedCostSol()

virtual Status getRedCostSol ( VectorBase< R > &  vector) const
virtual

get vector of reduced costs.

This method returns the Status of the basis. If it is REGULAR or better, the vector of reduced costs of the current basis will be copied to the argument vector. Hence, vector must be of dimension nCols().

Let d denote the vector of dual variables, as defined above, and A the LPs constraint matrix. Then the reduced cost vector r is defined as \(r^T = c^T - d^TA\).

Exceptions
SPxStatusExceptionif no problem loaded

◆ getResult()

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.

◆ getRhs()

void getRhs ( VectorBase< R > &  p_rhs) const

copy rhs value VectorBase<R> to p_rhs.

Definition at line 2249 of file spxsolver.h.

◆ getSlacks()

virtual Status getSlacks ( VectorBase< R > &  vector) const
virtual

get VectorBase<R> of slack variables.

This method returns the Status of the basis. If it is REGULAR or better, the slack variables of the current basis will be copied to the argument vector. Hence, VectorBase<R> must be of dimension nRows().

Warning
Because SPxSolverBase supports range constraints as its default, slack variables are defined in a nonstandard way: Let x be the current solution vector and A the constraint matrix. Then the vector of slack variables is defined as \(s = Ax\).
Exceptions
SPxStatusExceptionif no problem loaded

◆ getSolutionPolishing()

SolutionPolish getSolutionPolishing ( )

return objective of solution polishing

Definition at line 676 of file spxsolver.h.

◆ getTiming()

Timer::TYPE getTiming ( )

set timing type

Definition at line 870 of file spxsolver.h.

◆ getUpper()

void getUpper ( VectorBase< R > &  p_up) const

copy upper bound VectorBase<R> to p_up.

Definition at line 2237 of file spxsolver.h.

◆ hyperPricing()

void hyperPricing ( bool  h)

enable or disable hyper sparse pricing

◆ id()

SPxId id ( int  i) const

id of i 'th vector.

The i 'th Id is the i 'th SPxRowId for a rowwise and the i 'th SPxColId for a columnwise basis represenation. Hence, 0 <= i < coDim().

Definition at line 1146 of file spxsolver.h.

References SPxLPBase< R >::cId(), SPxSolverBase< R >::coId(), and SPxLPBase< R >::rId().

◆ init()

virtual void init ( )
virtual

intialize data structures.

If SPxSolverBase is not initialized, the method solve() calls init() to setup all vectors and internal data structures. Most of the other methods within this section are called by init().

Derived classes should add the initialization of additional data structures by overriding this method. Don't forget, however, to call SPxSolverBase<R>::init().

◆ initRep()

void initRep ( Representation  p_rep)

initialize ROW or COLUMN representation.

◆ invalidateBasis()

void invalidateBasis ( )

invalidates the basis, triggers refactorization

◆ isBasic() [1/5]

bool isBasic ( typename SPxBasisBase< R >::Desc::Status  stat) const

does stat describe a basic index ?

Definition at line 1311 of file spxsolver.h.

◆ isBasic() [2/5]

bool isBasic ( const SPxId p_id) const

is the p_id 'th vector basic ?

Definition at line 1317 of file spxsolver.h.

◆ isBasic() [3/5]

bool isBasic ( const SPxRowId rid) const

is the rid 'th vector basic ?

Definition at line 1326 of file spxsolver.h.

◆ isBasic() [4/5]

bool isBasic ( const SPxColId cid) const

is the cid 'th vector basic ?

Definition at line 1332 of file spxsolver.h.

◆ isBasic() [5/5]

bool isBasic ( int  i) const

is the i 'th vector basic ?

Definition at line 1350 of file spxsolver.h.

◆ isBasisValid()

bool isBasisValid ( DataArray< VarStatus rows,
DataArray< VarStatus cols 
)

check a given basis for validity.

◆ isCoBasic()

bool isCoBasic ( int  i) const

is the i 'th covector basic ?

Definition at line 1356 of file spxsolver.h.

◆ isCoId()

bool isCoId ( const SPxId p_id) const

Is p_id a CoId.

This method returns wheather or not p_id identifies a coVector with respect to the chosen representation.

Definition at line 1192 of file spxsolver.h.

◆ isColBasic()

bool isColBasic ( int  i) const

is the i 'th column vector basic ?

Definition at line 1344 of file spxsolver.h.

◆ isConsistent()

bool isConsistent ( ) const

check consistency.

Miscellaneous

◆ isId()

bool isId ( const SPxId p_id) const

Is p_id an SPxId ?

This method returns wheather or not p_id identifies a vector with respect to the chosen representation.

Definition at line 1183 of file spxsolver.h.

Referenced by SPxSolverBase< R >::coId().

◆ isInitialized()

bool isInitialized ( ) const
protected

has the internal data been initialized?

As long as an instance of SPxSolverBase is not initialized, no member contains setup data. Initialization is performed via method init(). Afterwards all data structures are kept up to date (even for all manipulation methods), until unInit() is called. However, some manipulation methods call unInit() themselfs.

Definition at line 1898 of file spxsolver.h.

◆ isRowBasic()

bool isRowBasic ( int  i) const

is the i 'th row vector basic ?

Definition at line 1338 of file spxsolver.h.

◆ isTimeLimitReached()

bool isTimeLimitReached ( const bool  forceCheck = false)

returns whether current time limit is reached; call to time() may be skipped unless forceCheck is true

◆ iterations()

int iterations ( ) const

get number of iterations of current solution.

Definition at line 2167 of file spxsolver.h.

◆ lbBound() [1/2]

const VectorBase<R>& lbBound ( ) const

lower bound for fVec.

Definition at line 1407 of file spxsolver.h.

◆ lbBound() [2/2]

VectorBase<R>& lbBound ( )

lower bound for fVec, writable.

This method returns the lower bound for the feasibility vector. It may only be called for the ENTERing Simplex.

For the ENTERing Simplex algorithms, the feasibility vector is maintained to fullfill its bounds. As fVec itself, also its bound depend on the chosen representation. Further, they may need to be shifted (see below).

Definition at line 1420 of file spxsolver.h.

◆ lcBound() [1/2]

const VectorBase<R>& lcBound ( ) const

Definition at line 1486 of file spxsolver.h.

◆ lcBound() [2/2]

VectorBase<R>& lcBound ( )

lower bound for coPvec.

This method returns the lower bound for coPvec. It may only be called for the leaving Simplex algorithm.

For the leaving Simplex algorithms coPvec is maintained to fullfill its bounds. As coPvec itself, also its bound depend on the chosen representation. Further, they may need to be shifted (see below).

Definition at line 1500 of file spxsolver.h.

◆ leave()

bool leave ( int  i,
bool  polish = false 
)
private

let index i leave the basis and manage entering of another one.

Returns
false if LP is unbounded/infeasible.

◆ leavetol()

R leavetol ( ) const

feasibility tolerance maintained by ratio test during LEAVE algorithm.

Definition at line 822 of file spxsolver.h.

◆ loadBasis()

virtual void loadBasis ( const typename SPxBasisBase< R >::Desc )
virtual

set a start basis.

◆ loadLP()

virtual void loadLP ( const SPxLPBase< R > &  LP,
bool  initSlackBasis = true 
)
virtual

copy LP.

◆ localAddCols()

void localAddCols ( int  start)
private

◆ localAddRows()

void localAddRows ( int  start)
private

◆ lpBound() [1/2]

const VectorBase<R>& lpBound ( ) const

Definition at line 1552 of file spxsolver.h.

◆ lpBound() [2/2]

VectorBase<R>& lpBound ( )

lower bound for pVec.

This method returns the lower bound for pVec. It may only be called for the leaving Simplex algorithm.

For the leaving Simplex algorithms pVec is maintained to fullfill its bounds. As pVec itself, also its bound depend on the chosen representation. Further, they may need to be shifted (see below).

Definition at line 1566 of file spxsolver.h.

◆ maxCycle()

int maxCycle ( ) const

maximum number of degenerate simplex steps before we detect cycling.

SPxSolverBase considers a Simplex step as degenerate if the steplength does not exceed epsilon(). Cycling occurs if only degenerate steps are taken. To prevent this situation, SPxSolverBase perturbs the problem such that nondegenerate steps are ensured.

maxCycle() controls how agressive such perturbation is performed, since no more than maxCycle() degenerate steps are accepted before perturbing the LP. The current number of consecutive degenerate steps is counted by numCycle().

Definition at line 917 of file spxsolver.h.

◆ maxInfeas()

virtual R maxInfeas ( ) const
virtual

maximal infeasibility of basis

This method is called before concluding optimality. Since it is possible that some stable implementation of class SPxRatioTester yielded a slightly infeasible (or unpriced) basis, this must be checked before terminating with an optimal solution.

◆ nonbasicValue()

R nonbasicValue ( )
protected

Compute part of objective value.

This method is called from value() in order to compute the part of the objective value resulting form nonbasic variables for COLUMN Representation.

◆ noViols()

virtual bool noViols ( tol) const
virtual

check for violations above tol and immediately return false w/o checking the remaining values

This method is useful for verifying whether an objective limit can be used as termination criterion

◆ numCycle()

int numCycle ( ) const

actual number of degenerate simplex steps encountered so far.

Definition at line 922 of file spxsolver.h.

◆ objValue()

virtual R objValue ( )
virtual

get objective value of current solution.

Definition at line 2051 of file spxsolver.h.

◆ operator=()

SPxSolverBase<R>& operator= ( const SPxSolverBase< R > &  base)

assignment operator

assignment operator and copy constructor

◆ opttol()

R opttol ( ) const

allowed optimality, i.e., dual feasibility tolerance.

Definition at line 837 of file spxsolver.h.

◆ performSolutionPolishing()

void performSolutionPolishing ( )

Identify primal basic variables that have zero reduced costs and try to pivot them out of the basis to make them tight. This is supposed to decrease the number of fractional variables when solving LP relaxations of (mixed) integer programs. The objective must not be modified during this procedure.

◆ perturbMax() [1/2]

void perturbMax ( const UpdateVector< R > &  vec,
VectorBase< R > &  low,
VectorBase< R > &  up,
eps,
delta,
int  start = 0,
int  incr = 1 
)
private

◆ perturbMax() [2/2]

R perturbMax ( const UpdateVector< R > &  uvec,
VectorBase< R > &  low,
VectorBase< R > &  up,
eps,
delta,
const typename SPxBasisBase< R >::Desc::Status stat,
int  start,
int  incr 
)
private

◆ perturbMaxEnter()

virtual void perturbMaxEnter ( void  )
protectedvirtual

perturb basis bounds.

◆ perturbMaxLeave()

virtual void perturbMaxLeave ( void  )
protectedvirtual

perturb nonbasic bounds.

◆ perturbMin() [1/2]

void perturbMin ( const UpdateVector< R > &  vec,
VectorBase< R > &  low,
VectorBase< R > &  up,
eps,
delta,
int  start = 0,
int  incr = 1 
)
private

◆ perturbMin() [2/2]

R perturbMin ( const UpdateVector< R > &  uvec,
VectorBase< R > &  low,
VectorBase< R > &  up,
eps,
delta,
const typename SPxBasisBase< R >::Desc::Status stat,
int  start,
int  incr 
)
private

◆ perturbMinEnter()

virtual void perturbMinEnter ( void  )
protectedvirtual

◆ perturbMinLeave()

virtual void perturbMinLeave ( void  )
protectedvirtual

◆ polishIterations()

int polishIterations ( )

return number of iterations done with primal algorithm

Definition at line 2186 of file spxsolver.h.

◆ precisionReached()

virtual bool precisionReached ( R &  newpricertol) const
protectedvirtual

is the solution precise enough, or should we increase delta() ?

◆ pricer()

const SPxPricer<R>* pricer ( ) const

return loaded SPxPricer.

Definition at line 1819 of file spxsolver.h.

◆ pricing()

Pricing pricing ( ) const

return current Pricing.

Definition at line 541 of file spxsolver.h.

◆ primalDegeneratePivots()

int primalDegeneratePivots ( )

get number of primal degenerate pivots

Definition at line 2149 of file spxsolver.h.

◆ primalIterations()

int primalIterations ( )

return number of iterations done with primal algorithm

Definition at line 2173 of file spxsolver.h.

◆ printDisplayLine()

virtual void printDisplayLine ( const bool  force = false,
const bool  forceHead = false 
)
virtual

print display line of flying table

◆ pVec()

UpdateVector<R>& pVec ( ) const

pricing vector.

The pricing vector pVec is the product of coPvec with the constraint matrix. As coPvec, also pVec is maintained within its bound for the leaving Simplex algorithm, while the bounds are tested for the entering Simplex. pVec is of dimension coDim(). Vector pVec() is only up to date for LEAVEing Simplex or FULL pricing in ENTERing Simplex.

Definition at line 1526 of file spxsolver.h.

◆ qualBoundViolation()

virtual void qualBoundViolation ( R &  maxviol,
R &  sumviol 
) const
virtual

get violations of bounds.

◆ qualConstraintViolation()

virtual void qualConstraintViolation ( R &  maxviol,
R &  sumviol 
) const
virtual

get violation of constraints.

◆ qualRedCostViolation()

virtual void qualRedCostViolation ( R &  maxviol,
R &  sumviol 
) const
virtual

get violation of optimality criterion.

◆ qualSlackViolation()

virtual void qualSlackViolation ( R &  maxviol,
R &  sumviol 
) const
virtual

get the residuum |Ax-b|.

◆ ratiotester()

const SPxRatioTester<R>* ratiotester ( ) const

return loaded SPxRatioTester.

Definition at line 1829 of file spxsolver.h.

◆ read()

virtual bool read ( std::istream &  in,
NameSet rowNames = 0,
NameSet colNames = 0,
DIdxSet intVars = 0 
)
virtual

read LP from input stream.

Reimplemented from SPxLPBase< R >.

◆ readBasisFile()

virtual bool readBasisFile ( const char *  filename,
const NameSet rowNames,
const NameSet colNames 
)
virtual

Load basis from filename in MPS format. If rowNames and colNames are NULL, default names are used for the constraints and variables.

◆ reDim()

virtual void reDim ( )
protectedvirtual

reset dimensions of vectors according to loaded LP.

◆ reinitializeVecs()

virtual void reinitializeVecs ( )
protectedvirtual

setup all vecs fresh

◆ rejectEnter()

virtual void rejectEnter ( SPxId  enterId,
enterTest,
typename SPxBasisBase< R >::Desc::Status  enterStat 
)
protectedvirtual

◆ rejectLeave()

virtual void rejectLeave ( int  leaveNum,
SPxId  leaveId,
typename SPxBasisBase< R >::Desc::Status  leaveStat,
const SVectorBase< R > *  newVec = 0 
)
protectedvirtual

◆ reLoad()

virtual void reLoad ( )
virtual

reload LP.

◆ rep()

Representation rep ( ) const

return the current basis representation.

Definition at line 529 of file spxsolver.h.

◆ resetClockStats()

void resetClockStats ( )
protected

resets clock average statistics

◆ resetCumulativeTime()

void resetCumulativeTime ( )

reset cumulative time counter to zero.

Definition at line 2131 of file spxsolver.h.

◆ rowId()

SPxRowId rowId ( int  i) const

RowId of i 'th inequality.

Mapping between numbers and Ids

Definition at line 2325 of file spxsolver.h.

◆ rows()

const LPRowSetBase<R>& rows ( ) const

return const lp's rows if available.

Definition at line 2220 of file spxsolver.h.

◆ sense()

SPxLPBase<R>::SPxSense sense ( ) const

optimization sense.

Definition at line 2255 of file spxsolver.h.

◆ setBasis()

void setBasis ( const VarStatus  rows[],
const VarStatus  cols[] 
)

set the lp solver's basis.

◆ setBasisSolver()

virtual void setBasisSolver ( SLinSolver< R > *  slu,
const bool  destroy = false 
)
virtual

setup linear solver to use. If destroy is true, slusolver will be freed in destructor.

◆ setBasisStatus()

void setBasisStatus ( typename SPxBasisBase< R >::SPxStatus  stat)

set the lp solver's basis status.

Definition at line 2100 of file spxsolver.h.

◆ setComputeDegenFlag()

void setComputeDegenFlag ( bool  computeDegen)

sets whether the degeneracy is computed at each iteration

Definition at line 2282 of file spxsolver.h.

◆ setDecompIterationLimit()

void setDecompIterationLimit ( int  iterationLimit)

sets the iteration limit for the decomposition simplex initialisation

Definition at line 2309 of file spxsolver.h.

◆ setDecompStatus()

void setDecompStatus ( DecompStatus  decomp_stat)

turn on or off the improved dual simplex.

◆ setDegenCompOffset()

void setDegenCompOffset ( int  iterOffset)

sets the offset for the number of iterations before the degeneracy is computed

Definition at line 2296 of file spxsolver.h.

◆ setDelta()

void setDelta ( d)

set parameter delta, i.e., set feastol and opttol to same value.

◆ setDisplayFreq()

void setDisplayFreq ( int  freq)

set display frequency

Definition at line 881 of file spxsolver.h.

◆ setDual()

void setDual ( VectorBase< R > &  p_vector)
private

◆ setDualColBounds()

void setDualColBounds ( )
protected

◆ setDualNorms()

bool setDualNorms ( int  nnormsRow,
int  nnormsCol,
R *  norms 
)

set dual norms

◆ setDualRowBounds()

void setDualRowBounds ( )
protected

◆ setEnterBound4Col()

void setEnterBound4Col ( int  ,
int   
)
protected

◆ setEnterBound4Row()

void setEnterBound4Row ( int  ,
int   
)
protected

◆ setEnterBounds()

virtual void setEnterBounds ( )
protectedvirtual

◆ setFeastol()

void setFeastol ( d)

set parameter feastol.

◆ setFillFactor()

void setFillFactor ( f)

set refactor threshold for fill-in in current factor update compared to fill-in in last factorization

Definition at line 505 of file spxsolver.h.

◆ setIntegralityInformation()

void setIntegralityInformation ( int  ncols,
int *  intInfo 
)

pass integrality information about the variables to the solver

◆ setLeaveBound4Col()

void setLeaveBound4Col ( int  i,
int  n 
)
protected

◆ setLeaveBound4Row()

void setLeaveBound4Row ( int  i,
int  n 
)
protected

◆ setLeaveBounds()

virtual void setLeaveBounds ( )
protectedvirtual

◆ setMemFactor()

void setMemFactor ( f)

set refactor threshold for memory growth in current factor update compared to the last factorization

Definition at line 511 of file spxsolver.h.

◆ setMetricInformation()

void setMetricInformation ( int  type)

print basis metric within the usual output

Definition at line 893 of file spxsolver.h.

◆ setNonzeroFactor()

void setNonzeroFactor ( f)

set refactor threshold for nonzeros in last factorized basis matrix compared to updated basis matrix

Definition at line 499 of file spxsolver.h.

◆ setOpttol()

void setOpttol ( d)

set parameter opttol.

◆ setOutstream()

void setOutstream ( SPxOut newOutstream)

Definition at line 492 of file spxsolver.h.

◆ setPricer()

virtual void setPricer ( SPxPricer< R > *  pricer,
const bool  destroy = false 
)
virtual

setup pricer to use. If destroy is true, pricer will be freed in destructor.

◆ setPricing()

void setPricing ( Pricing  pr)

set FULL or PARTIAL pricing.

◆ setPrimal()

void setPrimal ( VectorBase< R > &  p_vector)
private

◆ setPrimalBounds()

void setPrimalBounds ( )
protected

setup feasibility bounds for entering algorithm

◆ setRedCost()

void setRedCost ( VectorBase< R > &  p_vector)
private

◆ setRep()

void setRep ( Representation  p_rep)

switch to ROW or COLUMN representation if not already used.

◆ setSlacks()

void setSlacks ( VectorBase< R > &  p_vector)
private

◆ setSolutionPolishing()

void setSolutionPolishing ( SolutionPolish  _polishObj)

set objective of solution polishing (0: off, 1: max_basic_slack, 2: min_basic_slack)

Definition at line 670 of file spxsolver.h.

◆ setSolverStatus()

void setSolverStatus ( typename SPxSolverBase< R >::Status  stat)

setting the solver status external from the solve loop.

Definition at line 2109 of file spxsolver.h.

◆ setSparsePricingFactor()

void setSparsePricingFactor ( fac)

Definition at line 899 of file spxsolver.h.

◆ setStarter()

virtual void setStarter ( SPxStarter< R > *  starter,
const bool  destroy = false 
)
virtual

setup starting basis generator to use. If destroy is true, starter will be freed in destructor.

◆ setTerminationIter()

virtual void setTerminationIter ( int  iteration = -1)
virtual

set iteration limit.

◆ setTerminationTime()

virtual void setTerminationTime ( Real  time = infinity)
virtual

set time limit.

Limits and status inquiry

◆ setTerminationValue()

virtual void setTerminationValue ( value = R(infinity))
virtual

set objective limit.

◆ setTester()

virtual void setTester ( SPxRatioTester< R > *  tester,
const bool  destroy = false 
)
virtual

setup ratio-tester to use. If destroy is true, tester will be freed in destructor.

◆ setTiming()

void setTiming ( Timer::TYPE  ttype)

set timing type

Definition at line 859 of file spxsolver.h.

◆ setType()

void setType ( Type  tp)

set LEAVE or ENTER algorithm.

◆ setup4coSolve()

void setup4coSolve ( SSVectorBase< R > *  p_y,
SSVectorBase< R > *  p_rhs 
)

Setup vectors to be cosolved within Simplex loop.

Load vector y to be coSolved with the basis matrix during the ENTER Simplex. The system will be solved after SPxSolverBase's call to SPxRatioTester. The system will be solved along with another system. Solving two linear system at a time has performance advantages over solving the two linear systems seperately.

Definition at line 1770 of file spxsolver.h.

◆ setup4coSolve2()

void setup4coSolve2 ( SSVectorBase< R > *  p_z,
SSVectorBase< R > *  p_rhs 
)

Setup vectors to be cosolved within Simplex loop.

Load a second vector z to be coSolved with the basis matrix during the ENTER Simplex. The system will be solved after SPxSolverBase's call to SPxRatioTester. The system will be solved along with two other systems.

Definition at line 1782 of file spxsolver.h.

◆ setup4solve()

void setup4solve ( SSVectorBase< R > *  p_y,
SSVectorBase< R > *  p_rhs 
)

Setup vectors to be solved within Simplex loop.

Load vector y to be solved with the basis matrix during the LEAVE Simplex. The system will be solved after SPxSolverBase's call to SPxRatioTester. The system will be solved along with another system. Solving two linear system at a time has performance advantages over solving the two linear systems seperately.

Definition at line 1742 of file spxsolver.h.

◆ setup4solve2()

void setup4solve2 ( SSVectorBase< R > *  p_y2,
SSVectorBase< R > *  p_rhs2 
)

Setup vectors to be solved within Simplex loop.

Load a second additional vector y2 to be solved with the basis matrix during the LEAVE Simplex. The system will be solved after SPxSolverBase's call to SPxRatioTester. The system will be solved along with at least one other system. Solving several linear system at a time has performance advantages over solving them seperately.

Definition at line 1756 of file spxsolver.h.

◆ setupPupdate()

virtual void setupPupdate ( void  )
protectedvirtual

◆ shift()

virtual R shift ( ) const
virtual

total current shift amount.

Definition at line 1675 of file spxsolver.h.

◆ shiftFvec()

void shiftFvec ( )

Perform initial shifting to optain an feasible or pricable basis.

◆ shiftLBbound()

void shiftLBbound ( int  i,
to 
)

shift i 'th lbBound to to.

Definition at line 1632 of file spxsolver.h.

◆ shiftLCbound()

void shiftLCbound ( int  i,
to 
)

shift i 'th lcBound to to.

Definition at line 1664 of file spxsolver.h.

◆ shiftLPbound()

void shiftLPbound ( int  i,
to 
)

shift i 'th lpBound to to.

Definition at line 1648 of file spxsolver.h.

◆ shiftPvec()

void shiftPvec ( )

Perform initial shifting to optain an feasible or pricable basis.

◆ shiftUBbound()

void shiftUBbound ( int  i,
to 
)

shift i 'th ubBound to to.

Definition at line 1624 of file spxsolver.h.

◆ shiftUCbound()

void shiftUCbound ( int  i,
to 
)

shift i 'th ucBound to to.

Definition at line 1656 of file spxsolver.h.

◆ shiftUPbound()

void shiftUPbound ( int  i,
to 
)

shift i 'th upBound to to.

Definition at line 1640 of file spxsolver.h.

◆ slinSolver()

const SLinSolver<R>* slinSolver ( ) const

return loaded SLinSolver.

Definition at line 1824 of file spxsolver.h.

◆ solve()

virtual Status solve ( volatile bool *  interrupt = NULL)
virtual

solve loaded LP.

Solves the loaded LP by processing the Simplex iteration until the termination criteria is fullfilled (see terminate()). The SPxStatus of the solver will indicate the reason for termination.

Exceptions
SPxStatusExceptionif either no problem, solver, pricer or ratiotester loaded or if solve is still running when it shouldn't be

◆ starter()

SPxStarter<R>* starter ( ) const

return current starter.

Definition at line 547 of file spxsolver.h.

◆ statistics()

std::string statistics ( ) const

returns statistical information in form of a string.

Definition at line 2261 of file spxsolver.h.

◆ status()

Status status ( ) const

Status of solution process.

◆ subversion()

int subversion ( ) const

return the internal subversion of SPxSolverBase as number

Definition at line 524 of file spxsolver.h.

◆ sumDualDegeneracy()

R sumDualDegeneracy ( )

get the sum of dual degeneracy

Definition at line 2155 of file spxsolver.h.

◆ sumPrimalDegeneracy()

R sumPrimalDegeneracy ( )

get the sum of primal degeneracy

Definition at line 2161 of file spxsolver.h.

◆ terminate()

virtual bool terminate ( )
virtual

Termination criterion.

This method is called in each Simplex iteration to determine, if the algorithm is to terminate. In this case a nonzero value is returned.

This method is declared virtual to allow for implementation of other stopping criteria or using it as callback method within the Simplex loop, by overriding the method in a derived class. However, all implementations must terminate with the statement return SPxSolverBase<R>::terminate(), if no own termination criteria is encountered.

Note, that the Simplex loop stopped even when terminate() returns 0, if the LP has been solved to optimality (i.e. no further pricing succeeds and no shift is present).

◆ terminationIter()

virtual int terminationIter ( ) const
virtual

return iteration limit.

◆ terminationTime()

virtual Real terminationTime ( ) const
virtual

return time limit.

◆ terminationValue()

virtual R terminationValue ( ) const
virtual

return objective limit.

◆ test() [1/2]

const VectorBase<R>& test ( ) const

Violations of pVec.

In entering Simplex pricing selects checks vectors coPvec() and pVec() for violation of its bounds. Vector test() contains the violations for pVec(), i.e., if test()[i] < 0, the i'th element of pVec() is violated by test()[i]. Vector test() is only up to date for FULL pricing.

Definition at line 1579 of file spxsolver.h.

◆ test() [2/2]

R test ( int  i,
typename SPxBasisBase< R >::Desc::Status  stat 
) const
private

test VectorBase<R> i with status stat.

◆ testBounds()

void testBounds ( ) const

◆ testVecs()

void testVecs ( )

◆ time()

Real time ( ) const

time spent in last call to method solve().

Definition at line 2192 of file spxsolver.h.

◆ type()

Type type ( ) const

return current Type.

Definition at line 535 of file spxsolver.h.

◆ ubBound() [1/2]

const VectorBase<R>& ubBound ( ) const

upper bound for fVec.

Definition at line 1389 of file spxsolver.h.

◆ ubBound() [2/2]

VectorBase<R>& ubBound ( )

upper bound for fVec, writable.

This method returns the upper bound for the feasibility vector. It may only be called for the ENTERing Simplex.

For the ENTERing Simplex algorithms, the feasibility vector is maintained to fullfill its bounds. As fVec itself, also its bounds depend on the chosen representation. Further, they may need to be shifted (see below).

Definition at line 1402 of file spxsolver.h.

◆ ucBound() [1/2]

const VectorBase<R>& ucBound ( ) const

Definition at line 1465 of file spxsolver.h.

◆ ucBound() [2/2]

VectorBase<R>& ucBound ( )

upper bound for coPvec.

This method returns the upper bound for coPvec. It may only be called for the leaving Simplex algorithm.

For the leaving Simplex algorithms coPvec is maintained to fullfill its bounds. As coPvec itself, also its bound depend on the chosen representation. Further, they may need to be shifted (see below).

Definition at line 1479 of file spxsolver.h.

◆ ungetEnterVal()

virtual void ungetEnterVal ( SPxId  enterId,
typename SPxBasisBase< R >::Desc::Status  enterStat,
leaveVal,
const SVectorBase< R > &  vec,
StableSum< R > &  objChange 
)
protectedvirtual

◆ unInit()

virtual void unInit ( )
protectedvirtual

uninitialize data structures.

Definition at line 1907 of file spxsolver.h.

◆ unitVector()

const SVectorBase<R>& unitVector ( int  i) const

return i 'th unit vector.

Definition at line 1284 of file spxsolver.h.

◆ unscaleLPandReloadBasis()

void unscaleLPandReloadBasis ( )

unscales the LP and reloads the basis

◆ unShift()

virtual void unShift ( void  )
virtual

remove shift as much as possible.

◆ upBound() [1/2]

const VectorBase<R>& upBound ( ) const

Definition at line 1531 of file spxsolver.h.

◆ upBound() [2/2]

VectorBase<R>& upBound ( )

upper bound for pVec.

This method returns the upper bound for pVec. It may only be called for the leaving Simplex algorithm.

For the leaving Simplex algorithms pVec is maintained to fullfill its bounds. As pVec itself, also its bound depend on the chosen representation. Further, they may need to be shifted (see below).

Definition at line 1545 of file spxsolver.h.

◆ updateCoTest()

void updateCoTest ( )
private

recompute coTest vector.

◆ updateFtest()

void updateFtest ( )
private

update basis feasibility test vector.

◆ updateNonbasicValue()

bool updateNonbasicValue ( objChange)
Returns
whether nonbasic part of objective is reliable

◆ updateTest()

void updateTest ( )
private

recompute test vector.

◆ useFullPerturbation()

void useFullPerturbation ( bool  full)

perturb entire problem or only the bounds relevant to the current pivot

Definition at line 928 of file spxsolver.h.

◆ value()

virtual R value ( )
virtual

current objective value.

Returns
Objective value of the current solution vector (see getPrimalSol()).

◆ varStatus()

SPxBasisBase<R>::Desc::Status varStatus ( int  i) const

Status of i 'th variable.

Definition at line 1299 of file spxsolver.h.

◆ varStatusToBasisStatusCol()

SPxBasisBase<R>::Desc::Status varStatusToBasisStatusCol ( int  col,
VarStatus  stat 
) const
protected

converts VarStatus to basis status for columns

◆ varStatusToBasisStatusRow()

SPxBasisBase<R>::Desc::Status varStatusToBasisStatusRow ( int  row,
VarStatus  stat 
) const
protected

converts VarStatus to basis status for rows

◆ vector() [1/4]

const SVectorBase<R>& vector ( int  i) const

i 'th vector.

Returns
a reference to the i 'th, 0 <= i < coDim(), vector of the loaded LP (with respect to the chosen representation).

Definition at line 1205 of file spxsolver.h.

◆ vector() [2/4]

const SVectorBase<R>& vector ( const SPxRowId rid) const

Definition at line 1211 of file spxsolver.h.

◆ vector() [3/4]

const SVectorBase<R>& vector ( const SPxColId cid) const

Definition at line 1219 of file spxsolver.h.

◆ vector() [4/4]

const SVectorBase<R>& vector ( const SPxId p_id) const

VectorBase<R> associated to p_id.

Returns
Returns a reference to the VectorBase<R> of the loaded LP corresponding to id (with respect to the chosen representation). If p_id is an id, a vector of the constraint matrix is returned, otherwise the corresponding unit vector (of the slack variable or bound inequality) is returned.
Todo:
The implementation does not exactly look like it will do what is promised in the describtion.

Definition at line 1236 of file spxsolver.h.

◆ version()

int version ( ) const

return the version of SPxSolverBase as number like 123 for 1.2.3

Definition at line 519 of file spxsolver.h.

◆ writeBasisFile()

virtual bool writeBasisFile ( const char *  filename,
const NameSet rowNames,
const NameSet colNames,
const bool  cpxFormat = false 
) const
virtual

Write basis to filename in MPS format. If rowNames and colNames are NULL, default names are used for the constraints and variables.

◆ writeState()

virtual bool writeState ( const char *  filename,
const NameSet rowNames = NULL,
const NameSet colNames = NULL,
const bool  cpxFormat = false 
) const
virtual

Write current LP, basis, and parameter settings. LP is written in MPS format to "\p filename".mps, basis is written in "\p filename".bas, and parameters are written to "\p filename".set. If rowNames and colNames are NULL, default names are used for the constraints and variables.

Member Data Documentation

◆ addVec

UpdateVector<R> addVec
protected

storage for thePvec = &addVec

Definition at line 357 of file spxsolver.h.

◆ boundflips

int boundflips
protected

number of performed bound flips

Definition at line 405 of file spxsolver.h.

◆ boundrange

R boundrange
protected

absolute range of all bounds in the problem

Definition at line 419 of file spxsolver.h.

◆ computeDegeneracy

bool computeDegeneracy
private

Definition at line 331 of file spxsolver.h.

◆ coSolveVector2

SSVectorBase<R>* coSolveVector2
private

when 2 systems are to be solved at a time; typically for speepest edge weights

Definition at line 296 of file spxsolver.h.

◆ coSolveVector2rhs

SSVectorBase<R>* coSolveVector2rhs
private

when 2 systems are to be solved at a time; typically for speepest edge weights

Definition at line 298 of file spxsolver.h.

◆ coSolveVector3

SSVectorBase<R>* coSolveVector3
private

when 3 systems are to be solved at a time; typically reserved for bound flipping ratio test (basic solution will be modified!)

Definition at line 300 of file spxsolver.h.

◆ coSolveVector3rhs

SSVectorBase<R>* coSolveVector3rhs
private

when 3 systems are to be solved at a time; typically reserved for bound flipping ratio test (basic solution will be modified!)

Definition at line 302 of file spxsolver.h.

◆ coWeights

VectorBase<R> coWeights

store dual norms

Definition at line 473 of file spxsolver.h.

◆ decompIterationLimit

int decompIterationLimit
private

the maximum number of iterations before the decomposition simplex is aborted.

Definition at line 335 of file spxsolver.h.

◆ degenCompIterOffset

int degenCompIterOffset
private

the number of iterations performed before the degeneracy level is computed

Definition at line 333 of file spxsolver.h.

◆ displayFreq

int displayFreq
private

Definition at line 326 of file spxsolver.h.

◆ displayLine

int displayLine
private

Definition at line 325 of file spxsolver.h.

◆ dualDegenSum

R dualDegenSum
protected

the sum of the dual degeneracy percentage

Definition at line 413 of file spxsolver.h.

◆ dualFarkas

DSVectorBase<R> dualFarkas
protected

stores dual farkas proof in case of infeasibility

Definition at line 398 of file spxsolver.h.

◆ dualRhs

VectorBase<R> dualRhs
protected

rhs VectorBase<R> for computing the dual vector

Definition at line 355 of file spxsolver.h.

◆ dualVec

UpdateVector<R> dualVec
protected

dual vector

Definition at line 356 of file spxsolver.h.

◆ enterCount

int enterCount
protected

number of ENTER iterations

Definition at line 401 of file spxsolver.h.

◆ enterCycles

int enterCycles
protected

the number of degenerate steps during the entering algorithm

Definition at line 408 of file spxsolver.h.

◆ enterDegenCand

int enterDegenCand
protected

the number of degenerate candidates in the entering algorithm

Definition at line 410 of file spxsolver.h.

◆ freePricer

bool freePricer
private

true iff thepricer should be freed inside of object

Definition at line 304 of file spxsolver.h.

◆ freeRatioTester

bool freeRatioTester
private

true iff theratiotester should be freed inside of object

Definition at line 305 of file spxsolver.h.

◆ freeStarter

bool freeStarter
private

true iff thestarter should be freed inside of object

Definition at line 306 of file spxsolver.h.

◆ fullPerturbation

bool fullPerturbation
private

whether to perturb the entire problem or just the bounds relevant for the current pivot

Definition at line 338 of file spxsolver.h.

◆ getStartingDecompBasis

bool getStartingDecompBasis
private

flag to indicate whether the simplex is solved to get the starting improved dual simplex basis

Definition at line 330 of file spxsolver.h.

◆ hyperPricingEnter

bool hyperPricingEnter

true if hyper sparse pricing is turned on in the entering Simplex

Definition at line 465 of file spxsolver.h.

◆ hyperPricingLeave

bool hyperPricingLeave

true if hyper sparse pricing is turned on in the leaving Simplex

Definition at line 464 of file spxsolver.h.

◆ infeasibilities

DIdxSet infeasibilities

For the leaving Simplex algorithm this vector contains the indices of infeasible basic variables; for the entering Simplex algorithm this vector contains the indices of infeasible slack variables.

Definition at line 442 of file spxsolver.h.

◆ infeasibilitiesCo

DIdxSet infeasibilitiesCo

For the entering Simplex algorithm these vectors contains the indices of infeasible basic variables.

Definition at line 445 of file spxsolver.h.

◆ initialized

bool initialized
private

true, if all vectors are setup.

Definition at line 285 of file spxsolver.h.

◆ instableEnter

bool instableEnter
private

Definition at line 319 of file spxsolver.h.

◆ instableEnterId

SPxId instableEnterId
private

Definition at line 318 of file spxsolver.h.

◆ instableEnterVal

R instableEnterVal
private

Definition at line 320 of file spxsolver.h.

◆ instableLeave

bool instableLeave
private

Definition at line 312 of file spxsolver.h.

◆ instableLeaveNum

int instableLeaveNum
private

Definition at line 311 of file spxsolver.h.

◆ instableLeaveVal

R instableLeaveVal
private

Definition at line 313 of file spxsolver.h.

◆ integerVariables

DataArray<int> integerVariables

supplementary variable information, 0: continous variable, 1: integer variable

Definition at line 489 of file spxsolver.h.

◆ isInfeasible

DataArray<int> isInfeasible

0: index not violated, 1: index violated, 2: index violated and among candidate list

Binary vectors to store whether basic indices are infeasible the i-th entry equals false, if the i-th basic variable is not infeasible the i-th entry equals true, if the i-th basic variable is infeasible

Definition at line 456 of file spxsolver.h.

◆ isInfeasibleCo

DataArray<int> isInfeasibleCo

0: index not violated, 1: index violated, 2: index violated and among candidate list

Definition at line 458 of file spxsolver.h.

◆ lastShift

R lastShift
private

for forcing feasibility.

Definition at line 282 of file spxsolver.h.

◆ leaveCount

int leaveCount
protected

number of LEAVE iterations

Definition at line 400 of file spxsolver.h.

◆ leaveCycles

int leaveCycles
protected

the number of degenerate steps during the leaving algorithm

Definition at line 409 of file spxsolver.h.

◆ leaveDegenCand

int leaveDegenCand
protected

the number of degenerate candidates in the leaving algorithm

Definition at line 411 of file spxsolver.h.

◆ m_entertol

R m_entertol
private

feasibility tolerance maintained during entering algorithm

Definition at line 279 of file spxsolver.h.

◆ m_leavetol

R m_leavetol
private

feasibility tolerance maintained during leaving algorithm

Definition at line 280 of file spxsolver.h.

◆ m_maxCycle

int m_maxCycle
private

maximum steps before cycling is detected.

Definition at line 283 of file spxsolver.h.

◆ m_nonbasicValue

R m_nonbasicValue
private

nonbasic part of current objective value

Definition at line 268 of file spxsolver.h.

◆ m_nonbasicValueUpToDate

bool m_nonbasicValueUpToDate
private

true, if the stored objValue is up to date

Definition at line 269 of file spxsolver.h.

◆ m_numCycle

int m_numCycle
private

actual number of degenerate steps so far.

Definition at line 284 of file spxsolver.h.

◆ m_numViol

int m_numViol
private

number of violations of current solution

Definition at line 277 of file spxsolver.h.

◆ m_pricingViol

R m_pricingViol
private

maximal feasibility violation of current solution

Definition at line 271 of file spxsolver.h.

◆ m_pricingViolCo

R m_pricingViolCo
private

maximal feasibility violation of current solution in coDim

Definition at line 275 of file spxsolver.h.

◆ m_pricingViolCoUpToDate

bool m_pricingViolCoUpToDate
private

true, if the stored violation in coDim is up to date

Definition at line 276 of file spxsolver.h.

◆ m_pricingViolUpToDate

bool m_pricingViolUpToDate
private

true, if the stored violation is up to date

Definition at line 272 of file spxsolver.h.

◆ m_status

Status m_status
private

status of algorithm.

Definition at line 266 of file spxsolver.h.

◆ maxIters

int maxIters
private

maximum allowed iterations.

Definition at line 261 of file spxsolver.h.

◆ maxTime

Real maxTime
private

maximum allowed time.

Definition at line 262 of file spxsolver.h.

◆ multColwiseCalls

int multColwiseCalls

number of products, columnwise multiplication

Definition at line 483 of file spxsolver.h.

◆ multFullCalls

int multFullCalls

number of products ignoring sparsity

Definition at line 482 of file spxsolver.h.

◆ multSparseCalls

int multSparseCalls

number of products exploiting sparsity

Definition at line 481 of file spxsolver.h.

◆ multTimeColwise

Timer* multTimeColwise

time spent in setupPupdate(), columnwise multiplication

Definition at line 479 of file spxsolver.h.

◆ multTimeFull

Timer* multTimeFull

time spent in setupPupdate() ignoring sparsity

Definition at line 478 of file spxsolver.h.

◆ multTimeSparse

Timer* multTimeSparse

time spent in setupPupdate() exploiting sparsity

Definition at line 477 of file spxsolver.h.

◆ multTimeUnsetup

Timer* multTimeUnsetup

time spent in setupPupdate() w/o sparsity information

Definition at line 480 of file spxsolver.h.

◆ multUnsetupCalls

int multUnsetupCalls

number of products w/o sparsity information

Definition at line 484 of file spxsolver.h.

◆ nCallsToTimelim

long nCallsToTimelim
private

Definition at line 264 of file spxsolver.h.

◆ nClckSkipsLeft

int nClckSkipsLeft
private

remaining number of times the clock can be safely skipped

Definition at line 263 of file spxsolver.h.

◆ objLimit

R objLimit
private

< the number of calls to the method isTimeLimitReached()

objective value limit.

Definition at line 265 of file spxsolver.h.

◆ objrange

R objrange
protected

absolute range of all objective coefficients in the problem

Definition at line 421 of file spxsolver.h.

◆ polishCount

int polishCount
protected

number of solution polishing iterations

Definition at line 403 of file spxsolver.h.

◆ polishObj

SolutionPolish polishObj
private

objective of solution polishing

Definition at line 257 of file spxsolver.h.

◆ primalCount

int primalCount
protected

number of primal iterations

Definition at line 402 of file spxsolver.h.

◆ primalDegenSum

R primalDegenSum
protected

the sum of the primal degeneracy percentage

Definition at line 412 of file spxsolver.h.

◆ primalRay

DSVectorBase<R> primalRay
protected

stores primal ray in case of unboundedness

Definition at line 397 of file spxsolver.h.

◆ primRhs

VectorBase<R> primRhs
protected

rhs VectorBase<R> for computing the primal vector

Definition at line 353 of file spxsolver.h.

◆ primVec

UpdateVector<R> primVec
protected

primal vector

Definition at line 354 of file spxsolver.h.

◆ printBasisMetric

int printBasisMetric
private

printing the current basis metric in the log (-1: off, 0: condition estimate, 1: trace, 2: determinant, 3: condition)

Definition at line 340 of file spxsolver.h.

◆ random

Random random

The random number generator used throughout the whole computation. Its seed can be modified.

Definition at line 437 of file spxsolver.h.

◆ recomputedVectors

bool recomputedVectors
private

flag to perform clean up step to reduce numerical errors only once

Definition at line 323 of file spxsolver.h.

◆ remainingRoundsEnter

int remainingRoundsEnter

Definition at line 468 of file spxsolver.h.

◆ remainingRoundsEnterCo

int remainingRoundsEnterCo

Definition at line 469 of file spxsolver.h.

◆ remainingRoundsLeave

int remainingRoundsLeave

number of dense rounds/refactorizations until sparsePricing is enabled again

Definition at line 467 of file spxsolver.h.

◆ siderange

R siderange
protected

absolute range of all side in the problem

Definition at line 420 of file spxsolver.h.

◆ solveVector2

SSVectorBase<R>* solveVector2
private

when 2 systems are to be solved at a time; typically for speepest edge weights

Definition at line 288 of file spxsolver.h.

◆ solveVector2rhs

SSVectorBase<R>* solveVector2rhs
private

when 2 systems are to be solved at a time; typically for speepest edge weights

Definition at line 290 of file spxsolver.h.

◆ solveVector3

SSVectorBase<R>* solveVector3
private

when 3 systems are to be solved at a time; typically reserved for bound flipping ratio test (basic solution will be modified!)

Definition at line 292 of file spxsolver.h.

◆ solveVector3rhs

SSVectorBase<R>* solveVector3rhs
private

when 3 systems are to be solved at a time; typically reserved for bound flipping ratio test (basic solution will be modified!)

Definition at line 294 of file spxsolver.h.

◆ sparsePricingEnter

bool sparsePricingEnter

true if sparsePricing is turned on in the entering Simplex for slack variables

Definition at line 462 of file spxsolver.h.

◆ sparsePricingEnterCo

bool sparsePricingEnterCo

true if sparsePricing is turned on in the entering Simplex

Definition at line 463 of file spxsolver.h.

◆ sparsePricingFactor

R sparsePricingFactor
private

enable sparse pricing when viols < factor * dim()

Definition at line 327 of file spxsolver.h.

◆ sparsePricingLeave

bool sparsePricingLeave

These values enable or disable sparse pricing.

true if sparsePricing is turned on in the leaving Simplex

Definition at line 461 of file spxsolver.h.

◆ SPxBoundFlippingRT< R >

friend SPxBoundFlippingRT< R >
private

Definition at line 99 of file spxsolver.h.

◆ SPxFastRT< R >

friend SPxFastRT< R >
private

Definition at line 98 of file spxsolver.h.

◆ spxout

SPxOut* spxout

message handler

Definition at line 486 of file spxsolver.h.

◆ theCoLbound

VectorBase<R>* theCoLbound
protected

Lower bound for covars.

Definition at line 391 of file spxsolver.h.

◆ theCoPrhs

VectorBase<R>* theCoPrhs
protected

Definition at line 378 of file spxsolver.h.

◆ theCoPvec

UpdateVector<R>* theCoPvec
protected

Definition at line 379 of file spxsolver.h.

◆ theCoTest

VectorBase<R> theCoTest
protected

Definition at line 394 of file spxsolver.h.

◆ theCoUbound

VectorBase<R>* theCoUbound
protected

Upper bound for covars.

Definition at line 390 of file spxsolver.h.

◆ thecovectors

const SVSetBase<R>* thecovectors
protected

the LP coVectors according to representation

Definition at line 351 of file spxsolver.h.

◆ theCPvec

UpdateVector<R>* theCPvec
protected

column pricing vector

Definition at line 384 of file spxsolver.h.

◆ theCumulativeTime

Real theCumulativeTime
private

cumulative time spent in all calls to method solve()

Definition at line 260 of file spxsolver.h.

◆ theFrhs

VectorBase<R>* theFrhs
protected

The values of the rhs corresponding to the current basis.

Definition at line 373 of file spxsolver.h.

◆ theFvec

UpdateVector<R>* theFvec
protected

The values of all basis variables.

Definition at line 375 of file spxsolver.h.

◆ theLBbound

VectorBase<R> theLBbound
protected

Lower Basic Feasibility bound.

Definition at line 370 of file spxsolver.h.

◆ theLbound

VectorBase<R>* theLbound
protected

Lower bound for vars.

Definition at line 389 of file spxsolver.h.

◆ theLCbound

VectorBase<R> theLCbound
protected

Lower Column Feasibility bound.

Definition at line 362 of file spxsolver.h.

◆ theLRbound

VectorBase<R> theLRbound
protected

Lower Row Feasibility bound.

Definition at line 360 of file spxsolver.h.

◆ thepricer

SPxPricer<R>* thepricer
protected

Definition at line 415 of file spxsolver.h.

◆ thePricing

Pricing thePricing
private

full or partial pricing.

Definition at line 255 of file spxsolver.h.

◆ thePvec

UpdateVector<R>* thePvec
protected

The pricing VectorBase<R>

Definition at line 381 of file spxsolver.h.

◆ theratiotester

SPxRatioTester<R>* theratiotester
protected

Definition at line 416 of file spxsolver.h.

◆ theRep

Representation theRep
private

row or column representation.

Definition at line 256 of file spxsolver.h.

◆ theRPvec

UpdateVector<R>* theRPvec
protected

row pricing vector

Definition at line 383 of file spxsolver.h.

◆ theShift

R theShift
private

sum of all shifts applied to any bound.

Definition at line 281 of file spxsolver.h.

◆ thestarter

SPxStarter<R>* thestarter
protected

Definition at line 417 of file spxsolver.h.

◆ theTest

VectorBase<R> theTest
protected

Definition at line 395 of file spxsolver.h.

◆ theTime

Timer* theTime
private

time spent in last call to method solve()

Definition at line 258 of file spxsolver.h.

◆ theType

Type theType
private

entering or leaving algortihm.

Definition at line 254 of file spxsolver.h.

◆ theUBbound

VectorBase<R> theUBbound
protected

Upper Basic Feasibility bound.

In entering Simplex algorithm, the ratio test must ensure that all basic variables remain within their feasibility bounds. To give fast acces to them, the bounds of basic variables are copied into the following two vectors.

Definition at line 369 of file spxsolver.h.

◆ theUbound

VectorBase<R>* theUbound
protected

Upper bound for vars.

Definition at line 388 of file spxsolver.h.

◆ theUCbound

VectorBase<R> theUCbound
protected

Upper Column Feasibility bound.

Definition at line 361 of file spxsolver.h.

◆ theURbound

VectorBase<R> theURbound
protected

Upper Row Feasibility bound.

Definition at line 359 of file spxsolver.h.

◆ thevectors

const SVSetBase<R>* thevectors
protected

the LP vectors according to representation

Definition at line 350 of file spxsolver.h.

◆ timerType

Timer::TYPE timerType
private

type of timer (user or wallclock)

Definition at line 259 of file spxsolver.h.

◆ totalboundflips

int totalboundflips
protected

total number of bound flips

Definition at line 406 of file spxsolver.h.

◆ unitVecs

Array< UnitVectorBase<R> > unitVecs
protected

array of unit vectors

Definition at line 349 of file spxsolver.h.

◆ updateViols

DIdxSet updateViols

store indices that were changed in the previous iteration and must be checked in hyper pricing

Definition at line 448 of file spxsolver.h.

◆ updateViolsCo

DIdxSet updateViolsCo

Definition at line 449 of file spxsolver.h.

◆ weights

VectorBase<R> weights

dual pricing norms

store dual norms

Definition at line 472 of file spxsolver.h.

◆ weightsAreSetup

bool weightsAreSetup

are the dual norms already set up?

Definition at line 474 of file spxsolver.h.