SPxBasis

In file doc.dxx:

class SPxBasis

simplex basis

Inheritance:

Public

Documentation

simplex basis. Consider the linear program as provided from class SPxLP

where $c, l_c, u_c, x \in R^n$, $l_r, u_r \in R^m$ and $A \in 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 nonsingular 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 nonsigular matrix. The dimension of the vectors is refferred to as the basis' dimension, whereas the number of vectors belonging to the LP is called the basis' codimension.
Class SPxBasis 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 SPxBasis provides methods for solving linear systems with the basis matrix. However, SPxBasis does not provide a linear solver by its own. Instead, a SLinSolver object must be loaded to a SPxBasis which will be called for solving linear systems.

Basis status enum SPxStatus Basis status. Each SPxBasis is assigned a status flag, which can take on of the above values. NO_PROBLEM No Problem has been loaded to the basis SINGULAR Basis is singular REGULAR Basis is not know to be dual nor primal feasible DUAL Basis is dual feasible PRIMAL Basis is primal feasible OPTIMAL Basis is optimal, i.e. dual and primal feasible UNBOUNDED LP has been proven to be unbounded INFEASIBLE LP has been proven to be infeasible SPxStatus status() current SPxStatus. void setStatus(SPxStatus stat) set basis SPxStatus to stat.

Basis descriptor

class Desc

enum Status
Status of a variable. A basis is described by assigning a Status to all of the LPs variables and covariables. This assignment is maintained by the basis Descriptor.
Variables and covariables may have a primal or dual Status. The first type specifies that a variable is set on a primal bound, while the later type indicates a dual variable to be set on a bound. If a row variable has a primal status, P_ON_UPPER say, this means that the upper bound of the inequality is set to be tight. Hence, in this case the upper bound must not be infinity.
Equivalently, if the status of a variable is dual, D_ON_UPPER say, it means that the dual variable corresponding to the upper bound inequality of this variable is set to 0.
For a column basis, primal Status's correspond to nonbasic variables, while dual ones are basic. This is reversed for a row basis. We will now reveil in more detail the significance of variable Status's.
Primal Variables
Let consider a range inequality $l_r \le a^T x \le u_r$ or bounds on a variable $l_c \le x_c \le u_c$ The following table reveils what is implied if the corresponding variable or covariable is assigned to a primal Status:

$l_c \le x_c \le u_c$ Status($x_i$) $l_r \le a^T x \le u_r$

$x_c = u_c < \infty$ P_ON_UPPER $a^T x = u_r < \infty$
$x_c = l_c > -\infty$ P_ON_LOWER $a^T x = l_r > -\infty$
$-\infty < l_c = x_c = u_c < \infty$ P_FIXED $-\infty < l_r = a^T x = u_r < \infty$
$-\infty = l_i < x_i=0 < u_i = \infty$ P_FREE $-\infty = l_r < a^T x = 0 < u_r = \infty$

Note that to determine if a variable with Status stat is set to its upper bound, on can compute the following test: (-stat | -P_ON_UPPER). This will yield true even if the variable is fixed, i.e. sitting on both bounds at the same time.
Dual Variables
In principle for implementing the Simplex algorithm it would suffice to use only one dual Status. However, for performance reasons it is advisable to introduce various dual Status types, reflecting the structure of the bounds. Given an upper bound $u$ and a lower bound $l$ of a constraint or variable, the following table indicates the setting of the dual Status of this variable.

$l \le ... \le u$ Status

$-\infty < l \ne u < \infty$ D_ON_BOTH
$-\infty < l \ne u = \infty$ D_ON_UPPER
$-\infty = l \ne u < \infty$ D_ON_LOWER
$-\infty < l = u < \infty$ D_FREE
$-\infty = l \ne u = \infty$ D_UNDEFINED

Note that unbounded primal variables are reflected by an D_UNDEFINED dual variable, since no DUAL variables exist to them. To facilate the assignment of dual Status's, class SPxBasis provides methods dualStatus, dualColStatus and dualRowStatus.

P_ON_LOWER
primal variable is set to its lower bound

P_ON_UPPER
primal variable is set to its upper bound

P_FREE
primal variable is left free, but not unset

P_FIXED
primal variable is fixed to both bounds

D_FREE
dual variable is left free, but not unset

D_ON_UPPER
dual variable is set to its upper bound

D_ON_LOWER
dual variable is set to its lower bound

D_ON_BOTH
dual variable has two bounds

D_UNDEFINED
primal or dual variable has no status

int nCols()
number of columns.

int nRows()
number of rows.

int dim()
dimension.

int coDim()
codimension.

Status& rowStatus( int i )

Status rowStatus( int i )
status of row i.

const Status* rowStatus( void )
array of row Status's.

Status& colStatus( int i )

Status colStatus( int i )
status of column i.

const Status* colStatus( void )
array of column Status's.

Status& status( int i )

Status status( int i )
status of variable i.

const Status* status( void )
array of variable Status's.

Status& coStatus( int i )

Status coStatus( int i )
status of covariable i.

const Status* coStatus( void )
array of covariable Status's.

void reSize( int rowDim, int colDim )
reset dimensions.

int isConsistent( )

const Desc& desc()

Desc& desc()
current Desc of basis.

Desc::Status dualColStatus( int i )
dual Status for the i-th column variable of the loaded LP.

Desc::Status dualStatus( const SPxLP::SPxColId& id )
dual Status for the id-th column variable of the loaded LP.

Desc::Status dualRowStatus( int i )
dual Status for the i-th row variable of the loaded LP.

Desc::Status dualStatus( const SPxLP::SPxRowId& id )
dual Status for the id-th row variable of the loaded LP.

Desc::Status dualStatus( const SPxLP::Id& id )
dual Status for the id-th variable of the loaded LP.

virtual void load( const Desc& )
Setup basis. Loads a Desc to the basis and sets up the basis matrix and all vectors accordingly. The Desc must the same number of rows and columns as the currently loaded LP.

virtual void readBasis( istream& in, NameSet& rowNames, NameSet& colNames )
read a file in MPS basis format from in.

Control Parameters int maxUpdates 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. double nonzeroFactor increase of nonzeros before refactorization. When the number of nonzeros in LU factorization exceeds nonzeroFactor times the number of nonzeros of a fresh on, the basis matrix is refactorized.

Inquiry Methods SPxLP::Id& baseId(int i) SPxLP::Id baseId(int i) id of i-th basic vector. const SVector& baseVec(int i) i-th basic vector. SPxLP::Id lastEntered() Id of last vector included to the basis. SPxLP::Id lastLeft() Id of last vector that left the basis. int lastIndex() index in basis where last update was done. int lastUpdate() number of basis changes since last refactorization. int iteration() number of basis changes since last load. SoPlex* return loaded solver ()

Linear Algebra Vector& multBaseWith( Vector& x) Basis-vector product. Depending on the representation, for a SPxBasis B, B.multBaseWith(x) computes {$x \leftarrow Bx$} in the columnwise case and {$x \leftarrow x^TB$} in the rowwise case. Both can be seen uniformly as multiplying the basis matrix B with a vector x alligned the same way as the vectors of B. Vector& multWithBase( Vector& x) Vector-basis product. Depending on the representation, for a SPxBasis B, B.multWithBase(x) computes {$x \leftarrow x^TB$} in the columnwise case and {$x \leftarrow Bx$} in the rowwise case. Both can be seen uniformly as multiplying the basis matrix B with a vector x alligned the same way as the covectors of B. double stability() stability of basis matrix. void solve2( Vector& x, Vector& rhs ) Solve linear system with basis matrix. Depending on the representation, for a SPxBasis B, B.solve(x) computes {$x \leftarrow B^{-1}x$} in the columnwise case and {$x \leftarrow x^TB^{-1}$} in the rowwise case. Both can be seen uniformly as solving a linear system with the basis matrix B and a right handside vector x aligned the same way as the vectors of B. void solve2( Vector& x, SSVector& rhs ) void solve2( SSVector& x, Vector& rhs ) void solve2( SSVector& x, SSVector& rhs ) void solve( Vector& x, const Vector& rhs ) void solve( Vector& x, const SVector& rhs ) void solve( SSVector& x, const SVector& rhs ) void solve( SSVector& x, const Vector& rhs ) void solve4update( SSVector& x, const SVector& rhs ) void solve4update(SSVector& x, Vector& y, const SVector& rhsx, SSVector& rhsy) void coSolve2( Vector& x, Vector& rhs ) Cosolve linear system with basis matrix. Depending on the representation, for a SPxBasis B, B.solve(x) computes {$x \leftarrow x^TB^{-1}$} in the columnwise case and {$x \leftarrow B^{-1}x$} in the rowwise case. Both can be seen uniformly as solving a linear system with the basis matrix B and a right handside vector x alligned the same way as the covectors of B. If idx != 0 is given, upon return idx contains the indeces of the nonzeros of the result vector. idx must be allocated to fit enough indeces. void coSolve2( Vector& x, SSVector& rhs ) void coSolve2( SSVector& x, Vector& rhs ) void coSolve2( SSVector& x, SSVector& rhs ) void coSolve( Vector& x, const Vector& rhs ) void coSolve( Vector& x, const SVector& rhs ) void coSolve( SSVector& x, const SVector& rhs ) void coSolve( SSVector& x, const Vector& rhs ) void coSolve( SSVector& x, Vector& y, const SVector& rhsx, SSVector& rhsy ) solve 2 systems in 1 call.

Modification.

These methods must be called, after the loaded LP has been modified.

void reDim()

Resize 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.

void addedRows( int n )

void removedRow(int i)

void removedRows(int perm[])

void addedCols( int n )

void removedCol(int i)

void removedCols(int perm[])

void changedRow( int )

void changedCol( int )

void changedElement( int, int )

Miscellaneous virtual void change( int i, SPxLP::Id& id, const SVector* enterVec, const SSVector* eta=0 ) perform basis update. Changes the $i$-th vector of the basis with the vector associated to id. This includes: updating the factorization, or recomputing it from scratch by calling \hbox{factorize()} resetting lastEnered() resetting lastIndex() resetting lastLeft() resetting lastUpdate() resetting iterations() The basis Desc is not modified, since factor() cannot know about how to set up the status of the involved variables correctly. A vector vec may be passed for a fast ETA update of the LU factorization associated to the basis. It must be initialized with the solution vector $x$ of the right linear system $Bx = b$ with the entering vector as right hand side vetor $b$, where $B$ denotes the basis matrix. This can be computed using method solve(b). When using FAST updates, a vector upd may be passed for improved performance. It must be initialized by a call to factor->solveRightUpdate as described in SLinSolver. What implementation is hidden behind FAST updates, depends on the SLinSolver implementation class. virtual int doFactorize() refactorize basis instead of updating the factorization?. virtual void factorize() factorize the basis matrix. void setRep( ) Set descriptor representation according to loaded LP void load( SLinSolver* solver ) setup linear solver to use. void load( SoPlex* lp ) Loads the lp to the basis. This involves resetting all counters to 0 and setting up a regular default basis consisting of slacks, artificial variables or bounds. void unLoad( ) int isConsistent() SPxBasis()

Direct child classes:: SoPlex

alphabetic index hierarchy of classes

generated by doc++

$l_c \le x_c \le u_c$	`Status`($x_i$)	$l_r \le a^T x \le u_r$

$x_c = u_c < \infty$	`P_ON_UPPER`	$a^T x = u_r < \infty$
$x_c = l_c > -\infty$	`P_ON_LOWER`	$a^T x = l_r > -\infty$
$-\infty < l_c = x_c = u_c < \infty$	`P_FIXED`	$-\infty < l_r = a^T x = u_r < \infty$
$-\infty = l_i < x_i=0 < u_i = \infty$	`P_FREE`	$-\infty = l_r < a^T x = 0 < u_r = \infty$

$l \le ... \le u$	`Status`

$-\infty < l \ne u < \infty$	`D_ON_BOTH`
$-\infty < l \ne u = \infty$	`D_ON_UPPER`
$-\infty = l \ne u < \infty$	`D_ON_LOWER`
$-\infty < l = u < \infty$	`D_FREE`
$-\infty = l \ne u = \infty$	`D_UNDEFINED`

class SPxBasis

Inheritance:

Public

Documentation