# The dual simplex algorithm

Following is the dual simplex algorithm, adapted from p. 283 of Daniel Solow's "Linear Programming, An Introduction to Finite Improvement Algorithms", Elsevier Science Publishing Co., Inc., 1984. I don't understand why it is true that "$\mathbf{u}'$ and $K'$ satisfy points a, b and c listed in step 1", as stated in step 5 of the algorithm. Any help will be appreciated.

Input

1. $m, n \in \mathbb{N}_1 (=\{1, 2, 3, \dots\})$ ... The number of constraints ($m$) and the number of variables ($n$) in the primal LP (= linear program)
2. $\mathbf{A} \in \mathbb{R}_{m \times n}$ ... The constraints matrix
3. $\mathbf{b} \in \mathbb{R}_{m \times 1}$ ... The rhs (= right hand side) of the constraints list
4. $\mathbf{c} \in \mathbb{R}_{n \times 1}$ ... The cost coefficients
5. $\Phi := (m, n, \mathbf{A}, \mathbf{b}, \mathbf{c})$ ... The primal LP, considered as the problem of deciding whether the feasible set $F := \{\mathbf{x}\in \mathbb{R}_{n \times 1} \mid: \mathbf{A}\mathbf{x} = \mathbf{b}\wedge\mathbf{x}\geq\mathbf{0}_{m \times 1}\}$ is empty and, if not, whether the set of costs $Z := \{\mathbf{c}^T\mathbf{x} :\mid \mathbf{x} \in F\}$ is bounded from below, and, if so, calculating some $\mathbf{x}^* \in \arg\min Z$.

Output

The algorithm assumes that the set $F' := \{\mathbf{u} \in \mathbb{R}_{m \times 1} \mid: \mathbf{A}^T\mathbf{u} \leq \mathbf{c}\}$ is non-empty. If it terminates, and it does so without error, it provides answers to the following questions:

1. Is the set $Z':=\{\mathbf{b}^T\mathbf{u} :\mid \mathbf{u} \in F'\}$ bounded from above?
2. If $Z'$ is bounded from above, what is some $\mathbf{u}^* \in \arg\max Z'$?

Notation

If $\mathbf{B} \in \mathbb{R}_{a \times b}$ is a real matrix (possibly a row/column vector) for some $a, b \in \mathbb{N}_1$, and if $\alpha$ is a non-empty, finite sequence of numbers from the set $\{1, 2, \dots, a\}$ and if $\beta$ is a non-empty, finite sequence of numbers from the set $\{1, 2, \dots, b\}$, then $\mathbf{B}_{\alpha, \beta}$ is the matrix $$\left[\begin{array}{ccc} \mathbf{B}_{\alpha_1, \beta_1} & \mathbf{B}_{\alpha_1, \beta_2} & \dots \\ \mathbf{B}_{\alpha_2, \beta_1} & \mathbf{B}_{\alpha_2, \beta_2} & \dots \\ \vdots & \vdots & \ddots \end{array}\right]$$

A non-empty, finite subset $s \subseteq \{1, 2, \dots\}$ can be used where a sequence is expected (in particular, as a matrix subscript), in which case it denotes the sequence constructed by listing the elements of $s$ in ascending order.

If a single number, $t \in \{1, 2, \dots\}$. is used where a sequence is expected, it should be considered to denote the sequence $(t)$.

We set $M := \{1, 2, \dots, m\}$, $N := \{1, 2, \dots, n\}$, $L := N \setminus M$, where $m$, $n$ are the numbers that are input to the algorithm.

Vectors shall be considered to be matrices, and hence subscripted with two subscripts.

$\mathbf{N}_1 := \{1, 2, 3, \dots\}$. $I_a$ and $\mathbf{0}_{a \times b}$ (where $a, b \in \mathbb{N}_1$) are respectively the $a \times a$ identity matrix and the $a\times b$ matrix consisting entirely of $0$'s.

Comparisons between matrices of the same dimensions shall be carried out component-wise, for instance $[1\ 2] \geq \mathbf{0}_{1\times 2}$ is true, but $[-1\ 2] \geq \mathbf{0}_{1 \times 2}$ is false and $[1\ 2] \geq \mathbf{0}_{2 \times 1}$ is undefined.

If $\mathbf{v} \in \mathbb{R}_{a \times 1}$ ($a \in \mathbb{N}_1$) is a column vector of real numbers and $\varphi(x)$ is a predicate that applies to real numbers (e.g. "$x<0$"), then $\arg_{\varphi}(\mathbf{v}_{i, 1}) := \{i \in \{1, 2, \dots, a\} \mid: \varphi(i)\}$. If $\mathbf{w} \in \mathbb{R}_{1 \times a}$ is a row vector of real numbers and $\varphi(x)$ is as above, then $\arg_{\varphi}\mathbf{w} := \{j \in \{1, 2, \dots, a\} \mid: \varphi(\mathbf{w}_{1, j})\}$.

The matrix operations "transpose" and "inverse" are applied after subscripting, so, for example, if $\mathbf{B} \in \mathbb{R}_{a\times a}$ for some $a \in \mathbb{N}_1$, and if $\emptyset \neq \alpha \subseteq \{1, 2, \dots, a\}$ and $\emptyset \neq \beta \subseteq \{1, 2, \dots, a\}$, then $\mathbf{B}^T_{\alpha, \beta} = (\mathbf{B}_{\alpha, \beta})^T$.

Finally, we use the notation $F'$ and $Z'$ introduced in the "Output" section.

The dual simplex algorithm

1. "Initialization". Find a dual basic feasible solution (dbfs), i.e. a vector $\mathbf{u} \in \mathbf{R}_{m \times 1}$ and a subset $K \subseteq N$ of power $m$, for which

a) $A_{M, K}^T$ is invertible,

b) $\mathbf{u} = \left(A_{M, K}^T\right)^{-1}\mathbf{c}_{K, 1}$,

c) $\mathbf{u} \in F'$.

If no such $(\mathbf{u}, K)$ pair can be found, terminate with an error.

2. "Test for optimality". If $\mathbf{A}_{M, K}^{-1}\mathbf{b} \geq \mathbf{0}_{m \times 1}$, terminate: $Z'$ is bounded from above and $\mathbf{u} \in \arg\max Z'$. Otherwise, let $k \in \arg_{<0}\mathbf{A}_{M, K}^{-1}\mathbf{b}$, and set $k^*$ to be the $k$th element of the sequence $K$.

3. "Computing the direction of movement". Set $\mathbf{d} := -\left(A_{M, K}^{-1}\right)^T_{k, M}$ [This direction is chosen because it leads to an increase in the dual cost, since $\mathbf{b}^T\mathbf{d} > 0$.]

4. "Computing the amount of movement". If $\mathbf{A}_{M, L}^T\mathbf{d} \leq \mathbf{0}_{(n - m) \times 1}$, terminate: $Z'$ is not bounded from above. Otherwise, set \begin{aligned} T & := \{(\mathbf{c}_{L, 1} - \mathbf{A}_{M, L}^T\mathbf{u})_{j, 1}/(\mathbf{A}_{M, L}^T\mathbf{d})_{j, 1}:\mid j \in \arg_{>0}\mathbf{A}_{M, L}^T\mathbf{d}\} \\ t & := \min T \\ j & :\in \arg\min T \end{aligned}

($j$ is an arbitrary member of $\arg\min T$) and set $j^*$ to be the $j$th element of the sequence $L$.

5. "Moving to the new dbfs and pivoting". Set $\mathbf{u}' := \mathbf{u} + t\mathbf{d}$ and $K' := (K \setminus \{k^*\})\cup \{j^*\}$. $\mathbf{u}'$ and $K'$ satisfy points a, b and c listed in step 1 (if we identify $\mathbf{u}$ with $\mathbf{u}'$ and $K$ with $K'$). Go to step 2.

• Two much better descriptions of the dual simplex algorithm can be found in Bertsimas and Tsitsiklis' "Introduction to Linear Optimization", section 4.5 "Standard form problems and the dual simplex method" and Alevras and Padberg's "Linear Optimization and Extensions: Problems and Solutions", section 6.4 "A Dual Simplex Algorithm". – Evan Aad Sep 24 '14 at 21:15