Revised simplex method

In mathematical optimization, the revised simplex method is a variant of George Dantzig's simplex method for linear programming.

The revised simplex method is mathematically equivalent to the standard simplex method but differs in implementation. Instead of maintaining a tableau which explicitly represents the constraints adjusted to a set of basic variables, it maintains a representation of a basis of the matrix representing the constraints. The matrix-oriented approach allows for greater computational efficiency by enabling sparse matrix operations.^[1]

For the rest of the discussion, it is assumed that a linear programming problem has been converted into the following standard form:

minimize c T x subject to A x = b , x ≥ 0 {\displaystyle {\begin{array}{rl}{\text{minimize}}&{\boldsymbol {c}}^{\mathrm {T} }{\boldsymbol {x}}\\{\text{subject to}}&{\boldsymbol {Ax}}={\boldsymbol {b}},{\boldsymbol {x}}\geq {\boldsymbol {0}}\end{array}}}

where A ∈ ℝ^m×n. Without loss of generality, it is assumed that the constraint matrix A has full row rank and that the problem is feasible, i.e., there is at least one x ≥ 0 such that Ax = b. If A is rank-deficient, either there are redundant constraints, or the problem is infeasible. Both situations can be handled by a presolve step.

For linear programming, the Karush–Kuhn–Tucker conditions are both necessary and sufficient for optimality. The KKT conditions of a linear programming problem in the standard form is

A x = b , A T λ + s = c , x ≥ 0 , s ≥ 0 , s T x = 0 {\displaystyle {\begin{aligned}{\boldsymbol {Ax}}&={\boldsymbol {b}},\\{\boldsymbol {A}}^{\mathrm {T} }{\boldsymbol {\lambda }}+{\boldsymbol {s}}&={\boldsymbol {c}},\\{\boldsymbol {x}}&\geq {\boldsymbol {0}},\\{\boldsymbol {s}}&\geq {\boldsymbol {0}},\\{\boldsymbol {s}}^{\mathrm {T} }{\boldsymbol {x}}&=0\end{aligned}}}

where λ and s are the Lagrange multipliers associated with the constraints Ax = b and x ≥ 0, respectively.^[2] The last condition, which is equivalent to s_ix_i = 0 for all 1 < i < n, is called the complementary slackness condition.

By what is sometimes known as the fundamental theorem of linear programming, a vertex x of the feasible polytope can be identified by being a basis B of A chosen from the latter's columns.^[a] Since A has full rank, B is nonsingular. Without loss of generality, assume that A = [B N]. Then x is given by

x = [ x B x N ] = [ B − 1 b 0 ] {\displaystyle {\boldsymbol {x}}={\begin{bmatrix}{\boldsymbol {x_{B}}}\\{\boldsymbol {x_{N}}}\end{bmatrix}}={\begin{bmatrix}{\boldsymbol {B}}^{-1}{\boldsymbol {b}}\\{\boldsymbol {0}}\end{bmatrix}}}

where x_B ≥ 0. Partition c and s accordingly into

c = [ c B c N ] , s = [ s B s N ] . {\displaystyle {\begin{aligned}{\boldsymbol {c}}&={\begin{bmatrix}{\boldsymbol {c_{B}}}\\{\boldsymbol {c_{N}}}\end{bmatrix}},\\{\boldsymbol {s}}&={\begin{bmatrix}{\boldsymbol {s_{B}}}\\{\boldsymbol {s_{N}}}\end{bmatrix}}.\end{aligned}}}

To satisfy the complementary slackness condition, let s_B = 0. It follows that

B T λ = c B , N T λ + s N = c N , {\displaystyle {\begin{aligned}{\boldsymbol {B}}^{\mathrm {T} }{\boldsymbol {\lambda }}&={\boldsymbol {c_{B}}},\\{\boldsymbol {N}}^{\mathrm {T} }{\boldsymbol {\lambda }}+{\boldsymbol {s_{N}}}&={\boldsymbol {c_{N}}},\end{aligned}}}

which implies that

λ = ( B T ) − 1 c B , s N = c N − N T λ . {\displaystyle {\begin{aligned}{\boldsymbol {\lambda }}&=({\boldsymbol {B}}^{\mathrm {T} })^{-1}{\boldsymbol {c_{B}}},\\{\boldsymbol {s_{N}}}&={\boldsymbol {c_{N}}}-{\boldsymbol {N}}^{\mathrm {T} }{\boldsymbol {\lambda }}.\end{aligned}}}

If s_N ≥ 0 at this point, the KKT conditions are satisfied, and thus x is optimal.

If the KKT conditions are violated, a pivot operation consisting of introducing a column of N into the basis at the expense of an existing column in B is performed. In the absence of degeneracy, a pivot operation always results in a strict decrease in c^Tx. Therefore, if the problem is bounded, the revised simplex method must terminate at an optimal vertex after repeated pivot operations because there are only a finite number of vertices.^[4]

Select an index m < q ≤ n such that s_q < 0 as the entering index. The corresponding column of A, A_q, will be moved into the basis, and x_q will be allowed to increase from zero. It can be shown that

∂ ( c T x ) ∂ x q = s q , {\displaystyle {\frac {\partial ({\boldsymbol {c}}^{\mathrm {T} }{\boldsymbol {x}})}{\partial x_{q}}}=s_{q},}

i.e., every unit increase in x_q results in a decrease by −s_q in c^Tx.^[5] Since

B x B + A q x q = b , {\displaystyle {\boldsymbol {Bx_{B}}}+{\boldsymbol {A}}_{q}x_{q}={\boldsymbol {b}},}

x_B must be correspondingly decreased by Δx_B = B⁻¹A_qx_q subject to x_B − Δx_B ≥ 0. Let d = B⁻¹A_q. If d ≤ 0, no matter how much x_q is increased, x_B − Δx_B will stay nonnegative. Hence, c^Tx can be arbitrarily decreased, and thus the problem is unbounded. Otherwise, select an index p = argmin_1≤i≤m {x_i/d_i | d_i > 0} as the leaving index. This choice effectively increases x_q from zero until x_p is reduced to zero while maintaining feasibility. The pivot operation concludes with replacing A_p with A_q in the basis.

Consider a linear program where

c = [ − 2 − 3 − 4 0 0 ] T , A = [ 3 2 1 1 0 2 5 3 0 1 ] , b = [ 10 15 ] . {\displaystyle {\begin{aligned}{\boldsymbol {c}}&={\begin{bmatrix}-2&-3&-4&0&0\end{bmatrix}}^{\mathrm {T} },\\{\boldsymbol {A}}&={\begin{bmatrix}3&2&1&1&0\\2&5&3&0&1\end{bmatrix}},\\{\boldsymbol {b}}&={\begin{bmatrix}10\\15\end{bmatrix}}.\end{aligned}}}

Let

B = [ A 4 A 5 ] , N = [ A 1 A 2 A 3 ] {\displaystyle {\begin{aligned}{\boldsymbol {B}}&={\begin{bmatrix}{\boldsymbol {A}}_{4}&{\boldsymbol {A}}_{5}\end{bmatrix}},\\{\boldsymbol {N}}&={\begin{bmatrix}{\boldsymbol {A}}_{1}&{\boldsymbol {A}}_{2}&{\boldsymbol {A}}_{3}\end{bmatrix}}\end{aligned}}}

initially, which corresponds to a feasible vertex x = [0 0 0 10 15]^T. At this moment,

λ = [ 0 0 ] T , s N = [ − 2 − 3 − 4 ] T . {\displaystyle {\begin{aligned}{\boldsymbol {\lambda }}&={\begin{bmatrix}0&0\end{bmatrix}}^{\mathrm {T} },\\{\boldsymbol {s_{N}}}&={\begin{bmatrix}-2&-3&-4\end{bmatrix}}^{\mathrm {T} }.\end{aligned}}}

Choose q = 3 as the entering index. Then d = [1 3]^T, which means a unit increase in x₃ results in x₄ and x₅ being decreased by 1 and 3, respectively. Therefore, x₃ is increased to 5, at which point x₅ is reduced to zero, and p = 5 becomes the leaving index.

After the pivot operation,

B = [ A 3 A 4 ] , N = [ A 1 A 2 A 5 ] . {\displaystyle {\begin{aligned}{\boldsymbol {B}}&={\begin{bmatrix}{\boldsymbol {A}}_{3}&{\boldsymbol {A}}_{4}\end{bmatrix}},\\{\boldsymbol {N}}&={\begin{bmatrix}{\boldsymbol {A}}_{1}&{\boldsymbol {A}}_{2}&{\boldsymbol {A}}_{5}\end{bmatrix}}.\end{aligned}}}

Correspondingly,

x = [ 0 0 5 5 0 ] T , λ = [ 0 − 4 / 3 ] T , s N = [ 2 / 3 11 / 3 4 / 3 ] T . {\displaystyle {\begin{aligned}{\boldsymbol {x}}&={\begin{bmatrix}0&0&5&5&0\end{bmatrix}}^{\mathrm {T} },\\{\boldsymbol {\lambda }}&={\begin{bmatrix}0&-4/3\end{bmatrix}}^{\mathrm {T} },\\{\boldsymbol {s_{N}}}&={\begin{bmatrix}2/3&11/3&4/3\end{bmatrix}}^{\mathrm {T} }.\end{aligned}}}

A positive s_N indicates that x is now optimal.

Because the revised simplex method is mathematically equivalent to the simplex method, it also suffers from degeneracy, where a pivot operation does not result in a decrease in c^Tx, and a chain of pivot operations causes the basis to cycle. A perturbation or lexicographic strategy can be used to prevent cycling and guarantee termination.^[6]

Two types of linear systems involving B are present in the revised simplex method:

B z = y , B T z = y . {\displaystyle {\begin{aligned}{\boldsymbol {Bz}}&={\boldsymbol {y}},\\{\boldsymbol {B}}^{\mathrm {T} }{\boldsymbol {z}}&={\boldsymbol {y}}.\end{aligned}}}

Instead of refactorizing B, usually an LU factorization is directly updated after each pivot operation, for which purpose there exist several strategies such as the Forrest−Tomlin and Bartels−Golub methods. However, the amount of data representing the updates as well as numerical errors builds up over time and makes periodic refactorization necessary.^[1][7]