The Many Guises of Linear Programming

This is a survey on linear programming. However, this is not a survey of a single approach to linear programming, but rather of two distinct approaches: the simplex method and interior point methods based on the log-barrier technique. These two topics are in fact extremely vast, and a survey such as this can only provide a glimpse of the huge edifice known as linear programming. Our approach here is unconventional since instead of viewing linear programming as a stand-alone subject, we examine it through the lens of convex programming. This allows us additional insights that are not part of the traditional discourse of linear programming. The approach to the simplex method given in this survey is credited to Manfred Padberg. The freshness of his approach is that it is tableau-free and has a non-linear programming flavor of using a rank-one update of a basic feasible matrix if it is not optimal. We also provide a very simple proof of the strong duality theorem for linear programming due to J. E. Martinez-Legaz. In this chapter we have an extensive discussion on the KKT conditions for linear programming problems with detailed proofs. The convex programming approach will be readily apparent in the discussion of the interior point methods. The chapter also contains the author’s personal experience of learning linear programming, beginning with an aversion to the tableau approach and progressing to a profound appreciation for the Padberg and interior point methods.