Loading...
Searching...
No Matches
SPxBasisBase< R > Class Template Reference Simplex basis. More...
Inheritance diagram for SPxBasisBase< R >:
![]()
Detailed Descriptiontemplate<class R> class soplex::SPxBasisBase< R > Simplex basis. Consider the linear program as provided from class SPxLP: \[ \begin{array}{rl} \hbox{max} & c^T x \\ \hbox{s.t.} & l_r \le Ax \le u_r \\ & l_c \le x \le u_c \end{array} \] where \(c, l_c, u_c, x \in {\bf R}^n\), \(l_r, u_r \in {\bf R}^m\) and \(A \in {\bf R}^{m \times n}\). Solving this LP with the simplex algorithm requires the definition of a basis. Such can be defined as a set of column vectors or a set of row vectors building a non-singular matrix. We will refer to the first case as the columnwise representation and the latter case will be called the rowwise representation. In both cases, a basis is a set of vectors forming a non-singular matrix. The dimension of the vectors is referred to as the basis' dimension, whereas the number of vectors belonging to the LP is called the basis' codimension. Class SPxBasisBase is designed to represent a generic simplex basis, suitable for both representations. At any time the representation can be changed by calling method setRep(). Class SPxBasisBase provides methods for solving linear systems with the basis matrix. However, SPxBasisBase does not provide a linear solver by its own. Instead, a SLinSolver object must be loaded to a SPxBasisBase which will be called for solving linear systems. Definition at line 67 of file spxlpbase.h. Member Enumeration Documentation◆ SPxStatus
template<class R >
basis status. Each SPxBasisBase is assigned a status flag, which can take on of the above values. Definition at line 101 of file spxbasis.h. Constructor & Destructor Documentation◆ SPxBasisBase() [1/2]
template<class R >
default constructor. ◆ SPxBasisBase() [2/2]
template<class R >
copy constructor ◆ ~SPxBasisBase()
template<class R >
destructor. Member Function Documentation◆ addedCols()
template<class R >
inform SPxBasisBase that ◆ addedRows()
template<class R >
inform SPxBasisBase, that ◆ baseId() [1/2]
template<class R >
Definition at line 513 of file spxbasis.h. References SPxBasisBase< R >::theBaseId. ◆ baseId() [2/2]
template<class R >
returns the Id of the Definition at line 518 of file spxbasis.h. References SPxBasisBase< R >::theBaseId. ◆ baseVec()
template<class R >
returns the Definition at line 524 of file spxbasis.h. References SPxBasisBase< R >::matrix, and SPxBasisBase< R >::matrixIsSetup. ◆ change()
template<class R >
performs basis update. Changes the
The basis descriptor is not modified, since factor() cannot know about how to set up the status of the involved variables correctly. A vector ◆ changedCol()
template<class R >
inform SPxBasisBase that a column had been changed. ◆ changedElement()
template<class R >
inform SPxBasisBase that a matrix entry had been changed. ◆ changedRow()
template<class R >
inform SPxBasisBase that a row had been changed. ◆ condition()
template<class R >
Referenced by SPxBasisBase< R >::getEstimatedCondition(), and SPxBasisBase< R >::getExactCondition(). ◆ coSolve() [1/6]
template<class R >
Sparse version of coSolve. Definition at line 755 of file spxbasis.h. References SSVectorBase< R >::clear(), SPxBasisBase< R >::factor, SPxBasisBase< R >::factorize(), SPxBasisBase< R >::factorized, and SVectorBase< R >::size(). ◆ coSolve() [2/6]
template<class R >
Sparse version of solving two systems in one call. Definition at line 778 of file spxbasis.h. References SPxBasisBase< R >::factor, SPxBasisBase< R >::factorize(), and SPxBasisBase< R >::factorized. ◆ coSolve() [3/6]
template<class R >
Sparse version of solving three systems in one call. Definition at line 796 of file spxbasis.h. References SPxBasisBase< R >::factor, SPxBasisBase< R >::factorize(), and SPxBasisBase< R >::factorized. ◆ coSolve() [4/6]
template<class R >
solves two systems in one call. Definition at line 769 of file spxbasis.h. References SPxBasisBase< R >::factor, SPxBasisBase< R >::factorize(), and SPxBasisBase< R >::factorized. ◆ coSolve() [5/6]
template<class R >
solves three systems in one call. May be improved by using just one pass through the basis. Definition at line 787 of file spxbasis.h. References SPxBasisBase< R >::factor, SPxBasisBase< R >::factorize(), and SPxBasisBase< R >::factorized. ◆ coSolve() [6/6]
template<class R >
Cosolves linear system with basis matrix. Depending on the representation, for a SPxBasisBase B, B.coSolve(x) computes
Both can be seen uniformly as solving a linear system with the basis matrix Definition at line 741 of file spxbasis.h. References VectorBase< R >::clear(), VectorBase< R >::dim(), SPxBasisBase< R >::factor, SPxBasisBase< R >::factorize(), and SPxBasisBase< R >::factorized. ◆ desc() [1/2]
template<class R >
returns current basis Descriptor. Definition at line 478 of file spxbasis.h. References SPxBasisBase< R >::thedesc. ◆ desc() [2/2]
template<class R >
Definition at line 473 of file spxbasis.h. References SPxBasisBase< R >::thedesc. Referenced by SPxSolverBase< R >::covarStatus(), SPxSolverBase< R >::isBasic(), SPxSolverBase< R >::isBasic(), SPxSolverBase< R >::isBasic(), SPxSolverBase< R >::isCoBasic(), SPxSolverBase< R >::isColBasic(), SPxSolverBase< R >::isRowBasic(), and SPxSolverBase< R >::varStatus(). ◆ dualColStatus()
template<class R >
dual Status for the ◆ dualRowStatus()
template<class R >
dual Status for the ◆ dualStatus() [1/3]
template<class R >
dual Status for the column variable with ID Referenced by SPxBasisBase< R >::dualStatus(). ◆ dualStatus() [2/3]
template<class R >
dual Status for the variable with ID It is automatically detected, whether the Definition at line 500 of file spxbasis.h. References SPxBasisBase< R >::dualStatus(). ◆ dualStatus() [3/3]
template<class R >
dual Status for the row variable with ID ◆ dump()
template<class R >
output basis entries. ◆ factorize()
template<class R >
factorizes the basis matrix. Reimplemented in SPxSolverBase< R >, and SPxSolverBase< BP >. Referenced by SPxBasisBase< R >::coSolve(), SPxBasisBase< R >::coSolve(), SPxBasisBase< R >::coSolve(), SPxBasisBase< R >::coSolve(), SPxBasisBase< R >::coSolve(), SPxBasisBase< R >::coSolve(), SPxBasisBase< R >::solve(), SPxBasisBase< R >::solve(), SPxBasisBase< R >::solve4update(), SPxBasisBase< R >::solve4update(), SPxBasisBase< R >::solve4update(), SPxBasisBase< R >::solve4update(), and SPxBasisBase< R >::solve4update(). ◆ getEstimatedCondition()
template<class R >
Definition at line 617 of file spxbasis.h. References SPxBasisBase< R >::condition(). ◆ getExactCondition()
template<class R >
Definition at line 623 of file spxbasis.h. References SPxBasisBase< R >::condition(). ◆ getMatrixMetric()
template<class R >
compute one of several matrix metrics based on the diagonal of the LU factorization type = 0: max/min ratio type = 1: trace of U (sum of diagonal elements) type = 2: determinant (product of diagonal elements) ◆ getMaxUpdates()
template<class R >
returns maximum number of updates before a refactorization is performed Definition at line 467 of file spxbasis.h. References SPxBasisBase< R >::maxUpdates. ◆ getTotalUpdateCount()
template<class R >
number of updates performed Definition at line 938 of file spxbasis.h. References SPxBasisBase< R >::totalUpdateCount. Referenced by SPxBasisBase< R >::statistics(). ◆ getTotalUpdateTime()
template<class R >
time spent in updates Definition at line 933 of file spxbasis.h. References SPxBasisBase< R >::theTime, and Timer::time(). Referenced by SPxBasisBase< R >::statistics(). ◆ invalidate()
template<class R >
invalidates actual basis. This method makes the basis matrix and vectors invalid. The basis will be reinitialized if needed. Referenced by SPxBasisBase< R >::setStatus(). ◆ isConsistent()
template<class R >
consistency check. ◆ isDescValid()
template<class R >
checks if a Descriptor is valid for the current LP w.r.t. its bounds ◆ iteration()
template<class R >
returns number of basis changes since last load(). Definition at line 555 of file spxbasis.h. References SPxBasisBase< R >::iterCount. ◆ lastDegenCheck()
template<class R >
returns the number of iterations since the last degeneracy check Definition at line 567 of file spxbasis.h. References SPxBasisBase< R >::iterDegenCheck. ◆ lastEntered()
template<class R >
returns SPxId of last VectorBase<R> included to the basis. Definition at line 531 of file spxbasis.h. References SPxBasisBase< R >::lastin. ◆ lastIndex()
template<class R >
returns index in basis where last update was done. Definition at line 543 of file spxbasis.h. References SPxBasisBase< R >::lastidx. ◆ lastLeft()
template<class R >
returns SPxId of last vector that left the basis. Definition at line 537 of file spxbasis.h. References SPxBasisBase< R >::lastout. ◆ lastUpdate()
template<class R >
returns number of basis changes since last refactorization. Definition at line 549 of file spxbasis.h. References SPxBasisBase< R >::updateCount. ◆ load()
template<class R >
loads the LP This involves resetting all counters to 0 and setting up a regular default basis consisting of slacks, artificial variables or bounds. ◆ loadBasisSolver()
template<class R >
sets up linear solver to use. If destroy is true, solver will be freed inside this object, e.g. in the destructor. ◆ loadDesc()
template<class R >
sets up basis. Loads a Descriptor to the basis and sets up the basis matrix and all vectors accordingly. The Descriptor must have the same number of rows and columns as the currently loaded LP. ◆ loadMatrixVecs()
template<class R >
◆ multBaseWith() [1/2]
template<class R >
Basis-vector product. ◆ multBaseWith() [2/2]
template<class R >
Basis-vector product. Depending on the representation, for an SPxBasisBase B, B.multBaseWith(x) computes
Both can be seen uniformly as multiplying the basis matrix ◆ multWithBase() [1/2]
template<class R >
VectorBase<R>-basis product. ◆ multWithBase() [2/2]
template<class R >
Vector-basis product. Depending on the representation, for a SPxBasisBase B, B.multWithBase(x) computes
Both can be seen uniformly as multiplying the basis matrix ◆ operator=()
template<class R >
assignment operator ◆ prevIteration()
template<class R >
returns the number of iterations prior to the last break in execution Definition at line 561 of file spxbasis.h. References SPxBasisBase< R >::lastIterCount. ◆ printMatrix()
template<class R >
◆ printMatrixMTX()
template<class R >
Prints current basis matrix to a file using the MatrixMarket format: row col value The filename is basis/basis[number].mtx where number is a parameter. ◆ readBasis()
template<class R >
Load basis from ◆ reDim()
template<class R >
resizes internal arrays. When a new LP is loaded, the basis matrix and vectors become invalid and possibly also of the wrong dimension. Hence, after loading an LP, reDim() is called to reset all arrays etc. accoriding to the dimensions of the loaded LP. ◆ removedCol()
template<class R >
inform SPxBasisBase that column ◆ removedCols()
template<class R >
inform SPxBasisBase that columns in ◆ removedRow()
template<class R >
inform SPxBasisBase that row ◆ removedRows()
template<class R >
inform SPxBasisBase that rows in ◆ restoreInitialBasis()
template<class R >
Restores initial basis. This method changes the basis to that present just after loading the LP (see addedRows() and addedCols()). This may be necessary if a row or a column is changed, since then the current basis may become singular. ◆ setMaxUpdates()
template<class R >
change maximum number of iterations until a refactorization is performed Definition at line 460 of file spxbasis.h. References SPxBasisBase< R >::maxUpdates. ◆ setOutstream()
template<class R >
Definition at line 957 of file spxbasis.h. References SPxBasisBase< R >::spxout. ◆ setRep()
template<class R >
sets descriptor representation according to loaded LP. ◆ setStatus()
template<class R >
sets basis SPxStatus to Definition at line 443 of file spxbasis.h. References SPxOut::debug(), SPxBasisBase< R >::invalidate(), SPxBasisBase< R >::NO_PROBLEM, and SPxBasisBase< R >::thestatus. Referenced by SPxSolverBase< R >::setBasisStatus(), and SPxBasisBase< R >::unLoad(). ◆ solve() [1/2]
template<class R >
Definition at line 655 of file spxbasis.h. References SSVectorBase< R >::clear(), SPxBasisBase< R >::factor, SPxBasisBase< R >::factorize(), SPxBasisBase< R >::factorized, and SVectorBase< R >::size(). ◆ solve() [2/2]
template<class R >
Definition at line 641 of file spxbasis.h. References VectorBase< R >::clear(), VectorBase< R >::dim(), SPxBasisBase< R >::factor, SPxBasisBase< R >::factorize(), and SPxBasisBase< R >::factorized. ◆ solve4update() [1/5]
template<class R >
solves linear system with basis matrix. Depending on the representation, for a SPxBasisBase B, B.solve(x) computes
Both can be seen uniformly as solving a linear system with the basis matrix Definition at line 678 of file spxbasis.h. References SSVectorBase< R >::clear(), SPxBasisBase< R >::factor, SPxBasisBase< R >::factorize(), SPxBasisBase< R >::factorized, and SVectorBase< R >::size(). ◆ solve4update() [2/5]
template<class R >
solves two systems in one call using only sparse data structures Definition at line 701 of file spxbasis.h. References SPxBasisBase< R >::factor, SPxBasisBase< R >::factorize(), and SPxBasisBase< R >::factorized. ◆ solve4update() [3/5]
template<class R >
solves three systems in one call using only sparse data structures Definition at line 721 of file spxbasis.h. References SPxBasisBase< R >::factor, SPxBasisBase< R >::factorize(), SPxBasisBase< R >::factorized, and SSVectorBase< R >::isSetup(). ◆ solve4update() [4/5]
template<class R >
solves two systems in one call. Definition at line 692 of file spxbasis.h. References SPxBasisBase< R >::factor, SPxBasisBase< R >::factorize(), and SPxBasisBase< R >::factorized. ◆ solve4update() [5/5]
template<class R >
solves three systems in one call. Definition at line 710 of file spxbasis.h. References SPxBasisBase< R >::factor, SPxBasisBase< R >::factorize(), SPxBasisBase< R >::factorized, and SSVectorBase< R >::isSetup(). ◆ solver()
template<class R >
returns loaded solver. Definition at line 573 of file spxbasis.h. References SPxBasisBase< R >::theLP. ◆ stability()
template<class R >
returns the stability of the basis matrix. Definition at line 636 of file spxbasis.h. References SPxBasisBase< R >::factor. ◆ statistics()
template<class R >
returns statistical information in form of a string. Definition at line 944 of file spxbasis.h. References SPxBasisBase< R >::factor, SPxBasisBase< R >::getTotalUpdateCount(), and SPxBasisBase< R >::getTotalUpdateTime(). ◆ status()
template<class R >
returns current SPxStatus. Definition at line 437 of file spxbasis.h. References SPxBasisBase< R >::thestatus. Referenced by SPxSolverBase< R >::getBasisStatus(). ◆ unLoad()
template<class R >
unloads the LP from the basis. Definition at line 907 of file spxbasis.h. References SPxBasisBase< R >::NO_PROBLEM, SPxBasisBase< R >::setStatus(), and SPxBasisBase< R >::theLP. ◆ writeBasis()
template<class R >
Write basis to Member Data Documentation◆ factor
template<class R >
Definition at line 367 of file spxbasis.h. Referenced by SPxBasisBase< R >::coSolve(), SPxBasisBase< R >::coSolve(), SPxBasisBase< R >::coSolve(), SPxBasisBase< R >::coSolve(), SPxBasisBase< R >::coSolve(), SPxBasisBase< R >::coSolve(), SPxBasisBase< R >::solve(), SPxBasisBase< R >::solve(), SPxBasisBase< R >::solve4update(), SPxBasisBase< R >::solve4update(), SPxBasisBase< R >::solve4update(), SPxBasisBase< R >::solve4update(), SPxBasisBase< R >::solve4update(), SPxBasisBase< R >::stability(), and SPxBasisBase< R >::statistics(). ◆ factorized
template<class R >
Definition at line 369 of file spxbasis.h. Referenced by SPxBasisBase< R >::coSolve(), SPxBasisBase< R >::coSolve(), SPxBasisBase< R >::coSolve(), SPxBasisBase< R >::coSolve(), SPxBasisBase< R >::coSolve(), SPxBasisBase< R >::coSolve(), SPxBasisBase< R >::solve(), SPxBasisBase< R >::solve(), SPxBasisBase< R >::solve4update(), SPxBasisBase< R >::solve4update(), SPxBasisBase< R >::solve4update(), SPxBasisBase< R >::solve4update(), and SPxBasisBase< R >::solve4update(). ◆ fillFactor
template<class R >
allowed increase in relative fill before refactorization When the real relative fill is bigger than fillFactor times lastFill the Basis will be refactorized. Definition at line 391 of file spxbasis.h. ◆ freeSlinSolver
template<class R >
true iff factor should be freed inside of this object Definition at line 426 of file spxbasis.h. ◆ iterCount
template<class R >
number of calls to change() since last manipulation Definition at line 400 of file spxbasis.h. Referenced by SPxBasisBase< R >::iteration(). ◆ iterDegenCheck
template<class R >
number of calls to change() since last degeneracy check Definition at line 402 of file spxbasis.h. Referenced by SPxBasisBase< R >::lastDegenCheck(). ◆ lastFill
template<class R >
fill ratio that occured during last factorization Definition at line 407 of file spxbasis.h. ◆ lastidx
template<class R >
lastIndex(): basis index where last update was done Definition at line 415 of file spxbasis.h. Referenced by SPxBasisBase< R >::lastIndex(). ◆ lastin
template<class R >
lastEntered(): variable entered the base last Definition at line 413 of file spxbasis.h. Referenced by SPxBasisBase< R >::lastEntered(). ◆ lastIterCount
template<class R >
number of calls to change() before halting the simplex Definition at line 401 of file spxbasis.h. Referenced by SPxBasisBase< R >::prevIteration(). ◆ lastMem
template<class R >
memory needed after last fresh factorization Definition at line 406 of file spxbasis.h. ◆ lastNzCount
template<class R >
number of nonzeros in basis matrix after last fresh factorization Definition at line 408 of file spxbasis.h. ◆ lastout
template<class R >
lastLeft(): variable left the base last Definition at line 414 of file spxbasis.h. Referenced by SPxBasisBase< R >::lastLeft(). ◆ matrix
template<class R >
pointers to the vectors of the basis matrix. Definition at line 359 of file spxbasis.h. Referenced by SPxBasisBase< R >::baseVec(). ◆ matrixIsSetup
template<class R >
Definition at line 361 of file spxbasis.h. Referenced by SPxBasisBase< R >::baseVec(). ◆ maxUpdates
template<class R >
number of updates before refactorization. When a vector of the basis matrix is exchanged by a call to method change(), the LU factorization of the matrix is updated accordingly. However, after atmost maxUpdates updates of the factorization, it is recomputed in order to regain numerical stability and reduce fill in. Definition at line 378 of file spxbasis.h. Referenced by SPxBasisBase< R >::getMaxUpdates(), and SPxBasisBase< R >::setMaxUpdates(). ◆ memFactor
template<class R >
allowed total increase in memory consumption before refactorization Definition at line 394 of file spxbasis.h. ◆ minStab
template<class R >
minimum stability Definition at line 416 of file spxbasis.h. ◆ nonzeroFactor
template<class R >
allowed increase of nonzeros before refactorization. When the number of nonzeros in LU factorization exceeds nonzeroFactor times the number of nonzeros in B, the basis matrix is refactorized. Definition at line 385 of file spxbasis.h. ◆ nzCount
template<class R >
number of nonzeros in basis matrix Definition at line 405 of file spxbasis.h. ◆ spxout
template<class R >
message handler Definition at line 427 of file spxbasis.h. Referenced by SPxBasisBase< R >::setOutstream(). ◆ theBaseIdSPxIds of basic vectors. Definition at line 357 of file spxbasis.h. Referenced by SPxBasisBase< R >::baseId(), and SPxBasisBase< R >::baseId(). ◆ thedesc
template<class R >
the basis' Descriptor Definition at line 425 of file spxbasis.h. Referenced by SPxBasisBase< R >::desc(), and SPxBasisBase< R >::desc(). ◆ theLP
template<class R >
the LP For storing the basis matrix we keep two arrays: Array theBaseId contains the SPxIds of the basis vectors, and matrix the pointers to the vectors themselfes. Method loadMatrixVecs() serves for loading matrix according to the SPxIds stored in theBaseId. This method must be called whenever the VectorBase<R> pointers may have changed due to manipulations of the LP. Definition at line 355 of file spxbasis.h. Referenced by SPxBasisBase< R >::solver(), and SPxBasisBase< R >::unLoad(). ◆ thestatus
template<class R >
current status of the basis. Definition at line 424 of file spxbasis.h. Referenced by SPxBasisBase< R >::setStatus(), and SPxBasisBase< R >::status(). ◆ theTime
template<class R >
time spent in updates Definition at line 410 of file spxbasis.h. Referenced by SPxBasisBase< R >::getTotalUpdateTime(). ◆ timerType
template<class R >
type of timer (user or wallclock) Definition at line 411 of file spxbasis.h. ◆ totalUpdateCount
template<class R >
number of updates Definition at line 404 of file spxbasis.h. Referenced by SPxBasisBase< R >::getTotalUpdateCount(). ◆ updateCount
template<class R >
number of calls to change() since last factorize() Definition at line 403 of file spxbasis.h. Referenced by SPxBasisBase< R >::lastUpdate().
|