The Working Basis Matrix :: SAS/OR(R) 13.1 User's Guide: Mathematical Programming Legacy Procedures

The Working Basis Matrix

Let $\mb {T}$ be the basis matrix of NPSC. The following partitioning is done:

$\begin{equation*} \Strong{T=} \left[ \begin{array}{cc} \Strong{A} & \Strong{B} \\ \Strong{C} & \Strong{D} \\ \end{array} \right] \end{equation*}$

where

$n$ is the number of nodes.
$k$ is the number of side constraints.
$\mb {A} \: (n \times n)$ is the network component of the basis. Most of the columns of this matrix are columns of the problem’s node-arc incidence matrix. The arcs associated with columns of $\mb {A}$ , called key basic variables or key arcs, form a spanning tree. The data structures of the spanning tree of this submatrix of the basis $\mb {T}$ enable the computations involving $\mb {T}$ and the manner in which $\mb {T}$ is updated to be very efficient, especially those dealing with $\mb {A}$ (or $\mb {A^{-1}}$ ).
$\mb {C} \: (k \times n)$ are the key arcs’ side constraint coefficient columns.
$\mb {B} \: (n \times k)$ are the node-arc incidence matrix columns of the nontree arcs. The columns of $\mb {B}$ having nonzero elements are associated with basic nonspanning tree arcs.
$\mb {D} \: (k \times k)$ are the constraint coefficient columns of nonkey basic variables. Nonkey basic variables not only include nontree basic arcs but also basic slack, surplus, artificial, or nonarc variables.

It is more convenient to factor $\mb {T}$ by block triangular matrices $\mb {P}$ and $\mb {M}$ , such that $\mb {P} = \mb {T M}$ . The matrices $\mb {P}$ and $\mb {M}$ are used instead of $\mb {T}$ because they are less burdensome to work with. You can perform block substitution when solving the simplex iteration linear systems of equations

$\begin{equation*} \Strong{P=} \left[ \begin{array}{cc} \Strong{A} & \Strong{0} \\ \Strong{C} & \Strong{$D_ w$} \\ \end{array} \right] \end{equation*}$

$\begin{equation*} \Strong{M=} \left[ \begin{array}{cc} \Strong{I} & \Strong{$-A^{-1}B$} \\ \Strong{0} & \Strong{I} \\ \end{array} \right] \end{equation*}$

where $\mb {D_ w} = \mb {D} - \mb {CA^{-1}B}$ and is called the working basis matrix.

To perform block substitution, you need the tree data structure of the $\mb {A}$ matrix, and also the $\mb {C}$ , $\mb {B}$ , and $\mb {D_ w}$ matrices. Because the $\mb {C}$ matrix consists of columns of the constraint coefficient matrix, the maintenance of $\mb {C}$ from iteration to iteration simply entails changing information specifying which columns of the constraint coefficient matrix compose $\mb {C}$ .

The $\mb {A^{-1}B}$ matrix is usually very sparse. Fortunately, the information in $\mb {A^{-1}B}$ can be initialized easily using the tree structures. In most iterations, only one column is replaced by a new one. The values of the elements of the new column may already be known from preceding steps of the simplex iteration.

The working basis matrix is the submatrix that presents the most computational complexity. However, PROC NETFLOW usually can use classical simplex pivot techniques. In many iterations, only one column of $\mb {D_ w}$ changes. Sometimes it is not necessary to update $\mb {D_ w}$ or its inverse at all.

If INVD_2D is specified in the PROC NETFLOW statement, only one row and one column may need to be changed in the $\mb {D_ w^{-1}}$ before the next simplex iteration can begin. The new contents of the changed column are already known. The new elements of the row that changes are influenced by the contents of a row of $\mb {A^{-1}B}$ that is very sparse.

If INVD_2D is not specified in the PROC NETFLOW statement, the Bartels-Golub update can be used to update the LU factors of $\mb {D_ w}$ . The choice must be made whether to perform a series of updates (how many depends on the number of nonzeros in a row of $\mb {A^{-1}B}$ ), or refactorization.