4. LP Duality and Complementary Slackness

Linear programs always come in pairs. Every LP \(P\) has an associated LP \(D\) called its dual. If \(P\) is a maximization LP, then \(D\) is a minimization LP. These two LPs have the remarkable property that any feasible solution of \(P\) has an objective function value that is no greater than the objective function value of any feasible solution of \(D\). What's more, any optimal solution of \(P\) has exactly the same objective function value as any optimal solution of \(D\).

This relationship between an LP and its dual has many applications. First, we can use it to verify that a given solution of an LP is optimal. We will use this approach to prove that the Simplex Algorithm is correct, that the solution it produces is indeed an optimal solution of its input LP. Second, when designing approximation algorithms, we can often consider the LP formulation of the problem we are trying to solve and construct a feasible solution of the dual LP whose objective function value differs from the solution produced by our algorithm by only a small factor. This then proves that the solution produced by our algorithm is a good approximation of an optimal solution for the given problem instance. This technique is called dual fitting and will be discussed in Chapter 11. Third, and probably most importantly, there exists an algorithmic technique, called the primal-dual schema, which focuses on simultaneously finding optimal solutions to an LP and its dual. We will see numerous examples of this technique, for finding maximum flows in Section 5.2, for finding minimum-weight perfect matchings in Section 7.5, and for designing approximation algorithms in Chapter 12.

This chapter is organized as follows:

• Section 4.1 introduces the concept of the dual and proves that the optimal solutions of an LP and its dual always have the same objective function value.

• In Section 4.2, we use this to prove that the Simplex Algorithm does indeed output an optimal solution of its input LP. To do this, we explicitly construct a solution of the dual with the same objective function value as the solution output by the Simplex Algorithm.

• Section 4.3 introduces complementary slackness. Instead of directly comparing the objective function values of the solutions of an LP and its dual, complementary slackness focuses on how these solutions interact with the constraints in their respective LPs and uses these interactions to confirm that these solutions are optimal. Complementary slackness is the basis for the primal-dual schema mentioned above.

• In Section 2.5.2, we claimed that the LP relaxation of the ILP formulation of the minimum spanning tree problem given there has an integral optimal solution, but we lacked the tools to prove this. Complementary slackness is the tool we need to complete this proof, so we we prove this claim in Section 4.4 as one application of complementary slackness. You will see many more applications of this technique throughout the rest of this book.

• The concept of LP duality applies to LPs in canonical form. When using LP duality to reason about the correctness of numerous optimization algorithms, however, the LPs that arise are not in canonical form. A perfectly correct way to obtain the duals of such non-canonical LPs is to first convert them into canonical form—remember, by Lemmas 2.11 and 2.12, this is always possible—construct the dual, and then "convert the dual back". I encourage you to do this with a few non-canonical LPs until you are comfortable with duality, but overall, this is a rather tedious method to construct the dual of a non-canonical LP. Section 4.5 discusses how to obtain the dual of an arbitrary LP, one not necessarily in canonical form.