Loading...
Searching...
No Matches
SPxBasisBase< R > Class Template Reference Simplex basis. More...
Inheritance diagram for SPxBasisBase< R >:
![]()
Detailed DescriptionSimplex 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 93 of file spxbasis.h. Member Enumeration Documentation◆ SPxStatusbasis 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]
default constructor. References SPxBasisBase< R >::spxout. ◆ SPxBasisBase() [2/2]
copy constructor ◆ ~SPxBasisBase()
destructor. Member Function Documentation◆ addedCols()inform SPxBasisBase that ◆ addedRows()inform SPxBasisBase, that ◆ baseId() [1/2]Definition at line 516 of file spxbasis.h. References SPxBasisBase< R >::theBaseId. ◆ baseId() [2/2]returns the Id of the Definition at line 521 of file spxbasis.h. References SPxBasisBase< R >::theBaseId. ◆ baseVec()returns the Definition at line 527 of file spxbasis.h. References SPxBasisBase< R >::matrix, and SPxBasisBase< R >::matrixIsSetup. ◆ change()
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()inform SPxBasisBase that a column had been changed. ◆ changedElement()inform SPxBasisBase that a matrix entry had been changed. ◆ changedRow()inform SPxBasisBase that a row had been changed. ◆ condition()Referenced by SPxBasisBase< R >::getEstimatedCondition(), and SPxBasisBase< R >::getExactCondition(). ◆ coSolve() [1/6]
Sparse version of coSolve. Definition at line 758 of file spxbasis.h. References DataArray< T >::clear(), SPxBasisBase< R >::factor, SPxBasisBase< R >::factorize(), SPxBasisBase< R >::factorized, and DataArray< T >::size(). ◆ coSolve() [2/6]
Sparse version of solving two systems in one call. Definition at line 781 of file spxbasis.h. References SPxBasisBase< R >::factor, SPxBasisBase< R >::factorize(), and SPxBasisBase< R >::factorized. ◆ coSolve() [3/6]
Sparse version of solving three systems in one call. Definition at line 799 of file spxbasis.h. References SPxBasisBase< R >::factor, SPxBasisBase< R >::factorize(), and SPxBasisBase< R >::factorized. ◆ coSolve() [4/6]
solves two systems in one call. Definition at line 772 of file spxbasis.h. References SPxBasisBase< R >::factor, SPxBasisBase< R >::factorize(), and SPxBasisBase< R >::factorized. ◆ coSolve() [5/6]
solves three systems in one call. May be improved by using just one pass through the basis. Definition at line 790 of file spxbasis.h. References SPxBasisBase< R >::factor, SPxBasisBase< R >::factorize(), and SPxBasisBase< R >::factorized. ◆ coSolve() [6/6]
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 744 of file spxbasis.h. References DataArray< T >::clear(), SPxBasisBase< R >::factor, SPxBasisBase< R >::factorize(), and SPxBasisBase< R >::factorized. ◆ desc() [1/2]returns current basis Descriptor. Definition at line 481 of file spxbasis.h. References SPxBasisBase< R >::thedesc. ◆ desc() [2/2]Definition at line 476 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()
dual Status for the ◆ dualRowStatus()
dual Status for the ◆ dualStatus() [1/3]
dual Status for the column variable with ID Referenced by SPxBasisBase< R >::dualStatus(). ◆ dualStatus() [2/3]
dual Status for the variable with ID It is automatically detected, whether the Definition at line 503 of file spxbasis.h. References SPxBasisBase< R >::dualStatus(). ◆ dualStatus() [3/3]
dual Status for the row variable with ID ◆ dump()◆ factorize()factorizes the basis matrix. Reimplemented in SPxSolverBase< R >. 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()Definition at line 620 of file spxbasis.h. References SPxBasisBase< R >::condition(). ◆ getExactCondition()Definition at line 626 of file spxbasis.h. References SPxBasisBase< R >::condition(). ◆ getMatrixMetric()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()returns maximum number of updates before a refactorization is performed Definition at line 470 of file spxbasis.h. References SPxBasisBase< R >::maxUpdates. ◆ getTotalUpdateCount()number of updates performed Definition at line 941 of file spxbasis.h. References SPxBasisBase< R >::totalUpdateCount. Referenced by SPxBasisBase< R >::statistics(). ◆ getTotalUpdateTime()time spent in updates Definition at line 936 of file spxbasis.h. References SPxBasisBase< R >::theTime, and Timer::time(). Referenced by SPxBasisBase< R >::statistics(). ◆ invalidate()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()◆ isDescValid()checks if a Descriptor is valid for the current LP w.r.t. its bounds ◆ iteration()returns number of basis changes since last load(). Definition at line 558 of file spxbasis.h. References SPxBasisBase< R >::iterCount. ◆ lastDegenCheck()returns the number of iterations since the last degeneracy check Definition at line 570 of file spxbasis.h. References SPxBasisBase< R >::iterDegenCheck. ◆ lastEntered()returns SPxId of last VectorBase<R> included to the basis. Definition at line 534 of file spxbasis.h. References SPxBasisBase< R >::lastin. ◆ lastIndex()returns index in basis where last update was done. Definition at line 546 of file spxbasis.h. References SPxBasisBase< R >::lastidx. ◆ lastLeft()returns SPxId of last vector that left the basis. Definition at line 540 of file spxbasis.h. References SPxBasisBase< R >::lastout. ◆ lastUpdate()returns number of basis changes since last refactorization. Definition at line 552 of file spxbasis.h. References SPxBasisBase< R >::updateCount. ◆ load()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()sets up linear solver to use. If destroy is true, solver will be freed inside this object, e.g. in the destructor. ◆ loadDesc()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()◆ multBaseWith() [1/2]
Basis-vector product. ◆ multBaseWith() [2/2]
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]
VectorBase<R>-basis product. ◆ multWithBase() [2/2]
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=()
assignment operator ◆ prevIteration()returns the number of iterations prior to the last break in execution Definition at line 564 of file spxbasis.h. References SPxBasisBase< R >::lastIterCount. ◆ printMatrix()◆ printMatrixMTX()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()
Load basis from ◆ reDim()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()inform SPxBasisBase that column ◆ removedCols()inform SPxBasisBase that columns in ◆ removedRow()inform SPxBasisBase that row ◆ removedRows()inform SPxBasisBase that rows in ◆ restoreInitialBasis()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()change maximum number of iterations until a refactorization is performed Definition at line 463 of file spxbasis.h. References SPxBasisBase< R >::maxUpdates. ◆ setOutstream()Definition at line 960 of file spxbasis.h. ◆ setRep()◆ setStatus()sets basis SPxStatus to Definition at line 443 of file spxbasis.h. References SPxBasisBase< R >::invalidate(), MSG_DEBUG, SPxBasisBase< R >::NO_PROBLEM, and SPxBasisBase< R >::thestatus. Referenced by SPxSolverBase< R >::setBasisStatus(), and SPxBasisBase< R >::unLoad(). ◆ solve() [1/2]
Definition at line 658 of file spxbasis.h. References DataArray< T >::clear(), SPxBasisBase< R >::factor, SPxBasisBase< R >::factorize(), SPxBasisBase< R >::factorized, and DataArray< T >::size(). ◆ solve() [2/2]
Definition at line 644 of file spxbasis.h. References DataArray< T >::clear(), SPxBasisBase< R >::factor, SPxBasisBase< R >::factorize(), and SPxBasisBase< R >::factorized. ◆ solve4update() [1/5]
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 681 of file spxbasis.h. References DataArray< T >::clear(), SPxBasisBase< R >::factor, SPxBasisBase< R >::factorize(), SPxBasisBase< R >::factorized, and DataArray< T >::size(). ◆ solve4update() [2/5]
solves two systems in one call using only sparse data structures Definition at line 704 of file spxbasis.h. References SPxBasisBase< R >::factor, SPxBasisBase< R >::factorize(), and SPxBasisBase< R >::factorized. ◆ solve4update() [3/5]
solves three systems in one call using only sparse data structures Definition at line 724 of file spxbasis.h. References SPxBasisBase< R >::factor, SPxBasisBase< R >::factorize(), and SPxBasisBase< R >::factorized. ◆ solve4update() [4/5]
solves two systems in one call. Definition at line 695 of file spxbasis.h. References SPxBasisBase< R >::factor, SPxBasisBase< R >::factorize(), and SPxBasisBase< R >::factorized. ◆ solve4update() [5/5]
solves three systems in one call. Definition at line 713 of file spxbasis.h. References SPxBasisBase< R >::factor, SPxBasisBase< R >::factorize(), and SPxBasisBase< R >::factorized. ◆ solver()
returns loaded solver. Definition at line 576 of file spxbasis.h. References SPxBasisBase< R >::theLP. ◆ stability()returns the stability of the basis matrix. Definition at line 639 of file spxbasis.h. References SPxBasisBase< R >::factor. ◆ statistics()returns statistical information in form of a string. Definition at line 947 of file spxbasis.h. References SPxBasisBase< R >::factor, SPxBasisBase< R >::getTotalUpdateCount(), and SPxBasisBase< R >::getTotalUpdateTime(). ◆ status()returns current SPxStatus. Definition at line 437 of file spxbasis.h. References SPxBasisBase< R >::thestatus. Referenced by SPxSolverBase< R >::getBasisStatus(). ◆ unLoad()unloads the LP from the basis. Definition at line 910 of file spxbasis.h. References SPxBasisBase< R >::NO_PROBLEM, SPxBasisBase< R >::setStatus(), and SPxBasisBase< R >::theLP. ◆ writeBasis()
Write basis to Member Data Documentation◆ factor
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
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(). ◆ fillFactorallowed 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. ◆ freeSlinSolvertrue iff factor should be freed inside of this object Definition at line 426 of file spxbasis.h. ◆ iterCountnumber of calls to change() since last manipulation Definition at line 400 of file spxbasis.h. Referenced by SPxBasisBase< R >::iteration(). ◆ iterDegenChecknumber of calls to change() since last degeneracy check Definition at line 402 of file spxbasis.h. Referenced by SPxBasisBase< R >::lastDegenCheck(). ◆ lastFillfill ratio that occured during last factorization Definition at line 407 of file spxbasis.h. ◆ lastidxlastIndex(): basis index where last update was done Definition at line 415 of file spxbasis.h. Referenced by SPxBasisBase< R >::lastIndex(). ◆ lastinlastEntered(): variable entered the base last Definition at line 413 of file spxbasis.h. Referenced by SPxBasisBase< R >::lastEntered(). ◆ lastIterCountnumber of calls to change() before halting the simplex Definition at line 401 of file spxbasis.h. Referenced by SPxBasisBase< R >::prevIteration(). ◆ lastMemmemory needed after last fresh factorization Definition at line 406 of file spxbasis.h. ◆ lastNzCountnumber of nonzeros in basis matrix after last fresh factorization Definition at line 408 of file spxbasis.h. ◆ lastoutlastLeft(): variable left the base last Definition at line 414 of file spxbasis.h. Referenced by SPxBasisBase< R >::lastLeft(). ◆ matrixpointers to the vectors of the basis matrix. Definition at line 359 of file spxbasis.h. Referenced by SPxBasisBase< R >::baseVec(). ◆ matrixIsSetup
Definition at line 361 of file spxbasis.h. Referenced by SPxBasisBase< R >::baseVec(). ◆ maxUpdatesnumber 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(). ◆ memFactorallowed total increase in memory consumption before refactorization Definition at line 394 of file spxbasis.h. ◆ minStabminimum stability Definition at line 416 of file spxbasis.h. ◆ nonzeroFactorallowed 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. ◆ nzCountnumber of nonzeros in basis matrix Definition at line 405 of file spxbasis.h. ◆ spxoutmessage handler Definition at line 427 of file spxbasis.h. Referenced by SPxBasisBase< R >::SPxBasisBase(). ◆ theBaseIdSPxIds of basic vectors. Definition at line 357 of file spxbasis.h. Referenced by SPxBasisBase< R >::baseId(), and SPxBasisBase< R >::baseId(). ◆ thedescthe basis' Descriptor Definition at line 425 of file spxbasis.h. Referenced by SPxBasisBase< R >::desc(), and SPxBasisBase< R >::desc(). ◆ theLP
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(). ◆ thestatuscurrent status of the basis. Definition at line 424 of file spxbasis.h. Referenced by SPxBasisBase< R >::setStatus(), and SPxBasisBase< R >::status(). ◆ theTimetime spent in updates Definition at line 410 of file spxbasis.h. Referenced by SPxBasisBase< R >::getTotalUpdateTime(). ◆ timerType
type of timer (user or wallclock) Definition at line 411 of file spxbasis.h. ◆ totalUpdateCountnumber of updates Definition at line 404 of file spxbasis.h. Referenced by SPxBasisBase< R >::getTotalUpdateCount(). ◆ updateCountnumber of calls to change() since last factorize() Definition at line 403 of file spxbasis.h. Referenced by SPxBasisBase< R >::lastUpdate().
|