6.5.1. The Primal-Dual Schema

The right way to define what an "optimal" infeasible solution (a preflow in preflow-push algorithms, a pseudo-flow in the successive shortest paths algorithm) is to look at the problem through the lens of LP duality and complementary slackness. Both preflow-push algorithms and the successive shortest paths algorithm introduced in this section maintain a possibly infeasible primal solution—the preflow or pseudo-flow—and a feasible dual solution—a height or potential function of the vertices. At all times, the two solutions satisfy the primal complementary slackness conditions. It is in this sense that we consider the preflow or pseudo-flow to be optimal. As the algorithm progresses, it maintains primal complementary slackness while moving the primal solution towards feasibility, and it maintains that the dual solution is feasible while moving it towards optimality. At the end of the algorithm, both primal and dual solutions are feasible and satisfy complementary slackness. Thus, they are optimal solutions.

If an algorithm takes this approach of maintaining an infeasible but optimal primal solution and a feasible dual solution, and then gradually moving the primal towards feasibility while maintaining its optimality, it is said to use the primal-dual schema:

Every algorithm for some problem based on the primal-dual schema has the following characteristics:

• It maintains a primal solution of the LP formulation of the problem and a dual solution of the dual of the LP formulation.

• The dual solution is feasible at all times.

• The primal solution may be infeasible but is optimal in the sense that it satisfies some optimality criterion relative to the current dual. This criterion is often complementary slackness but can also be some problem-specific optimality criterion that is easier to work with.¹

• The algorihm iteratively updates the primal and dual solutions to move the primal towards feasibility while maintaining the optimality of the primal and the feasibility of the dual.

• Once both primal and dual are feasible, they are feasible optimal solutions because they satisfy the optimality criterion.

By the following exercise, preflow-push algorithms are indeed applications of the primal-dual schema:

Exercise 6.5: Consider the LP formulation of the maximum flow problem and its dual. Our goal is to prove the correctness of the preflow-push algorithms. Prove that a preflow \(f\) is a solution of the primal LP, and the height function \(h\) used in the algorithm is a solution of the dual LP, satisfying the following conditions:

• The initial preflow satisfies primal complementary slackness; the initial height function is a feasible dual solution.

• Every Push or Relabel operation maintains primal complementary slackness and the feasibility of the height function as a solution of the dual LP.

• When the algorithm terminates, the flow \(f\) is a feasible primal solution, the height function is a feasible dual solution, and \(f\) and \(h\) satisfy both primal and dual complementary slackness.

Next, we introduce the successive shortest paths algorithm for computing a minimum-cost flow and discuss that it is another application of the primal-dual schema.