2. Linear Programming

Linear programming (LP), as a tool for modelling optimization problems and as an algorithmic problem to be solved efficiently, can easily fill an entire course. Since this course focuses mainly on combinatorial algorithms for a wide range of problems, we do not cover LP in much depth. However, many of the problems discussed in this course have elegant LP or integer linear programming (ILP) formulations that shed light on the structure of the problems, and some of the developed algorithms use linear programming as a building block. Thus, a basic understanding of LP and ILP and of the basic techniques to solve LP and ILP problems is important for later topics covered in this course.

The discussion of LPs is split into three parts. In this chapter, we introduce what linear programs and integer linear programs are, and how to use them to model optimization problems. Chapter 3 introduces a classical algorithm for solving linear programs, the Simplex Algorithm. The proof of correctness of this algorithm is deferred to Chapter 4, which introduces LP duality and complementary slackness as two central tools for proving that a given solution of an LP is optimal.

The roadmap for this chapter is as follows:

• Section 2.1 defines what a linear program is.

• Section 2.2 illustrates the use of linear programs to model optimization problems using the single-source shortest paths problem as an example.

• Section 2.3 introduces integer linear programming and illustrates its usefulness as a tool for modelling optimization problems by showing how to convert the minimum spanning tree problem into an ILP.

• Section 2.4 explores the computational complexity of linear programming and integer linear programming. Linear programs can be solved in polynomial time, often even if they have an exponential number of constraints. Integer linear programming, on the other hand, is NP-hard. This raises the question whether we can use the tools to solve linear programs efficiently also to obtain good, albeit not optimal, solutions of ILPs.

• Section 2.5 discusses LP relaxations as a way to convert an ILP into a related LP. LP relaxation plays an important role in approximation algorithms, discussed in the third part of this book.

• Section 2.6 finally, discusses two commonly used forms of linear programs. One of them—canonical form—plays a key role in the theory of LP duality. The other—standard form—is the input expected by the Simplex Algorithm.