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]

Problem formulation

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

${\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 ∈ R^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.

Algorithmic description

Optimality conditions

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

${\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.[lower-alpha 1] Since A has full rank, B is nonsingular. Without loss of generality, assume that A = [B N]. Then x is given by

${\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

${\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

${\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

${\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.

Pivot operation

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

${\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

${\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.

Numerical example

Consider a linear program where

${\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

${\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,

${\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,

${\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,

${\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.

Practical issues

Degeneracy

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]

Basis representation

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

${\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]

Notes and references

Notes

1. The same theorem also states that the feasible polytope has at least one vertex and that there is at least one vertex which is optimal.[3]

References

1. Morgan 1997, §2.
2. Nocedal & Wright 2006, p. 358, Eq. 13.4.
3. Nocedal & Wright 2006, p. 363, Theorem 13.2.
4. Nocedal & Wright 2006, p. 370, Theorem 13.4.
5. Nocedal & Wright 2006, p. 369, Eq. 13.24.
6. Nocedal & Wright 2006, p. 381, §13.5.
7. Nocedal & Wright 2006, p. 372, §13.4.

Bibliography

• Morgan, S. S. (1997). A Comparison of Simplex Method Algorithms (MSc thesis). University of Florida. Archived from the original on 7 August 2011.CS1 maint: ref=harv (link)
• Nocedal, J.; Wright, S. J. (2006). Mikosch, T. V.; Resnick, S. I.; Robinson, S. M. (eds.). Numerical Optimization. Springer Series in Operations Research and Financial Engineering (2nd ed.). New York, NY, USA: Springer. ISBN 978-0-387-30303-1.CS1 maint: ref=harv (link)