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 Types | |
Data Types | |
| enum | Representation { ROW = -1, COLUMN = 1 } |
| LP basis representation. More... | |
| enum | Type { ENTER = -1, LEAVE = 1 } |
| Algorithmic type. More... | |
| enum | Pricing { FULL, PARTIAL } |
| Pricing type. More... | |
| enum | VarStatus { ON_UPPER, ON_LOWER, FIXED, ZERO, BASIC, UNDEFINED } |
| enum | Status { ERROR = -15, NO_RATIOTESTER = -14, NO_PRICER = -13, NO_SOLVER = -12, NOT_INIT = -11, ABORT_CYCLING = -8, ABORT_TIME = -7, ABORT_ITER = -6, ABORT_VALUE = -5, SINGULAR = -4, NO_PROBLEM = -3, REGULAR = -2, RUNNING = -1, UNKNOWN = 0, OPTIMAL = 1, UNBOUNDED = 2, INFEASIBLE = 3, INForUNBD = 4, OPTIMAL_UNSCALED_VIOLATIONS = 5 } |
| enum | SolutionPolish { POLISH_OFF, POLISH_INTEGRALITY, POLISH_FRACTIONALITY } |
| objective for solution polishing More... | |
 Public Types inherited from SPxLPBase< R > | |
| enum | SPxSense { MAXIMIZE = 1, MINIMIZE = -1 } |
| Optimization sense. More... | |
Public Member Functions | |
| void | setOutstream (SPxOut &newOutstream) |
| virtual void | setTolerances (std::shared_ptr< Tolerances > newTolerances) |
| set the _tolerances member variable More... | |
| const std::shared_ptr< Tolerances > & | tolerances () const |
| returns current tolerances More... | |
| 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... | |
| 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, bool polish=true) |
| solve loaded LP. More... | |
| bool | 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... | |
| void | scaleEntertol (R d) |
| scale the entering tolerance More... | |
| void | scaleLeavetol (R d) |
| scale the leaving tolerance More... | |
| void | scaleTolerances (R d) |
| R | delta () const |
| guaranteed primal and dual bound violation for optimal solution, returning the maximum of floatingPointFeastol() and floatingPointOpttol(). 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... | |
| DataArray< VarStatus > & | getOldBasisStatusRows () |
| DataArray< VarStatus > & | getOldBasisStatusCols () |
| void | setSolvingForBoosted (bool value) |
| void | setStoreBasisFreqForBoosting (int freq) |
| 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... | |
| const std::shared_ptr< Tolerances > | tolerances () const |
| returns current tolerances 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 SPxLPBase< R > | |
| std::shared_ptr< Tolerances > | _tolerances |
| 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 | entertolscale |
| factor to temporarily decrease the entering tolerance More... | |
| R | leavetolscale |
| factor to temporarily decrease the leaving tolerance 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... | |
| DataArray< VarStatus > | oldBasisStatusRows |
| stored stable basis met before a simplex pivot (used to warm start the solver) More... | |
| DataArray< VarStatus > | oldBasisStatusCols |
| They don't have setters because only the internal simplex method is meant to fill them. More... | |
| bool | solvingForBoosted |
| is this solver involved in a higher precision solving scheme? More... | |
| int | storeBasisSimplexFreq |
| number of simplex pivots -1 to perform before storing stable basis 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... | |
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 58 of file spxbasis.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 172 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 125 of file spxsolver.h.
| enum SolutionPolish |
objective for solution polishing
Definition at line 234 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_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 210 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 144 of file spxsolver.h.
| enum VarStatus |
Definition at line 197 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 1844 of file spxsolver.h.
| SPxBasisBase<R>& basis | ( | ) |
Definition at line 1849 of file spxsolver.h.
|
protected |
converts basis status to VarStatus
| int boundFlips | ( | ) | const |
get number of bound flips.
Definition at line 2172 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< BP >::changeBounds().
|
virtual |
Reimplemented from SPxLPBase< R >.
|
virtual |
Reimplemented from SPxLPBase< R >.
Definition at line 1086 of file spxsolver.h.
|
virtual |
Reimplemented from SPxLPBase< R >.
|
virtual |
Reimplemented from SPxLPBase< R >.
Definition at line 1138 of file spxsolver.h.
|
virtual |
Reimplemented from SPxLPBase< R >.
|
virtual |
Reimplemented from SPxLPBase< R >.
Definition at line 1146 of file spxsolver.h.
|
virtual |
Reimplemented from SPxLPBase< R >.
Referenced by SPxSolverBase< BP >::changeBounds().
|
virtual |
Reimplemented from SPxLPBase< R >.
|
virtual |
Reimplemented from SPxLPBase< R >.
Definition at line 1099 of file spxsolver.h.
|
virtual |
Referenced by SPxSolverBase< BP >::changeBounds().
|
virtual |
Reimplemented from SPxLPBase< R >.
|
virtual |
Reimplemented from SPxLPBase< R >.
|
virtual |
Reimplemented from SPxLPBase< R >.
Definition at line 1063 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 1035 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 1025 of file spxsolver.h.
|
virtual |
Reimplemented from SPxLPBase< R >.
|
virtual |
Reimplemented from SPxLPBase< R >.
|
virtual |
Reimplemented from SPxLPBase< R >.
Definition at line 1122 of file spxsolver.h.
|
virtual |
Reimplemented from SPxLPBase< R >.
|
virtual |
Reimplemented from SPxLPBase< R >.
|
virtual |
Reimplemented from SPxLPBase< R >.
Definition at line 1111 of file spxsolver.h.
|
virtual |
|
virtual |
Reimplemented from SPxLPBase< R >.
|
virtual |
Reimplemented from SPxLPBase< R >.
Definition at line 1130 of file spxsolver.h.
|
virtual |
Reimplemented from SPxLPBase< R >.
|
virtual |
Reimplemented from SPxLPBase< R >.
|
virtual |
Reimplemented from SPxLPBase< R >.
Definition at line 1045 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 1075 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 1050 of file spxsolver.h.
|
protectedvirtual |
| int coDim | ( | ) | const |
codimension.
Definition at line 1163 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 1200 of file spxsolver.h.
Referenced by SPxSolverBase< BP >::id().
| SPxColId colId | ( | int | i | ) | const |
ColId of i 'th column.
Definition at line 2318 of file spxsolver.h.
| const LPColSet& cols | ( | ) | const |
return const lp's cols if available.
Definition at line 2261 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 1494 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 1481 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 1548 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 1340 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 1284 of file spxsolver.h.
| const SVectorBase<R>& coVector | ( | const SPxRowId & | rid | ) | const |
Definition at line 1289 of file spxsolver.h.
| const SVectorBase<R>& coVector | ( | const SPxColId & | cid | ) | const |
Definition at line 1297 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 1311 of file spxsolver.h.
| Real cumulativeTime | ( | ) | const |
cumulative time spent in all calls to method solve().
Definition at line 2243 of file spxsolver.h.
| R delta | ( | ) | const |
guaranteed primal and dual bound violation for optimal solution, returning the maximum of floatingPointFeastol() and floatingPointOpttol().
Definition at line 863 of file spxsolver.h.
| int dim | ( | ) | const |
dimension of basis matrix.
Definition at line 1158 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 2178 of file spxsolver.h.
| int dualIterations | ( | ) |
return number of iterations done with primal algorithm
Definition at line 2215 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 832 of file spxsolver.h.
|
protectedvirtual |
Get pointer to the id 'th vector.
Definition at line 1979 of file spxsolver.h.
| R epsilon | ( | ) | const |
values \(|x| < \epsilon\) are considered to be 0.
if you want another value for epsilon, use Tolerances::setEpsilon().
Definition at line 827 of file spxsolver.h.
|
virtual |
Factorize basis matrix.
| SPxStatusException | if loaded matrix is singular |
Reimplemented from SPxBasisBase< R >.
| void forceRecompNonbasicValue | ( | ) |
Definition at line 713 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 1419 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 1468 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 1406 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 968 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 2123 of file spxsolver.h.
| R getDegeneracyLevel | ( | VectorBase< R > | degenvec | ) |
get level of dual degeneracy
| int getDisplayFreq | ( | ) |
get display frequency
Definition at line 898 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 2278 of file spxsolver.h.
| void getLower | ( | VectorBase< R > & | p_low | ) | const |
copy lower bound VectorBase<R> to p_low.
Definition at line 2267 of file spxsolver.h.
| int getMaxIters | ( | ) |
the maximum number of iterations
Definition at line 2249 of file spxsolver.h.
| Real getMaxTime | ( | ) |
the maximum runtime
Definition at line 2237 of file spxsolver.h.
| void getNdualNorms | ( | int & | nnormsRow, |
| int & | nnormsCol | ||
| ) | const |
get number of dual norms
Definition at line 924 of file spxsolver.h.
Definition at line 918 of file spxsolver.h.
|
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 2284 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 693 of file spxsolver.h.
| Timer::TYPE getTiming | ( | ) |
set timing type
Definition at line 881 of file spxsolver.h.
| void getUpper | ( | VectorBase< R > & | p_up | ) | const |
copy upper bound VectorBase<R> to p_up.
Definition at line 2272 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 1181 of file spxsolver.h.
|
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 1346 of file spxsolver.h.
| bool isBasic | ( | const SPxId & | p_id | ) | const |
is the p_id 'th vector basic ?
Definition at line 1352 of file spxsolver.h.
| bool isBasic | ( | const SPxRowId & | rid | ) | const |
is the rid 'th vector basic ?
Definition at line 1361 of file spxsolver.h.
| bool isBasic | ( | const SPxColId & | cid | ) | const |
is the cid 'th vector basic ?
Definition at line 1367 of file spxsolver.h.
| bool isBasic | ( | int | i | ) | const |
is the i 'th vector basic ?
Definition at line 1385 of file spxsolver.h.
check a given basis for validity.
| bool isCoBasic | ( | int | i | ) | const |
is the i 'th covector basic ?
Definition at line 1391 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 1227 of file spxsolver.h.
| bool isColBasic | ( | int | i | ) | const |
is the i 'th column vector basic ?
Definition at line 1379 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 1218 of file spxsolver.h.
Referenced by SPxSolverBase< BP >::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 1933 of file spxsolver.h.
| bool isRowBasic | ( | int | i | ) | const |
is the i 'th row vector basic ?
Definition at line 1373 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 2202 of file spxsolver.h.
| const VectorBase<R>& lbBound | ( | ) | const |
lower bound for fVec.
Definition at line 1442 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 1455 of file spxsolver.h.
| const VectorBase<R>& lcBound | ( | ) | const |
Definition at line 1521 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 1535 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 840 of file spxsolver.h.
|
virtual |
set a start basis.
|
virtual |
copy LP.
|
private |
|
private |
| const VectorBase<R>& lpBound | ( | ) | const |
Definition at line 1587 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 1601 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 952 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 957 of file spxsolver.h.
|
virtual |
get objective value of current solution.
Definition at line 2086 of file spxsolver.h.
| SPxSolverBase<R>& operator= | ( | const SPxSolverBase< R > & | base | ) |
assignment operator
assignment operator and copy constructor
| bool 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 2221 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 1854 of file spxsolver.h.
| Pricing pricing | ( | ) | const |
return current Pricing.
Definition at line 557 of file spxsolver.h.
| int primalDegeneratePivots | ( | ) |
get number of primal degenerate pivots
Definition at line 2184 of file spxsolver.h.
| int primalIterations | ( | ) |
return number of iterations done with primal algorithm
Definition at line 2208 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 1561 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 1864 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 545 of file spxsolver.h.
|
protected |
resets clock average statistics
| void resetCumulativeTime | ( | ) |
reset cumulative time counter to zero.
Definition at line 2166 of file spxsolver.h.
| SPxRowId rowId | ( | int | i | ) | const |
RowId of i 'th inequality.
Mapping between numbers and Ids
Definition at line 2313 of file spxsolver.h.
| const LPRowSetBase<R>& rows | ( | ) | const |
return const lp's rows if available.
Definition at line 2255 of file spxsolver.h.
| void scaleEntertol | ( | R | d | ) |
scale the entering tolerance
Definition at line 848 of file spxsolver.h.
| void scaleLeavetol | ( | R | d | ) |
scale the leaving tolerance
Definition at line 853 of file spxsolver.h.
| void scaleTolerances | ( | R | d | ) |
Definition at line 857 of file spxsolver.h.
optimization sense.
Definition at line 2290 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 2135 of file spxsolver.h.
| void setDisplayFreq | ( | int | freq | ) |
set display frequency
Definition at line 892 of file spxsolver.h.
|
private |
|
protected |
| bool setDualNorms | ( | int | nnormsRow, |
| int | nnormsCol, | ||
| R * | norms | ||
| ) |
set dual norms
|
protected |
|
protected |
|
protected |
|
protectedvirtual |
| void setFillFactor | ( | R | f | ) |
set refactor threshold for fill-in in current factor update compared to fill-in in last factorization
Definition at line 521 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 527 of file spxsolver.h.
| void setMetricInformation | ( | int | type | ) |
print basis metric within the usual output
Definition at line 904 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 515 of file spxsolver.h.
| void setOutstream | ( | SPxOut & | newOutstream | ) |
Definition at line 487 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 687 of file spxsolver.h.
| void setSolverStatus | ( | typename SPxSolverBase< R >::Status | stat | ) |
setting the solver status external from the solve loop.
Definition at line 2144 of file spxsolver.h.
| void setSolvingForBoosted | ( | bool | value | ) |
Definition at line 930 of file spxsolver.h.
| void setSparsePricingFactor | ( | R | fac | ) |
Definition at line 910 of file spxsolver.h.
|
virtual |
setup starting basis generator to use. If destroy is true, starter will be freed in destructor.
| void setStoreBasisFreqForBoosting | ( | int | freq | ) |
Definition at line 936 of file spxsolver.h.
|
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 870 of file spxsolver.h.
|
virtual |
set the _tolerances member variable
Reimplemented from SPxLPBase< R >.
Definition at line 494 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 1805 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 1817 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 1777 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 1791 of file spxsolver.h.
|
protectedvirtual |
|
virtual |
total current shift amount.
Definition at line 1710 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 1667 of file spxsolver.h.
| void shiftLCbound | ( | int | i, |
| R | to | ||
| ) |
shift i 'th lcBound to to.
Definition at line 1699 of file spxsolver.h.
| void shiftLPbound | ( | int | i, |
| R | to | ||
| ) |
shift i 'th lpBound to to.
Definition at line 1683 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 1659 of file spxsolver.h.
| void shiftUCbound | ( | int | i, |
| R | to | ||
| ) |
shift i 'th ucBound to to.
Definition at line 1691 of file spxsolver.h.
| void shiftUPbound | ( | int | i, |
| R | to | ||
| ) |
shift i 'th upBound to to.
Definition at line 1675 of file spxsolver.h.
| const SLinSolver<R>* slinSolver | ( | ) | const |
return loaded SLinSolver.
Definition at line 1859 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.
| interrupt | can be set externally to interrupt the solve |
| polish | should solution polishing be considered |
| 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 563 of file spxsolver.h.
| std::string statistics | ( | ) | const |
returns statistical information in form of a string.
Definition at line 2296 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 540 of file spxsolver.h.
| R sumDualDegeneracy | ( | ) |
get the sum of dual degeneracy
Definition at line 2190 of file spxsolver.h.
| R sumPrimalDegeneracy | ( | ) |
get the sum of primal degeneracy
Definition at line 2196 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 1614 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 2227 of file spxsolver.h.
| const std::shared_ptr<Tolerances>& tolerances | ( | ) | const |
returns current tolerances
Definition at line 509 of file spxsolver.h.
| Type type | ( | ) | const |
return current Type.
Definition at line 551 of file spxsolver.h.
| const VectorBase<R>& ubBound | ( | ) | const |
upper bound for fVec.
Definition at line 1424 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 1437 of file spxsolver.h.
| const VectorBase<R>& ucBound | ( | ) | const |
Definition at line 1500 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 1514 of file spxsolver.h.
|
protectedvirtual |
|
protectedvirtual |
uninitialize data structures.
Definition at line 1942 of file spxsolver.h.
| const SVectorBase<R>& unitVector | ( | int | i | ) | const |
return i 'th unit vector.
Definition at line 1319 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 1566 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 1580 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 963 of file spxsolver.h.
|
virtual |
current objective value.
| SPxBasisBase<R>::Desc::Status varStatus | ( | int | i | ) | const |
Status of i 'th variable.
Definition at line 1334 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 1240 of file spxsolver.h.
| const SVectorBase<R>& vector | ( | const SPxRowId & | rid | ) | const |
Definition at line 1246 of file spxsolver.h.
| const SVectorBase<R>& vector | ( | const SPxColId & | cid | ) | const |
Definition at line 1254 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 1271 of file spxsolver.h.
| int version | ( | ) | const |
return the version of SPxSolverBase as number like 123 for 1.2.3
Definition at line 535 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 352 of file spxsolver.h.
|
protected |
number of performed bound flips
Definition at line 400 of file spxsolver.h.
|
protected |
absolute range of all bounds in the problem
Definition at line 414 of file spxsolver.h.
|
private |
when 2 systems are to be solved at a time; typically for speepest edge weights
Definition at line 291 of file spxsolver.h.
|
private |
when 2 systems are to be solved at a time; typically for speepest edge weights
Definition at line 293 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 295 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 297 of file spxsolver.h.
| VectorBase<R> coWeights |
store dual norms
Definition at line 468 of file spxsolver.h.
|
private |
Definition at line 321 of file spxsolver.h.
|
private |
Definition at line 320 of file spxsolver.h.
|
protected |
the sum of the dual degeneracy percentage
Definition at line 408 of file spxsolver.h.
|
protected |
stores dual farkas proof in case of infeasibility
Definition at line 393 of file spxsolver.h.
|
protected |
rhs VectorBase<R> for computing the dual vector
Definition at line 350 of file spxsolver.h.
|
protected |
dual vector
Definition at line 351 of file spxsolver.h.
|
protected |
number of ENTER iterations
Definition at line 396 of file spxsolver.h.
|
protected |
the number of degenerate steps during the entering algorithm
Definition at line 403 of file spxsolver.h.
|
protected |
the number of degenerate candidates in the entering algorithm
Definition at line 405 of file spxsolver.h.
|
private |
factor to temporarily decrease the entering tolerance
Definition at line 274 of file spxsolver.h.
|
private |
true iff thepricer should be freed inside of object
Definition at line 299 of file spxsolver.h.
|
private |
true iff theratiotester should be freed inside of object
Definition at line 300 of file spxsolver.h.
|
private |
true iff thestarter should be freed inside of object
Definition at line 301 of file spxsolver.h.
|
private |
whether to perturb the entire problem or just the bounds relevant for the current pivot
Definition at line 333 of file spxsolver.h.
| bool hyperPricingEnter |
true if hyper sparse pricing is turned on in the entering Simplex
Definition at line 460 of file spxsolver.h.
| bool hyperPricingLeave |
true if hyper sparse pricing is turned on in the leaving Simplex
Definition at line 459 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 437 of file spxsolver.h.
| DIdxSet infeasibilitiesCo |
For the entering Simplex algorithm these vectors contains the indices of infeasible basic variables.
Definition at line 440 of file spxsolver.h.
|
private |
true, if all vectors are setup.
Definition at line 280 of file spxsolver.h.
|
private |
Definition at line 314 of file spxsolver.h.
|
private |
Definition at line 313 of file spxsolver.h.
|
private |
Definition at line 315 of file spxsolver.h.
|
private |
Definition at line 307 of file spxsolver.h.
|
private |
Definition at line 306 of file spxsolver.h.
|
private |
Definition at line 308 of file spxsolver.h.
| DataArray<int> integerVariables |
supplementary variable information, 0: continous variable, 1: integer variable
Definition at line 484 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 451 of file spxsolver.h.
| DataArray<int> isInfeasibleCo |
0: index not violated, 1: index violated, 2: index violated and among candidate list
Definition at line 453 of file spxsolver.h.
|
private |
for forcing feasibility.
Definition at line 277 of file spxsolver.h.
|
protected |
number of LEAVE iterations
Definition at line 395 of file spxsolver.h.
|
protected |
the number of degenerate steps during the leaving algorithm
Definition at line 404 of file spxsolver.h.
|
protected |
the number of degenerate candidates in the leaving algorithm
Definition at line 406 of file spxsolver.h.
|
private |
factor to temporarily decrease the leaving tolerance
Definition at line 275 of file spxsolver.h.
|
private |
maximum steps before cycling is detected.
Definition at line 278 of file spxsolver.h.
|
private |
nonbasic part of current objective value
Definition at line 263 of file spxsolver.h.
|
private |
true, if the stored objValue is up to date
Definition at line 264 of file spxsolver.h.
|
private |
actual number of degenerate steps so far.
Definition at line 279 of file spxsolver.h.
|
private |
number of violations of current solution
Definition at line 272 of file spxsolver.h.
|
private |
maximal feasibility violation of current solution
Definition at line 266 of file spxsolver.h.
|
private |
maximal feasibility violation of current solution in coDim
Definition at line 270 of file spxsolver.h.
|
private |
true, if the stored violation in coDim is up to date
Definition at line 271 of file spxsolver.h.
|
private |
true, if the stored violation is up to date
Definition at line 267 of file spxsolver.h.
|
private |
status of algorithm.
Definition at line 261 of file spxsolver.h.
|
private |
maximum allowed iterations.
Definition at line 256 of file spxsolver.h.
|
private |
maximum allowed time.
Definition at line 257 of file spxsolver.h.
| int multColwiseCalls |
number of products, columnwise multiplication
Definition at line 478 of file spxsolver.h.
| int multFullCalls |
number of products ignoring sparsity
Definition at line 477 of file spxsolver.h.
| int multSparseCalls |
number of products exploiting sparsity
Definition at line 476 of file spxsolver.h.
| Timer* multTimeColwise |
time spent in setupPupdate(), columnwise multiplication
Definition at line 474 of file spxsolver.h.
| Timer* multTimeFull |
time spent in setupPupdate() ignoring sparsity
Definition at line 473 of file spxsolver.h.
| Timer* multTimeSparse |
time spent in setupPupdate() exploiting sparsity
Definition at line 472 of file spxsolver.h.
| Timer* multTimeUnsetup |
time spent in setupPupdate() w/o sparsity information
Definition at line 475 of file spxsolver.h.
| int multUnsetupCalls |
number of products w/o sparsity information
Definition at line 479 of file spxsolver.h.
|
private |
Definition at line 259 of file spxsolver.h.
|
private |
remaining number of times the clock can be safely skipped
Definition at line 258 of file spxsolver.h.
|
private |
< the number of calls to the method isTimeLimitReached()
objective value limit.
Definition at line 260 of file spxsolver.h.
|
protected |
absolute range of all objective coefficients in the problem
Definition at line 416 of file spxsolver.h.
They don't have setters because only the internal simplex method is meant to fill them.
Definition at line 326 of file spxsolver.h.
stored stable basis met before a simplex pivot (used to warm start the solver)
Definition at line 324 of file spxsolver.h.
|
protected |
number of solution polishing iterations
Definition at line 398 of file spxsolver.h.
|
private |
objective of solution polishing
Definition at line 252 of file spxsolver.h.
|
protected |
number of primal iterations
Definition at line 397 of file spxsolver.h.
|
protected |
the sum of the primal degeneracy percentage
Definition at line 407 of file spxsolver.h.
|
protected |
stores primal ray in case of unboundedness
Definition at line 392 of file spxsolver.h.
|
protected |
rhs VectorBase<R> for computing the primal vector
Definition at line 348 of file spxsolver.h.
|
protected |
primal vector
Definition at line 349 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 335 of file spxsolver.h.
| Random random |
The random number generator used throughout the whole computation. Its seed can be modified.
Definition at line 432 of file spxsolver.h.
|
private |
flag to perform clean up step to reduce numerical errors only once
Definition at line 318 of file spxsolver.h.
| int remainingRoundsEnter |
Definition at line 463 of file spxsolver.h.
| int remainingRoundsEnterCo |
Definition at line 464 of file spxsolver.h.
| int remainingRoundsLeave |
number of dense rounds/refactorizations until sparsePricing is enabled again
Definition at line 462 of file spxsolver.h.
|
protected |
absolute range of all side in the problem
Definition at line 415 of file spxsolver.h.
|
private |
when 2 systems are to be solved at a time; typically for speepest edge weights
Definition at line 283 of file spxsolver.h.
|
private |
when 2 systems are to be solved at a time; typically for speepest edge weights
Definition at line 285 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 287 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 289 of file spxsolver.h.
|
private |
is this solver involved in a higher precision solving scheme?
Definition at line 329 of file spxsolver.h.
| bool sparsePricingEnter |
true if sparsePricing is turned on in the entering Simplex for slack variables
Definition at line 457 of file spxsolver.h.
| bool sparsePricingEnterCo |
true if sparsePricing is turned on in the entering Simplex
Definition at line 458 of file spxsolver.h.
|
private |
enable sparse pricing when viols < factor * dim()
Definition at line 322 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 456 of file spxsolver.h.
|
private |
Definition at line 108 of file spxsolver.h.
|
private |
Definition at line 107 of file spxsolver.h.
| SPxOut* spxout |
message handler
Definition at line 481 of file spxsolver.h.
|
private |
number of simplex pivots -1 to perform before storing stable basis
Definition at line 330 of file spxsolver.h.
|
protected |
Lower bound for covars.
Definition at line 386 of file spxsolver.h.
|
protected |
Definition at line 373 of file spxsolver.h.
|
protected |
Definition at line 374 of file spxsolver.h.
|
protected |
Definition at line 389 of file spxsolver.h.
|
protected |
Upper bound for covars.
Definition at line 385 of file spxsolver.h.
|
protected |
the LP coVectors according to representation
Definition at line 346 of file spxsolver.h.
|
protected |
column pricing vector
Definition at line 379 of file spxsolver.h.
|
private |
cumulative time spent in all calls to method solve()
Definition at line 255 of file spxsolver.h.
|
protected |
The values of the rhs corresponding to the current basis.
Definition at line 368 of file spxsolver.h.
|
protected |
The values of all basis variables.
Definition at line 370 of file spxsolver.h.
|
protected |
Lower Basic Feasibility bound.
Definition at line 365 of file spxsolver.h.
|
protected |
Lower bound for vars.
Definition at line 384 of file spxsolver.h.
|
protected |
Lower Column Feasibility bound.
Definition at line 357 of file spxsolver.h.
|
protected |
Lower Row Feasibility bound.
Definition at line 355 of file spxsolver.h.
|
protected |
Definition at line 410 of file spxsolver.h.
|
private |
full or partial pricing.
Definition at line 250 of file spxsolver.h.
|
protected |
The pricing VectorBase<R>
Definition at line 376 of file spxsolver.h.
|
protected |
Definition at line 411 of file spxsolver.h.
|
private |
row or column representation.
Definition at line 251 of file spxsolver.h.
|
protected |
row pricing vector
Definition at line 378 of file spxsolver.h.
|
private |
sum of all shifts applied to any bound.
Definition at line 276 of file spxsolver.h.
|
protected |
Definition at line 412 of file spxsolver.h.
|
protected |
Definition at line 390 of file spxsolver.h.
|
private |
time spent in last call to method solve()
Definition at line 253 of file spxsolver.h.
|
private |
entering or leaving algortihm.
Definition at line 249 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 364 of file spxsolver.h.
|
protected |
Upper bound for vars.
Definition at line 383 of file spxsolver.h.
|
protected |
Upper Column Feasibility bound.
Definition at line 356 of file spxsolver.h.
|
protected |
Upper Row Feasibility bound.
Definition at line 354 of file spxsolver.h.
|
protected |
the LP vectors according to representation
Definition at line 345 of file spxsolver.h.
|
private |
type of timer (user or wallclock)
Definition at line 254 of file spxsolver.h.
|
protected |
total number of bound flips
Definition at line 401 of file spxsolver.h.
|
protected |
array of unit vectors
Definition at line 344 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 443 of file spxsolver.h.
| DIdxSet updateViolsCo |
Definition at line 444 of file spxsolver.h.
| VectorBase<R> weights |
| bool weightsAreSetup |
are the dual norms already set up?
Definition at line 469 of file spxsolver.h.