SoPlex
Sequential object-oriented simPlex
Sequential object-oriented simPlex
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 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... | |
| R | computePvec (int i) |
| compute and return pVec()[i]. More... | |
| void | computePvec () |
| compute entire pVec(). More... | |
| R | 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:
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 | |
| R | epsilon () const |
| values \(|x| < \epsilon\) are considered to be 0. More... | |
| R | entertol () const |
| feasibility tolerance maintained by ratio test during ENTER algorithm. More... | |
| R | leavetol () const |
| feasibility tolerance maintained by ratio test during LEAVE algorithm. More... | |
| R | feastol () const |
| allowed primal feasibility tolerance. More... | |
| R | opttol () const |
| allowed optimality, i.e., dual feasibility tolerance. More... | |
| 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. 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... | |
| R | rhsUnscaled (int i) const |
Returns unscaled right hand side of row number i. More... | |
| R | 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... | |
| R | rowObj (int i) const |
| R | 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... | |
| R | lhsUnscaled (int i) const |
Returns unscaled left hand side of row number i. More... | |
| R | 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... | |
| R | obj (int i) const |
Returns objective value of column i. More... | |
| R | obj (const SPxColId &id) const |
Returns objective value of column with identifier id. More... | |
| R | objUnscaled (int i) const |
Returns unscaled objective value of column i. More... | |
| R | 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... | |
| R | maxObjUnscaled (int i) const |
Returns unscaled objective value of column i for maximization problem. More... | |
| R | 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... | |
| R | upperUnscaled (int i) const |
Returns unscaled upper bound of column i. More... | |
| R | 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... | |
| R | lowerUnscaled (int i) const |
Returns unscaled lower bound of column i. More... | |
| R | 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... | |
| Timer * | multTimeSparse |
| time spent in setupPupdate() exploiting sparsity More... | |
| Timer * | multTimeFull |
| time spent in setupPupdate() ignoring sparsity More... | |
| Timer * | multTimeColwise |
| time spent in setupPupdate(), columnwise multiplication More... | |
| Timer * | multTimeUnsetup |
| 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... | |
| SPxOut * | spxout |
| message handler More... | |
| DataArray< int > | integerVariables |
| supplementary variable information, 0: continous variable, 1: integer variable More... | |
| Public Attributes inherited from SPxLPBase< R > | |
| SPxOut * | spxout |
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... | |
| ClassArray & | operator= (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 Desc & | desc () const |
| Desc & | desc () |
| 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... | |
| SPxId & | baseId (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... | |
| R | condition (int maxiters=10, R tolerance=1e-6) |
| R | getEstimatedCondition () |
| R | getExactCondition () |
| R | getMatrixMetric (int type=0) |
| R | 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... | |
| R | primalDegenSum |
| the sum of the primal degeneracy percentage More... | |
| R | dualDegenSum |
| the sum of the dual degeneracy percentage More... | |
| SPxPricer< R > * | thepricer |
| SPxRatioTester< R > * | theratiotester |
| SPxStarter< R > * | thestarter |
| R | boundrange |
| absolute range of all bounds in the problem More... | |
| R | siderange |
| absolute range of all side in the problem More... | |
| R | 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< SPxId > | theBaseId |
| 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... | |
| R | nonzeroFactor |
| allowed increase of nonzeros before refactorization. More... | |
| R | fillFactor |
| allowed increase in relative fill before refactorization More... | |
| R | 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... | |
| R | lastFill |
| fill ratio that occured during last factorization More... | |
| int | lastNzCount |
| number of nonzeros in basis matrix after last fresh factorization More... | |
| Timer * | theTime |
| 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... | |
| R | 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) |
| R | 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) |
| R | 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... | |
| Timer * | theTime |
| 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 |
| R | objLimit |
| < the number of calls to the method isTimeLimitReached() More... | |
| Status | m_status |
| status of algorithm. More... | |
| R | m_nonbasicValue |
| nonbasic part of current objective value More... | |
| bool | m_nonbasicValueUpToDate |
| true, if the stored objValue is up to date More... | |
| R | m_pricingViol |
| maximal feasibility violation of current solution More... | |
| bool | m_pricingViolUpToDate |
| true, if the stored violation is up to date More... | |
| R | 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... | |
| R | m_entertol |
| feasibility tolerance maintained during entering algorithm More... | |
| R | m_leavetol |
| feasibility tolerance maintained during leaving algorithm More... | |
| R | theShift |
| sum of all shifts applied to any bound. More... | |
| R | 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 |
| R | instableLeaveVal |
| SPxId | instableEnterId |
| bool | instableEnter |
| R | instableEnterVal |
| bool | recomputedVectors |
| flag to perform clean up step to reduce numerical errors only once More... | |
| int | displayLine |
| int | displayFreq |
| R | 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: For the leaving Simplex: | |
| 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) |
| R | 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... | |
| R | 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.
| |
| 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) |
| R | 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... | |
| R | 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... | |
| R | sumDualDegeneracy () |
| get the sum of dual degeneracy More... | |
| R | 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 LPColSet & | cols () 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... | |
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.
| enum 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.
| 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.
| enum 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.
| enum SolutionPolish |
objective for solution polishing
Definition at line 239 of file spxsolver.h.
| enum Status |
| 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.
| 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 |
| COLUMN | PRIMAL | DUAL |
| Enumerator | |
|---|---|
| ENTER | Entering Simplex. The Simplex loop for the entering Simplex can be sketched as follows: |
| LEAVE | Leaving Simplex. The Simplex loop for the leaving Simplex can be sketched as follows: |
Definition at line 135 of file spxsolver.h.
| enum VarStatus |
Definition at line 200 of file spxsolver.h.
|
explicit |
default constructor.
Constructors / destructors
|
virtual |
| SPxSolverBase | ( | const SPxSolverBase< R > & | base | ) |
copy constructor
|
protectedvirtual |
Reimplemented from SPxLPBase< R >.
|
protectedvirtual |
Reimplemented from SPxLPBase< R >.
| const SPxBasisBase<R>& basis | ( | ) | const |
Return current basis.
Definition at line 1809 of file spxsolver.h.
| SPxBasisBase<R>& basis | ( | ) |
Definition at line 1814 of file spxsolver.h.
|
protected |
converts basis status to VarStatus
| int boundFlips | ( | ) | const |
get number of bound flips.
Definition at line 2137 of file spxsolver.h.
|
protected |
determine ranges of problem values for bounds, sides and objective to assess numerical difficulties
|
virtual |
Reimplemented from SPxLPBase< R >.
Referenced by SPxSolverBase< R >::changeBounds().
|
virtual |
Reimplemented from SPxLPBase< R >.
|
virtual |
Reimplemented from SPxLPBase< R >.
Definition at line 1051 of file spxsolver.h.
References SPxSolverBase< R >::changeBounds(), SPxSolverBase< R >::changeLhs(), SPxSolverBase< R >::changeLhsStatus(), and SPxLPBase< R >::number().
|
virtual |
Reimplemented from SPxLPBase< R >.
|
virtual |
Reimplemented from SPxLPBase< R >.
Definition at line 1103 of file spxsolver.h.
|
virtual |
Reimplemented from SPxLPBase< R >.
|
virtual |
Reimplemented from SPxLPBase< R >.
Definition at line 1111 of file spxsolver.h.
|
virtual |
Reimplemented from SPxLPBase< R >.
Referenced by SPxSolverBase< R >::changeBounds().
|
virtual |
Reimplemented from SPxLPBase< R >.
|
virtual |
Reimplemented from SPxLPBase< R >.
Definition at line 1064 of file spxsolver.h.
|
virtual |
Referenced by SPxSolverBase< R >::changeBounds().
|
virtual |
Reimplemented from SPxLPBase< R >.
|
virtual |
Reimplemented from SPxLPBase< R >.
|
virtual |
Reimplemented from SPxLPBase< R >.
Definition at line 1028 of file spxsolver.h.
|
virtual |
|
virtual |
Reimplemented from SPxLPBase< R >.
|
virtual |
Reimplemented from SPxLPBase< R >.
|
virtual |
overloading a virtual function
Reimplemented from SPxLPBase< R >.
Definition at line 1000 of file spxsolver.h.
|
virtual |
scale determines whether the new data needs to be scaled according to the existing LP (persistent scaling)
Reimplemented from SPxLPBase< R >.
|
virtual |
Reimplemented from SPxLPBase< R >.
|
virtual |
overloading a virtual function
Reimplemented from SPxLPBase< R >.
Definition at line 990 of file spxsolver.h.
|
virtual |
Reimplemented from SPxLPBase< R >.
|
virtual |
Reimplemented from SPxLPBase< R >.
|
virtual |
Reimplemented from SPxLPBase< R >.
Definition at line 1087 of file spxsolver.h.
|
virtual |
Reimplemented from SPxLPBase< R >.
|
virtual |
Reimplemented from SPxLPBase< R >.
|
virtual |
Reimplemented from SPxLPBase< R >.
Definition at line 1076 of file spxsolver.h.
|
virtual |
|
virtual |
Reimplemented from SPxLPBase< R >.
|
virtual |
Reimplemented from SPxLPBase< R >.
Definition at line 1095 of file spxsolver.h.
|
virtual |
Reimplemented from SPxLPBase< R >.
|
virtual |
Reimplemented from SPxLPBase< R >.
|
virtual |
Reimplemented from SPxLPBase< R >.
Definition at line 1010 of file spxsolver.h.
|
virtual |
Reimplemented from SPxLPBase< R >.
|
virtual |
Reimplemented from SPxLPBase< R >.
|
virtual |
overloading virtual function
Reimplemented from SPxLPBase< R >.
Definition at line 1040 of file spxsolver.h.
|
virtual |
|
virtual |
clear all data in solver.
Reimplemented from SPxLPBase< R >.
|
protected |
The following methods serve for initializing the bounds for dual or primal Simplex algorithm of entering or leaving type.
|
virtual |
Reimplemented from SPxLPBase< R >.
Definition at line 1015 of file spxsolver.h.
|
protectedvirtual |
| int coDim | ( | ) | const |
codimension.
Definition at line 1128 of file spxsolver.h.
| 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().
| SPxColId colId | ( | int | i | ) | const |
ColId of i 'th column.
Definition at line 2330 of file spxsolver.h.
| const LPColSet& cols | ( | ) | const |
return const lp's cols if available.
Definition at line 2226 of file spxsolver.h.
|
private |
compute coTest vector.
|
protected |
|
protected |
|
protectedvirtual |
compute theCoPrhs for entering Simplex.
|
protected |
|
protected |
|
protected |
compute feasibility vector from scratch.
|
protectedvirtual |
|
protected |
|
protectedvirtual |
|
private |
compute basis feasibility test vector.
|
protectedvirtual |
compute theCoPrhs for leaving Simplex.
|
protected |
|
protected |
|
protected |
Compute the primal ray or the farkas proof in case of unboundedness or infeasibility.
|
protected |
| R computePvec | ( | int | i | ) |
compute and return pVec()[i].
| void computePvec | ( | ) |
compute entire pVec().
| void computeTest | ( | ) |
compute test VectorBase<R> in ENTERing Simplex.
| 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.
| 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.
| 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.
|
private |
test coVector i with status stat.
| SPxBasisBase<R>::Desc::Status covarStatus | ( | int | i | ) | const |
Status of i 'th covariable.
Definition at line 1305 of file spxsolver.h.
| const SVectorBase<R>& coVector | ( | int | i | ) | const |
i 'th covector of LP.
i 'th, 0 <= i < dim(), covector of the loaded LP (with respect to the chosen representation). Definition at line 1249 of file spxsolver.h.
| const SVectorBase<R>& coVector | ( | const SPxRowId & | rid | ) | const |
Definition at line 1254 of file spxsolver.h.
| const SVectorBase<R>& coVector | ( | const SPxColId & | cid | ) | const |
Definition at line 1262 of file spxsolver.h.
| const SVectorBase<R>& coVector | ( | const SPxId & | p_id | ) | const |
coVector associated to p_id.
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.
| Real cumulativeTime | ( | ) | const |
cumulative time spent in all calls to method solve().
Definition at line 2208 of file spxsolver.h.
| 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.
| int dim | ( | ) | const |
dimension of basis matrix.
Definition at line 1123 of file spxsolver.h.
|
protectedvirtual |
|
protectedvirtual |
Reimplemented from SPxLPBase< R >.
|
protectedvirtual |
Reimplemented from SPxLPBase< R >.
|
protectedvirtual |
Reimplemented from SPxLPBase< R >.
|
protectedvirtual |
Reimplemented from SPxLPBase< R >.
| int dualDegeneratePivots | ( | ) |
get number of dual degenerate pivots
Definition at line 2143 of file spxsolver.h.
| int dualIterations | ( | ) |
return number of iterations done with primal algorithm
Definition at line 2180 of file spxsolver.h.
|
private |
let id enter the basis and manage leaving of another one.
false if LP is unbounded/infeasible. | R entertol | ( | ) | const |
feasibility tolerance maintained by ratio test during ENTER algorithm.
Definition at line 815 of file spxsolver.h.
|
protectedvirtual |
Get pointer to the id 'th vector.
Definition at line 1944 of file spxsolver.h.
| 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.
|
virtual |
Factorize basis matrix.
| SPxStatusException | if loaded matrix is singular |
Reimplemented from SPxBasisBase< R >.
| R feastol | ( | ) | const |
allowed primal feasibility tolerance.
Definition at line 829 of file spxsolver.h.
| void forceRecompNonbasicValue | ( | ) |
Definition at line 696 of file spxsolver.h.
| 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.
| 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.
| 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.
| Status getBasis | ( | VarStatus | rows[], |
| VarStatus | cols[], | ||
| const int | rowsSize = -1, |
||
| const int | colsSize = -1 |
||
| ) | const |
get current basis, and return solver status.
| VarStatus getBasisColStatus | ( | int | col | ) | const |
gets basis status for a single column
|
virtual |
Definition at line 933 of file spxsolver.h.
| VarStatus getBasisRowStatus | ( | int | row | ) | const |
gets basis status for a single row
| SPxBasisBase<R>::SPxStatus getBasisStatus | ( | ) | const |
gets basis status
Definition at line 2088 of file spxsolver.h.
| bool getComputeDegeneracy | ( | ) | const |
returns whether the degeneracy is computed in each iteration
Definition at line 2289 of file spxsolver.h.
| int getDecompIterationLimit | ( | ) | const |
returns the iteration limit for the decomposition simplex initialisation
Definition at line 2315 of file spxsolver.h.
| DecompStatus getDecompStatus | ( | ) | const |
returns whether a basis needs to be found for the improved dual simplex
Definition at line 2273 of file spxsolver.h.
| int getDegenCompOffset | ( | ) | const |
gets the offset for the number of iterations before the degeneracy is computed
Definition at line 2303 of file spxsolver.h.
| R getDegeneracyLevel | ( | VectorBase< R > | degenvec | ) |
get level of dual degeneracy
| int getDisplayFreq | ( | ) |
get display frequency
Definition at line 887 of file spxsolver.h.
|
virtual |
get dual farkas proof of infeasibility.
| SPxStatusException | if no problem loaded |
| bool getDualNorms | ( | int & | nnormsRow, |
| int & | nnormsCol, | ||
| R * | norms | ||
| ) | const |
get dual norms
|
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().
| SPxStatusException | if no problem loaded |
|
protectedvirtual |
|
protectedvirtual |
|
protectedvirtual |
|
protectedvirtual |
| void getLhs | ( | VectorBase< R > & | p_lhs | ) | const |
copy lhs value VectorBase<R> to p_lhs.
Definition at line 2243 of file spxsolver.h.
| void getLower | ( | VectorBase< R > & | p_low | ) | const |
copy lower bound VectorBase<R> to p_low.
Definition at line 2232 of file spxsolver.h.
| int getMaxIters | ( | ) |
the maximum number of iterations
Definition at line 2214 of file spxsolver.h.
| Real getMaxTime | ( | ) |
the maximum runtime
Definition at line 2202 of file spxsolver.h.
| void getNdualNorms | ( | int & | nnormsRow, |
| int & | nnormsCol | ||
| ) | const |
get number of dual norms
|
virtual |
get primal ray in case of unboundedness.
| SPxStatusException | if no problem loaded |
|
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().
| SPxStatusException | if not initialized |
|
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\).
| SPxStatusException | if no problem loaded |
| 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.
| void getRhs | ( | VectorBase< R > & | p_rhs | ) | const |
copy rhs value VectorBase<R> to p_rhs.
Definition at line 2249 of file spxsolver.h.
|
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().
| SPxStatusException | if no problem loaded |
| SolutionPolish getSolutionPolishing | ( | ) |
return objective of solution polishing
Definition at line 676 of file spxsolver.h.
| Timer::TYPE getTiming | ( | ) |
set timing type
Definition at line 870 of file spxsolver.h.
| void getUpper | ( | VectorBase< R > & | p_up | ) | const |
copy upper bound VectorBase<R> to p_up.
Definition at line 2237 of file spxsolver.h.
| void hyperPricing | ( | bool | h | ) |
enable or disable hyper sparse pricing
| 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().
|
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().
| void initRep | ( | Representation | p_rep | ) |
| void invalidateBasis | ( | ) |
invalidates the basis, triggers refactorization
| bool isBasic | ( | typename SPxBasisBase< R >::Desc::Status | stat | ) | const |
does stat describe a basic index ?
Definition at line 1311 of file spxsolver.h.
| bool isBasic | ( | const SPxId & | p_id | ) | const |
is the p_id 'th vector basic ?
Definition at line 1317 of file spxsolver.h.
| bool isBasic | ( | const SPxRowId & | rid | ) | const |
is the rid 'th vector basic ?
Definition at line 1326 of file spxsolver.h.
| bool isBasic | ( | const SPxColId & | cid | ) | const |
is the cid 'th vector basic ?
Definition at line 1332 of file spxsolver.h.
| bool isBasic | ( | int | i | ) | const |
is the i 'th vector basic ?
Definition at line 1350 of file spxsolver.h.
check a given basis for validity.
| bool isCoBasic | ( | int | i | ) | const |
is the i 'th covector basic ?
Definition at line 1356 of file spxsolver.h.
| 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.
| bool isColBasic | ( | int | i | ) | const |
is the i 'th column vector basic ?
Definition at line 1344 of file spxsolver.h.
| bool isConsistent | ( | ) | const |
check consistency.
Miscellaneous
| 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().
|
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.
| bool isRowBasic | ( | int | i | ) | const |
is the i 'th row vector basic ?
Definition at line 1338 of file spxsolver.h.
| bool isTimeLimitReached | ( | const bool | forceCheck = false | ) |
returns whether current time limit is reached; call to time() may be skipped unless forceCheck is true
| int iterations | ( | ) | const |
get number of iterations of current solution.
Definition at line 2167 of file spxsolver.h.
| const VectorBase<R>& lbBound | ( | ) | const |
lower bound for fVec.
Definition at line 1407 of file spxsolver.h.
| 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.
| const VectorBase<R>& lcBound | ( | ) | const |
Definition at line 1486 of file spxsolver.h.
| 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.
|
private |
let index i leave the basis and manage entering of another one.
false if LP is unbounded/infeasible. | R leavetol | ( | ) | const |
feasibility tolerance maintained by ratio test during LEAVE algorithm.
Definition at line 822 of file spxsolver.h.
|
virtual |
set a start basis.
|
virtual |
copy LP.
|
private |
|
private |
| const VectorBase<R>& lpBound | ( | ) | const |
Definition at line 1552 of file spxsolver.h.
| 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.
| 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.
|
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.
|
protected |
|
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
| int numCycle | ( | ) | const |
actual number of degenerate simplex steps encountered so far.
Definition at line 922 of file spxsolver.h.
|
virtual |
get objective value of current solution.
Definition at line 2051 of file spxsolver.h.
| SPxSolverBase<R>& operator= | ( | const SPxSolverBase< R > & | base | ) |
assignment operator
assignment operator and copy constructor
| R opttol | ( | ) | const |
allowed optimality, i.e., dual feasibility tolerance.
Definition at line 837 of file spxsolver.h.
| 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.
|
private |
|
private |
|
protectedvirtual |
perturb basis bounds.
|
protectedvirtual |
perturb nonbasic bounds.
|
private |
|
private |
|
protectedvirtual |
|
protectedvirtual |
| int polishIterations | ( | ) |
return number of iterations done with primal algorithm
Definition at line 2186 of file spxsolver.h.
|
protectedvirtual |
is the solution precise enough, or should we increase delta() ?
| const SPxPricer<R>* pricer | ( | ) | const |
return loaded SPxPricer.
Definition at line 1819 of file spxsolver.h.
| Pricing pricing | ( | ) | const |
return current Pricing.
Definition at line 541 of file spxsolver.h.
| int primalDegeneratePivots | ( | ) |
get number of primal degenerate pivots
Definition at line 2149 of file spxsolver.h.
| int primalIterations | ( | ) |
return number of iterations done with primal algorithm
Definition at line 2173 of file spxsolver.h.
|
virtual |
print display line of flying table
| 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.
|
virtual |
get violations of bounds.
|
virtual |
get violation of constraints.
|
virtual |
get violation of optimality criterion.
|
virtual |
get the residuum |Ax-b|.
| const SPxRatioTester<R>* ratiotester | ( | ) | const |
return loaded SPxRatioTester.
Definition at line 1829 of file spxsolver.h.
|
virtual |
read LP from input stream.
Reimplemented from SPxLPBase< R >.
|
virtual |
Load basis from filename in MPS format. If rowNames and colNames are NULL, default names are used for the constraints and variables.
|
protectedvirtual |
reset dimensions of vectors according to loaded LP.
|
protectedvirtual |
setup all vecs fresh
|
protectedvirtual |
|
protectedvirtual |
|
virtual |
reload LP.
| Representation rep | ( | ) | const |
return the current basis representation.
Definition at line 529 of file spxsolver.h.
|
protected |
resets clock average statistics
| void resetCumulativeTime | ( | ) |
reset cumulative time counter to zero.
Definition at line 2131 of file spxsolver.h.
| SPxRowId rowId | ( | int | i | ) | const |
RowId of i 'th inequality.
Mapping between numbers and Ids
Definition at line 2325 of file spxsolver.h.
| const LPRowSetBase<R>& rows | ( | ) | const |
return const lp's rows if available.
Definition at line 2220 of file spxsolver.h.
optimization sense.
Definition at line 2255 of file spxsolver.h.
|
virtual |
setup linear solver to use. If destroy is true, slusolver will be freed in destructor.
| void setBasisStatus | ( | typename SPxBasisBase< R >::SPxStatus | stat | ) |
set the lp solver's basis status.
Definition at line 2100 of file spxsolver.h.
| void setComputeDegenFlag | ( | bool | computeDegen | ) |
sets whether the degeneracy is computed at each iteration
Definition at line 2282 of file spxsolver.h.
| void setDecompIterationLimit | ( | int | iterationLimit | ) |
sets the iteration limit for the decomposition simplex initialisation
Definition at line 2309 of file spxsolver.h.
| void setDecompStatus | ( | DecompStatus | decomp_stat | ) |
turn on or off the improved dual simplex.
| 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.
| void setDelta | ( | R | d | ) |
set parameter delta, i.e., set feastol and opttol to same value.
| void setDisplayFreq | ( | int | freq | ) |
set display frequency
Definition at line 881 of file spxsolver.h.
|
private |
|
protected |
| bool setDualNorms | ( | int | nnormsRow, |
| int | nnormsCol, | ||
| R * | norms | ||
| ) |
set dual norms
|
protected |
|
protected |
|
protected |
|
protectedvirtual |
| void setFeastol | ( | R | d | ) |
set parameter feastol.
| void setFillFactor | ( | R | 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.
| void setIntegralityInformation | ( | int | ncols, |
| int * | intInfo | ||
| ) |
pass integrality information about the variables to the solver
|
protected |
|
protected |
|
protectedvirtual |
| void setMemFactor | ( | R | f | ) |
set refactor threshold for memory growth in current factor update compared to the last factorization
Definition at line 511 of file spxsolver.h.
| void setMetricInformation | ( | int | type | ) |
print basis metric within the usual output
Definition at line 893 of file spxsolver.h.
| void setNonzeroFactor | ( | R | f | ) |
set refactor threshold for nonzeros in last factorized basis matrix compared to updated basis matrix
Definition at line 499 of file spxsolver.h.
| void setOpttol | ( | R | d | ) |
set parameter opttol.
| void setOutstream | ( | SPxOut & | newOutstream | ) |
Definition at line 492 of file spxsolver.h.
|
virtual |
setup pricer to use. If destroy is true, pricer will be freed in destructor.
|
private |
|
protected |
setup feasibility bounds for entering algorithm
|
private |
| void setRep | ( | Representation | p_rep | ) |
|
private |
| 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.
| void setSolverStatus | ( | typename SPxSolverBase< R >::Status | stat | ) |
setting the solver status external from the solve loop.
Definition at line 2109 of file spxsolver.h.
| void setSparsePricingFactor | ( | R | fac | ) |
Definition at line 899 of file spxsolver.h.
|
virtual |
setup starting basis generator to use. If destroy is true, starter will be freed in destructor.
|
virtual |
set iteration limit.
set time limit.
Limits and status inquiry
|
virtual |
set objective limit.
|
virtual |
setup ratio-tester to use. If destroy is true, tester will be freed in destructor.
| void setTiming | ( | Timer::TYPE | ttype | ) |
set timing type
Definition at line 859 of file spxsolver.h.
| 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.
| 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.
| 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.
| 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.
|
protectedvirtual |
|
virtual |
total current shift amount.
Definition at line 1675 of file spxsolver.h.
| void shiftFvec | ( | ) |
Perform initial shifting to optain an feasible or pricable basis.
| void shiftLBbound | ( | int | i, |
| R | to | ||
| ) |
shift i 'th lbBound to to.
Definition at line 1632 of file spxsolver.h.
| void shiftLCbound | ( | int | i, |
| R | to | ||
| ) |
shift i 'th lcBound to to.
Definition at line 1664 of file spxsolver.h.
| void shiftLPbound | ( | int | i, |
| R | to | ||
| ) |
shift i 'th lpBound to to.
Definition at line 1648 of file spxsolver.h.
| void shiftPvec | ( | ) |
Perform initial shifting to optain an feasible or pricable basis.
| void shiftUBbound | ( | int | i, |
| R | to | ||
| ) |
shift i 'th ubBound to to.
Definition at line 1624 of file spxsolver.h.
| void shiftUCbound | ( | int | i, |
| R | to | ||
| ) |
shift i 'th ucBound to to.
Definition at line 1656 of file spxsolver.h.
| void shiftUPbound | ( | int | i, |
| R | to | ||
| ) |
shift i 'th upBound to to.
Definition at line 1640 of file spxsolver.h.
| const SLinSolver<R>* slinSolver | ( | ) | const |
return loaded SLinSolver.
Definition at line 1824 of file spxsolver.h.
|
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.
| SPxStatusException | if either no problem, solver, pricer or ratiotester loaded or if solve is still running when it shouldn't be |
| SPxStarter<R>* starter | ( | ) | const |
return current starter.
Definition at line 547 of file spxsolver.h.
| std::string statistics | ( | ) | const |
returns statistical information in form of a string.
Definition at line 2261 of file spxsolver.h.
| Status status | ( | ) | const |
Status of solution process.
| int subversion | ( | ) | const |
return the internal subversion of SPxSolverBase as number
Definition at line 524 of file spxsolver.h.
| R sumDualDegeneracy | ( | ) |
get the sum of dual degeneracy
Definition at line 2155 of file spxsolver.h.
| R sumPrimalDegeneracy | ( | ) |
get the sum of primal degeneracy
Definition at line 2161 of file spxsolver.h.
|
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).
|
virtual |
return iteration limit.
|
virtual |
return time limit.
|
virtual |
return objective limit.
| 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.
|
private |
test VectorBase<R> i with status stat.
| void testBounds | ( | ) | const |
| void testVecs | ( | ) |
| Real time | ( | ) | const |
time spent in last call to method solve().
Definition at line 2192 of file spxsolver.h.
| Type type | ( | ) | const |
return current Type.
Definition at line 535 of file spxsolver.h.
| const VectorBase<R>& ubBound | ( | ) | const |
upper bound for fVec.
Definition at line 1389 of file spxsolver.h.
| 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.
| const VectorBase<R>& ucBound | ( | ) | const |
Definition at line 1465 of file spxsolver.h.
| 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.
|
protectedvirtual |
|
protectedvirtual |
uninitialize data structures.
Definition at line 1907 of file spxsolver.h.
| const SVectorBase<R>& unitVector | ( | int | i | ) | const |
return i 'th unit vector.
Definition at line 1284 of file spxsolver.h.
| void unscaleLPandReloadBasis | ( | ) |
unscales the LP and reloads the basis
|
virtual |
remove shift as much as possible.
| const VectorBase<R>& upBound | ( | ) | const |
Definition at line 1531 of file spxsolver.h.
| 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.
|
private |
recompute coTest vector.
|
private |
update basis feasibility test vector.
| bool updateNonbasicValue | ( | R | objChange | ) |
|
private |
recompute test vector.
| void useFullPerturbation | ( | bool | full | ) |
perturb entire problem or only the bounds relevant to the current pivot
Definition at line 928 of file spxsolver.h.
|
virtual |
current objective value.
| SPxBasisBase<R>::Desc::Status varStatus | ( | int | i | ) | const |
Status of i 'th variable.
Definition at line 1299 of file spxsolver.h.
|
protected |
converts VarStatus to basis status for columns
|
protected |
converts VarStatus to basis status for rows
| const SVectorBase<R>& vector | ( | int | i | ) | const |
i 'th vector.
i 'th, 0 <= i < coDim(), vector of the loaded LP (with respect to the chosen representation). Definition at line 1205 of file spxsolver.h.
| const SVectorBase<R>& vector | ( | const SPxRowId & | rid | ) | const |
Definition at line 1211 of file spxsolver.h.
| const SVectorBase<R>& vector | ( | const SPxColId & | cid | ) | const |
Definition at line 1219 of file spxsolver.h.
| const SVectorBase<R>& vector | ( | const SPxId & | p_id | ) | const |
VectorBase<R> associated to p_id.
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. Definition at line 1236 of file spxsolver.h.
| int version | ( | ) | const |
return the version of SPxSolverBase as number like 123 for 1.2.3
Definition at line 519 of file spxsolver.h.
|
virtual |
Write basis to filename in MPS format. If rowNames and colNames are NULL, default names are used for the constraints and variables.
|
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.
|
protected |
storage for thePvec = &addVec
Definition at line 357 of file spxsolver.h.
|
protected |
number of performed bound flips
Definition at line 405 of file spxsolver.h.
|
protected |
absolute range of all bounds in the problem
Definition at line 419 of file spxsolver.h.
|
private |
Definition at line 331 of file spxsolver.h.
|
private |
when 2 systems are to be solved at a time; typically for speepest edge weights
Definition at line 296 of file spxsolver.h.
|
private |
when 2 systems are to be solved at a time; typically for speepest edge weights
Definition at line 298 of file spxsolver.h.
|
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.
|
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.
| VectorBase<R> coWeights |
store dual norms
Definition at line 473 of file spxsolver.h.
|
private |
the maximum number of iterations before the decomposition simplex is aborted.
Definition at line 335 of file spxsolver.h.
|
private |
the number of iterations performed before the degeneracy level is computed
Definition at line 333 of file spxsolver.h.
|
private |
Definition at line 326 of file spxsolver.h.
|
private |
Definition at line 325 of file spxsolver.h.
|
protected |
the sum of the dual degeneracy percentage
Definition at line 413 of file spxsolver.h.
|
protected |
stores dual farkas proof in case of infeasibility
Definition at line 398 of file spxsolver.h.
|
protected |
rhs VectorBase<R> for computing the dual vector
Definition at line 355 of file spxsolver.h.
|
protected |
dual vector
Definition at line 356 of file spxsolver.h.
|
protected |
number of ENTER iterations
Definition at line 401 of file spxsolver.h.
|
protected |
the number of degenerate steps during the entering algorithm
Definition at line 408 of file spxsolver.h.
|
protected |
the number of degenerate candidates in the entering algorithm
Definition at line 410 of file spxsolver.h.
|
private |
true iff thepricer should be freed inside of object
Definition at line 304 of file spxsolver.h.
|
private |
true iff theratiotester should be freed inside of object
Definition at line 305 of file spxsolver.h.
|
private |
true iff thestarter should be freed inside of object
Definition at line 306 of file spxsolver.h.
|
private |
whether to perturb the entire problem or just the bounds relevant for the current pivot
Definition at line 338 of file spxsolver.h.
|
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.
| bool hyperPricingEnter |
true if hyper sparse pricing is turned on in the entering Simplex
Definition at line 465 of file spxsolver.h.
| bool hyperPricingLeave |
true if hyper sparse pricing is turned on in the leaving Simplex
Definition at line 464 of file spxsolver.h.
| 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.
| DIdxSet infeasibilitiesCo |
For the entering Simplex algorithm these vectors contains the indices of infeasible basic variables.
Definition at line 445 of file spxsolver.h.
|
private |
true, if all vectors are setup.
Definition at line 285 of file spxsolver.h.
|
private |
Definition at line 319 of file spxsolver.h.
|
private |
Definition at line 318 of file spxsolver.h.
|
private |
Definition at line 320 of file spxsolver.h.
|
private |
Definition at line 312 of file spxsolver.h.
|
private |
Definition at line 311 of file spxsolver.h.
|
private |
Definition at line 313 of file spxsolver.h.
| DataArray<int> integerVariables |
supplementary variable information, 0: continous variable, 1: integer variable
Definition at line 489 of file spxsolver.h.
| 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.
| 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.
|
private |
for forcing feasibility.
Definition at line 282 of file spxsolver.h.
|
protected |
number of LEAVE iterations
Definition at line 400 of file spxsolver.h.
|
protected |
the number of degenerate steps during the leaving algorithm
Definition at line 409 of file spxsolver.h.
|
protected |
the number of degenerate candidates in the leaving algorithm
Definition at line 411 of file spxsolver.h.
|
private |
feasibility tolerance maintained during entering algorithm
Definition at line 279 of file spxsolver.h.
|
private |
feasibility tolerance maintained during leaving algorithm
Definition at line 280 of file spxsolver.h.
|
private |
maximum steps before cycling is detected.
Definition at line 283 of file spxsolver.h.
|
private |
nonbasic part of current objective value
Definition at line 268 of file spxsolver.h.
|
private |
true, if the stored objValue is up to date
Definition at line 269 of file spxsolver.h.
|
private |
actual number of degenerate steps so far.
Definition at line 284 of file spxsolver.h.
|
private |
number of violations of current solution
Definition at line 277 of file spxsolver.h.
|
private |
maximal feasibility violation of current solution
Definition at line 271 of file spxsolver.h.
|
private |
maximal feasibility violation of current solution in coDim
Definition at line 275 of file spxsolver.h.
|
private |
true, if the stored violation in coDim is up to date
Definition at line 276 of file spxsolver.h.
|
private |
true, if the stored violation is up to date
Definition at line 272 of file spxsolver.h.
|
private |
status of algorithm.
Definition at line 266 of file spxsolver.h.
|
private |
maximum allowed iterations.
Definition at line 261 of file spxsolver.h.
|
private |
maximum allowed time.
Definition at line 262 of file spxsolver.h.
| int multColwiseCalls |
number of products, columnwise multiplication
Definition at line 483 of file spxsolver.h.
| int multFullCalls |
number of products ignoring sparsity
Definition at line 482 of file spxsolver.h.
| int multSparseCalls |
number of products exploiting sparsity
Definition at line 481 of file spxsolver.h.
| Timer* multTimeColwise |
time spent in setupPupdate(), columnwise multiplication
Definition at line 479 of file spxsolver.h.
| Timer* multTimeFull |
time spent in setupPupdate() ignoring sparsity
Definition at line 478 of file spxsolver.h.
| Timer* multTimeSparse |
time spent in setupPupdate() exploiting sparsity
Definition at line 477 of file spxsolver.h.
| Timer* multTimeUnsetup |
time spent in setupPupdate() w/o sparsity information
Definition at line 480 of file spxsolver.h.
| int multUnsetupCalls |
number of products w/o sparsity information
Definition at line 484 of file spxsolver.h.
|
private |
Definition at line 264 of file spxsolver.h.
|
private |
remaining number of times the clock can be safely skipped
Definition at line 263 of file spxsolver.h.
|
private |
< the number of calls to the method isTimeLimitReached()
objective value limit.
Definition at line 265 of file spxsolver.h.
|
protected |
absolute range of all objective coefficients in the problem
Definition at line 421 of file spxsolver.h.
|
protected |
number of solution polishing iterations
Definition at line 403 of file spxsolver.h.
|
private |
objective of solution polishing
Definition at line 257 of file spxsolver.h.
|
protected |
number of primal iterations
Definition at line 402 of file spxsolver.h.
|
protected |
the sum of the primal degeneracy percentage
Definition at line 412 of file spxsolver.h.
|
protected |
stores primal ray in case of unboundedness
Definition at line 397 of file spxsolver.h.
|
protected |
rhs VectorBase<R> for computing the primal vector
Definition at line 353 of file spxsolver.h.
|
protected |
primal vector
Definition at line 354 of file spxsolver.h.
|
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 |
The random number generator used throughout the whole computation. Its seed can be modified.
Definition at line 437 of file spxsolver.h.
|
private |
flag to perform clean up step to reduce numerical errors only once
Definition at line 323 of file spxsolver.h.
| int remainingRoundsEnter |
Definition at line 468 of file spxsolver.h.
| int remainingRoundsEnterCo |
Definition at line 469 of file spxsolver.h.
| int remainingRoundsLeave |
number of dense rounds/refactorizations until sparsePricing is enabled again
Definition at line 467 of file spxsolver.h.
|
protected |
absolute range of all side in the problem
Definition at line 420 of file spxsolver.h.
|
private |
when 2 systems are to be solved at a time; typically for speepest edge weights
Definition at line 288 of file spxsolver.h.
|
private |
when 2 systems are to be solved at a time; typically for speepest edge weights
Definition at line 290 of file spxsolver.h.
|
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.
|
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.
| bool sparsePricingEnter |
true if sparsePricing is turned on in the entering Simplex for slack variables
Definition at line 462 of file spxsolver.h.
| bool sparsePricingEnterCo |
true if sparsePricing is turned on in the entering Simplex
Definition at line 463 of file spxsolver.h.
|
private |
enable sparse pricing when viols < factor * dim()
Definition at line 327 of file spxsolver.h.
| 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.
|
private |
Definition at line 99 of file spxsolver.h.
|
private |
Definition at line 98 of file spxsolver.h.
| SPxOut* spxout |
message handler
Definition at line 486 of file spxsolver.h.
|
protected |
Lower bound for covars.
Definition at line 391 of file spxsolver.h.
|
protected |
Definition at line 378 of file spxsolver.h.
|
protected |
Definition at line 379 of file spxsolver.h.
|
protected |
Definition at line 394 of file spxsolver.h.
|
protected |
Upper bound for covars.
Definition at line 390 of file spxsolver.h.
|
protected |
the LP coVectors according to representation
Definition at line 351 of file spxsolver.h.
|
protected |
column pricing vector
Definition at line 384 of file spxsolver.h.
|
private |
cumulative time spent in all calls to method solve()
Definition at line 260 of file spxsolver.h.
|
protected |
The values of the rhs corresponding to the current basis.
Definition at line 373 of file spxsolver.h.
|
protected |
The values of all basis variables.
Definition at line 375 of file spxsolver.h.
|
protected |
Lower Basic Feasibility bound.
Definition at line 370 of file spxsolver.h.
|
protected |
Lower bound for vars.
Definition at line 389 of file spxsolver.h.
|
protected |
Lower Column Feasibility bound.
Definition at line 362 of file spxsolver.h.
|
protected |
Lower Row Feasibility bound.
Definition at line 360 of file spxsolver.h.
|
protected |
Definition at line 415 of file spxsolver.h.
|
private |
full or partial pricing.
Definition at line 255 of file spxsolver.h.
|
protected |
The pricing VectorBase<R>
Definition at line 381 of file spxsolver.h.
|
protected |
Definition at line 416 of file spxsolver.h.
|
private |
row or column representation.
Definition at line 256 of file spxsolver.h.
|
protected |
row pricing vector
Definition at line 383 of file spxsolver.h.
|
private |
sum of all shifts applied to any bound.
Definition at line 281 of file spxsolver.h.
|
protected |
Definition at line 417 of file spxsolver.h.
|
protected |
Definition at line 395 of file spxsolver.h.
|
private |
time spent in last call to method solve()
Definition at line 258 of file spxsolver.h.
|
private |
entering or leaving algortihm.
Definition at line 254 of file spxsolver.h.
|
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.
|
protected |
Upper bound for vars.
Definition at line 388 of file spxsolver.h.
|
protected |
Upper Column Feasibility bound.
Definition at line 361 of file spxsolver.h.
|
protected |
Upper Row Feasibility bound.
Definition at line 359 of file spxsolver.h.
|
protected |
the LP vectors according to representation
Definition at line 350 of file spxsolver.h.
|
private |
type of timer (user or wallclock)
Definition at line 259 of file spxsolver.h.
|
protected |
total number of bound flips
Definition at line 406 of file spxsolver.h.
|
protected |
array of unit vectors
Definition at line 349 of file spxsolver.h.
| 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.
| DIdxSet updateViolsCo |
Definition at line 449 of file spxsolver.h.
| VectorBase<R> weights |
| bool weightsAreSetup |
are the dual norms already set up?
Definition at line 474 of file spxsolver.h.