Revised simplex method

In mathematical optimization, the revised simplex method is an 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.

Problem formulation

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

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

where ${\boldsymbol {A}}\in \mathbb {R} ^{m\times n}$. Without loss of generality, it is assumed that the constraint matrix ${\boldsymbol {A}}$ has full rank and that the problem is feasible, i.e., there is at least one ${\boldsymbol {x}}\geq {\boldsymbol {0}}$ such that ${\boldsymbol {Ax}}={\boldsymbol {b}}$. If ${\boldsymbol {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

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

where ${\boldsymbol {\lambda }}$ and ${\boldsymbol {s}}$ are the Lagrange multipliers associated with the constraints ${\boldsymbol {Ax}}={\boldsymbol {b}}$ and ${\boldsymbol {x}}\geq {\boldsymbol {0}}$, respectively. The last condition, which is equivalent to $s_{i}x_{i}=0$ for all $1\leq i\leq n$, is called the complementary slackness condition.

By what is sometimes known as the fundamental theorem of linear programming, a vertex ${\boldsymbol {x}}$ of the feasible polytope can be identified by be a basis ${\boldsymbol {B}}$ of ${\boldsymbol {A}}$ chosen from the latter's columns. Since ${\boldsymbol {A}}$ has full rank, ${\boldsymbol {B}}$ is nonsingular. Without loss of generality, assume that ${\boldsymbol {A}}={\begin{bmatrix}{\boldsymbol {B}}&{\boldsymbol {N}}\end{bmatrix}}$. Then ${\boldsymbol {x}}$ is given by

${\boldsymbol {x}}={\begin{bmatrix}{\boldsymbol {x_{B}}}\\{\boldsymbol {x_{N}}}\end{bmatrix}}={\begin{bmatrix}{\boldsymbol {B}}^{-1}{\boldsymbol {b}}\\{\boldsymbol {0}}\end{bmatrix}}$

where ${\boldsymbol {x_{B}}}\geq {\boldsymbol {0}}$. Partition ${\boldsymbol {c}}$ and ${\boldsymbol {s}}$ accordingly into

${\begin{aligned}{\boldsymbol {c}}&={\begin{bmatrix}{\boldsymbol {c_{B}}}\\{\boldsymbol {c_{N}}}\end{bmatrix}}{\text{,}}\\{\boldsymbol {s}}&={\begin{bmatrix}{\boldsymbol {s_{B}}}\\{\boldsymbol {s_{N}}}\end{bmatrix}}{\text{.}}\end{aligned}}$

To satisfy the complementary slackness condition, let ${\boldsymbol {s_{B}}}={\boldsymbol {0}}$. It follows that

${\begin{aligned}{\boldsymbol {B}}^{\mathrm {T} }{\boldsymbol {\lambda }}&={\boldsymbol {c_{B}}}{\text{,}}\\{\boldsymbol {N}}^{\mathrm {T} }{\boldsymbol {\lambda }}+{\boldsymbol {s_{N}}}&={\boldsymbol {c_{N}}}{\text{,}}\end{aligned}}$

which implies that

${\begin{aligned}{\boldsymbol {\lambda }}&={\boldsymbol {B}}^{-\mathrm {T} }{\boldsymbol {c_{B}}}{\text{,}}\\{\boldsymbol {s_{N}}}&={\boldsymbol {c_{N}}}-{\boldsymbol {N}}^{\mathrm {T} }{\boldsymbol {\lambda }}{\text{.}}\end{aligned}}$

If ${\boldsymbol {s_{N}}}\geq {\boldsymbol {0}}$ at this point, the KKT conditions are satisfied, and thus ${\boldsymbol {x}}$ is optimal.

Pivot operation

If the KKT conditions are violated, a pivot operation consisting of introducing a column of ${\boldsymbol {N}}$ into the basis at the expense of an existing column in ${\boldsymbol {B}}$ is performed. In the absence of degeneracy, a pivot operation always results in a strict decrease in ${\boldsymbol {c}}^{\mathrm {T} }{\boldsymbol {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.

Select an index $m<q\leq n$ such that $s_{q}<0$ as the entering index. The corresponding column of ${\boldsymbol {A}}$, ${\boldsymbol {A}}_{q}$, will be moved into the basis, and $x_{q}$ will be allowed to increase from zero. It can be shown that

${\frac {\partial ({\boldsymbol {c}}^{\mathrm {T} }{\boldsymbol {x}})}{\partial x_{q}}}=s_{q}{\text{,}}$

i.e., every unit increase in $x_{q}$ will results in a decrease by $-s_{q}$ in ${\boldsymbol {c}}^{\mathrm {T} }{\boldsymbol {x}}$. Since

${\boldsymbol {Bx_{B}}}+{\boldsymbol {A}}_{q}x_{q}={\boldsymbol {b}}{\text{,}}$

${\boldsymbol {x_{B}}}$ must be correspondingly decreased by $\Delta {\boldsymbol {x_{B}}}={\boldsymbol {B}}^{-1}{\boldsymbol {A}}_{q}x_{q}$ subject to ${\boldsymbol {x_{B}}}-\Delta {\boldsymbol {x_{B}}}\geq {\boldsymbol {0}}$. Let ${\boldsymbol {d}}={\boldsymbol {B}}^{-1}{\boldsymbol {A}}_{q}$. If ${\boldsymbol {d}}\leq {\boldsymbol {0}}$, no matter how much $x_{q}$ is increased, ${\boldsymbol {x_{B}}}-\Delta {\boldsymbol {x_{B}}}$ will stay nonnegative. Hence, ${\boldsymbol {c}}^{\mathrm {T} }{\boldsymbol {x}}$ can be arbitrarily decreased, and thus the problem is unbounded. Otherwise, select an index $p=\operatorname {argmin} _{1\leq i\leq m}\{x_{i}/d_{i}\mathop {|} 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 ${\boldsymbol {A}}_{p}$ with ${\boldsymbol {A}}_{q}$ in the basis.

Notes and references

Bibliography

• 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. {{cite book}}: Invalid |ref=harv (help)