The Dual Simplex Method
The Dual Simplex method is a variant of the Simplex method for solving Linear Programming (LP) problems. While the classical Simplex algorithm maintains primal feasibility and improves the objective value, the Dual Simplex method follows the opposite strategy: it maintains dual feasibility while iteratively restoring primal feasibility.
This complementary perspective makes the Dual Simplex method particularly effective in reoptimization settings and in modern Mixed-Integer Linear Programming (MILP) solvers.
Core Idea and Algorithmic Principle
The Dual Simplex method operates on a basis that satisfies the dual feasibility conditions but may violate primal feasibility. This situation typically arises when some basic variables take values outside their allowed bounds.
At each iteration, the algorithm selects a basic variable that violates feasibility and removes it from the basis. A nonbasic variable is then chosen to enter the basis in a way that preserves dual feasibility. This pivot operation adjusts the solution while moving it closer to primal feasibility.
The process continues until all variables satisfy their bounds, at which point the solution is both primal and dual feasible and therefore optimal.
Like the classical Simplex method, the Dual Simplex method progresses through adjacent basic solutions, but the direction of improvement differs. Instead of improving the objective at each step, it maintains dual optimality while correcting infeasibilities.
Comparison with Other LP Methods
The Dual Simplex method is closely related to the primal Simplex method, and both rely on pivot operations on a simplex tableau. The key distinction lies in which feasibility conditions are maintained during the iterations.
Compared to Interior-Point methods, which traverse the interior of the feasible region, both primal and dual Simplex methods operate on the boundary of the feasible polytope.
In practice, modern solvers often switch between primal and dual Simplex depending on the problem structure and the type of modifications applied during the solution process.
Role in Modern Optimization Solvers
The Dual Simplex method is widely used in large-scale optimization due to its efficiency in reoptimization scenarios. In Branch-and-Bound and Branch-and-Cut algorithms, many closely related LPs must be solved repeatedly as constraints are added or modified.
Dual Simplex is particularly well-suited to this setting because it can reuse information from previous solutions and quickly restore feasibility. As a result, it is often the default LP solver within modern MILP implementations.
Further Reading and References
Dantzig, G. B. (1963). Linear Programming and Extensions. Princeton University Press.
A classic reference covering both primal and dual simplex methods and their theoretical foundations.
Bertsimas, D., & Tsitsiklis, J. N. (1997). Introduction to Linear Optimization. Athena Scientific.
A modern textbook providing a clear presentation of the dual simplex method and its role in linear programming.
Vanderbei, R. J. (2014). Linear Programming: Foundations and Extensions (4th ed.). Springer.
A comprehensive reference discussing simplex variants, including dual simplex, and their implementation in solvers.