Interior-point methods for linear programming: A guided tour

The purpose of mathematical programming, a branch of optimization, is to minimize (or maximize) a function of several variables under a set of constraints. This is a very important problem arising in many real-world situations (e.g. cost or duration minimization). When the function to optimize and its associated set of constraints are linear, we talk about linear programming. The simplex algorithm, first developed by Dantzig in 1947, is a very efficient method to solve this class of problems. It has been thoroughly studied and improved since its first appearance, and is now widely used in commercial software to solve a great variety of problems (production planning, transportation, scheduling, etc.). However, an article by Karmarkar introduced in 1984 a new class of methods: the so-called interior-point methods. Most of the ideas underlying these new methods originate from the nonlinear optimization domain. These methods are both theoretically and practically efficient, can be used to solve large-scale problems and can be generalized to other types of convex optimization problems. The purpose of this article is to give an overview of this rather new domain, providing a clear and understandable description of these methods, both from a theoretical and a practical point of view.