Simplex-Type Algorithms

Tamas Terlaky

ABSTRACT

Although interior-point methods (IPMs) have polynomial complexity, simplex-type methods - originally developed by Dantzig - are still one of the most efficient algorithms to solve linear programming problems. In many situations, simplex methods compete favorably with IPMs, especially when they are embedded in branch-and-cut schemes to solve combinatorial and integer optimization problems. In this paper a short introduction to the theory of simplex algorithms is given. Some implementation issues, first-phase strategies, and a brief overview of state-of-the-art implementations is given as well.