# Revised simplex method

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Revised_simplex_method
> Markdown URL: https://mediated.wiki/source/Revised_simplex_method.md
> Source: https://en.wikipedia.org/wiki/Revised_simplex_method
> Source revision: 1331449587
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

Linear programming algorithm

In [mathematical optimization](/source/Mathematical_optimization), the **revised simplex method** is a variant of [George Dantzig](/source/George_Dantzig)'s [simplex method](/source/Simplex_method) for [linear programming](/source/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](/source/Basis_(linear_algebra)) of the [matrix](/source/Matrix_(mathematics)) 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:

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

## Algorithmic description

### Optimality conditions

For linear programming, the [Karush–Kuhn–Tucker conditions](/source/Karush%E2%80%93Kuhn%E2%80%93Tucker_conditions) are both [necessary and sufficient](/source/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](/source/Lagrange_multiplier) associated with the constraints ***Ax*** = ***b*** and ***x*** ≥ **0**, respectively.[2] The last condition, which is equivalent to *sixi* = 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 ***xB*** ≥ **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 ***sB*** = **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 ***sN*** ≥ **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](/source/Degeneracy_(mathematics)), a pivot operation always results in a strict decrease in ***c***T***x***. 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 *sq* < 0 as the *entering index*. The corresponding column of ***A***, ***A**q*, will be moved into the basis, and *xq* 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 *xq* results in a decrease by −*sq* in ***c***T***x***.[5] Since

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

***xB*** must be correspondingly decreased by Δ***xB*** = ***B***−1***A**qxq* subject to ***xB*** − Δ***xB*** ≥ **0**. Let ***d*** = ***B***−1***A**q*. If ***d*** ≤ **0**, no matter how much *xq* is increased, ***xB*** − Δ***xB*** will stay nonnegative. Hence, ***c***T***x*** can be arbitrarily decreased, and thus the problem is unbounded. Otherwise, select an index *p* = argmin1≤*i*≤*m* {*xi*/*di* | *di* > 0} as the *leaving index*. This choice effectively increases *xq* from zero until *xp* is reduced to zero while maintaining feasibility. The pivot operation concludes with replacing ***A**p* with ***A**q* in the basis.

## Numerical example

See also: [Simplex method § Example](/source/Simplex_method#Example)

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*3 results in *x*4 and *x*5 being decreased by 1 and 3, respectively. Therefore, *x*3 is increased to 5, at which point *x*5 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 ***sN*** indicates that ***x*** is now optimal.

## Practical issues

### Degeneracy

See also: [Simplex method § Degeneracy: stalling and cycling](/source/Simplex_method#Degeneracy:_stalling_and_cycling)

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***T***x***, 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](/source/System_of_linear_equations) 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](/source/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. **[^](#cite_ref-4)** 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. ^ [***a***](#cite_ref-FOOTNOTEMorgan1997§2_1-0) [***b***](#cite_ref-FOOTNOTEMorgan1997§2_1-1) [Morgan 1997](#CITEREFMorgan1997), §2.

1. **[^](#cite_ref-FOOTNOTENocedalWright2006358Eq.&nbsp;13.4_2-0)** [Nocedal & Wright 2006](#CITEREFNocedalWright2006), p. 358, Eq. 13.4.

1. **[^](#cite_ref-FOOTNOTENocedalWright2006363Theorem&nbsp;13.2_3-0)** [Nocedal & Wright 2006](#CITEREFNocedalWright2006), p. 363, Theorem 13.2.

1. **[^](#cite_ref-FOOTNOTENocedalWright2006370Theorem&nbsp;13.4_5-0)** [Nocedal & Wright 2006](#CITEREFNocedalWright2006), p. 370, Theorem 13.4.

1. **[^](#cite_ref-FOOTNOTENocedalWright2006369Eq.&nbsp;13.24_6-0)** [Nocedal & Wright 2006](#CITEREFNocedalWright2006), p. 369, Eq. 13.24.

1. **[^](#cite_ref-FOOTNOTENocedalWright2006381§13.5_7-0)** [Nocedal & Wright 2006](#CITEREFNocedalWright2006), p. 381, §13.5.

1. **[^](#cite_ref-FOOTNOTENocedalWright2006372§13.4_8-0)** [Nocedal & Wright 2006](#CITEREFNocedalWright2006), p. 372, §13.4.

### Bibliography

- Morgan, S. S. (1997). [*A Comparison of Simplex Method Algorithms*](https://web.archive.org/web/20110807134509/http://www.cise.ufl.edu/research/sparse/Morgan/index.htm) (MSc thesis). [University of Florida](/source/University_of_Florida). Archived from [the original](http://www.cise.ufl.edu/research/sparse/Morgan/index.htm) on 7 August 2011.

- Nocedal, J.; Wright, S. J. (2006). Mikosch, T. V.; Resnick, S. I.; Robinson, S. M. (eds.). [*Numerical Optimization*](https://www.springer.com/mathematics/book/978-0-387-30303-1). Springer Series in Operations Research and Financial Engineering (2nd ed.). New York, NY, USA: [Springer](/source/Springer_Science%2BBusiness_Media). [ISBN](/source/ISBN_(identifier)) [978-0-387-30303-1](https://en.wikipedia.org/wiki/Special:BookSources/978-0-387-30303-1).

v t e Optimization: Algorithms, methods, and heuristics Unconstrained nonlinear Functions Golden-section search Powell's method Line search Nelder–Mead method Successive parabolic interpolation Gradients Convergence Trust region Wolfe conditions Quasi–Newton Berndt–Hall–Hall–Hausman Broyden–Fletcher–Goldfarb–Shanno and L-BFGS Davidon–Fletcher–Powell Symmetric rank-one (SR1) Other methods Conjugate gradient Gauss–Newton Gradient Mirror Levenberg–Marquardt Powell's dog leg method Truncated Newton Hessians Newton's method Optimization computes maxima and minima. Constrained nonlinear General Barrier methods Penalty methods Differentiable Augmented Lagrangian methods Sequential quadratic programming Successive linear programming Convex optimization Convex minimization Cutting-plane method Reduced gradient (Frank–Wolfe) Subgradient method Linear and quadratic Interior point Affine scaling Ellipsoid algorithm of Khachiyan Projective algorithm of Karmarkar Basis-exchange Simplex algorithm of Dantzig Revised simplex algorithm Criss-cross algorithm Principal pivoting algorithm of Lemke Active-set method Combinatorial Paradigms Approximation algorithm Dynamic programming Greedy algorithm Integer programming Branch and bound/cut Graph algorithms Minimum spanning tree Borůvka Prim Kruskal Shortest path Bellman–Ford SPFA Dijkstra Floyd–Warshall Network flows Dinic Edmonds–Karp Ford–Fulkerson Push–relabel maximum flow Metaheuristics Evolutionary algorithm Hill climbing Local search Parallel metaheuristics Simulated annealing Spiral optimization algorithm Tabu search Software

v t e Complementarity problems and algorithms Complementarity Problems Linear programming (LP) Quadratic programming (QP) Linear complementarity problem (LCP) Mixed linear (MLCP) Mixed (MCP) Nonlinear (NCP) Basis-exchange algorithms Simplex (Dantzig) Revised simplex Criss-cross Lemke

---
Adapted from the Wikipedia article [Revised simplex method](https://en.wikipedia.org/wiki/Revised_simplex_method) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Revised_simplex_method?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.