The Primal-Dual Algorithm

18.433 Combinatorial Optimization The Primal-dual Algorithm October 28 In this lecture, we introduce the complementary slackness conditions and use them to obtain a primal-dual method for solving linear programming. 1 Complementary Slackness As we have seen before, using strong duality, we know that the optimum value for the following two linear programming are equal, i.e. u = w, if they are both feasible. u = max{cT x : Ax ≤ b, x ≥ 0} (P ) w = min{bT y : AT y ≥ c, y ≥ 0} (D) Using the above result, we can check the optimality of a primal and/or a dual solution. Theorem 1. Suppose x and y are feasible solutions to (P ) and (D). Then x and y are optimal if and only if the following conditions are satisfied:
∀i (bi − aij xj )yi = 0; j ∀j (
aij yi − cj )xj = 0. i Proof. First, we note that since x and y are feasible (bi −  j aij xj )yi ≥ 0 and (  cj )xj ≥ 0. By summing over i and j, we have:

(bi − aij xj )yi ≥ 0 i (1) (2) i By adding 1 and 2 and using the strong duality theorem





bi yi − aij xj yi + aij yi xj − cj xj = bi yi − cj xj = 0. i i,j − j

( aij yi − cj )xj ≥ 0 j i aij yi j,i j i j Therefore, all our inequalities must be equalities and we obtain the desired result. 1 2 Primal-dual algorithm The main implication of Theorem 1 is that if x and y are feasible and satisfy the complementary slackness conditions, then they are optimal. This result leads us to the primal-dual algorithm in which we start with a feasible solution x and y and try to satisfy the conditions more and more. For the sake of convenience, we consider the primal and dual programs as follows: min{cT x : Ax = b, x ≥ 0} (P ) max{bT y : AT y ≤ c} (D) In this form, the complementary slackness conditions that we need to satisfy are reduced to: ∀j (cj −
aij yi )xj = 0. (3) i The steps of the primal-dual algorithm are as follows: 1. Start with a feasible solution y for (D). Obtaining such feasible solution y is easier than solving the linear program in many cases.  Let J = {j : i aij yi = cj }. Now using 3, we need to obtain a solution x for (P ) such that ∀j ∈ J, xj = 0. So the question is whether there is a feasible solution x with this property. 2. Formulate the restricted primal (RP) as follows: min ∀i
m
Xi i=1 aij xj + Xi = bi j∈J Xi , xj ≥ 0 ∀j ∈ J, xj = 0 In fact, (RP ) formulates the problem of finding feasible solution x with the afore mentioned property. Here variables Xi ’s are artificial variables and if min m i=1 Xi is equal to zero, then xj ’s are optimal solutions to (P ). 2 3. If Opt(RP ) = 0 then x and y are optimal. Otherwise Opt(RP ) > 0 and we write the dual of (RP), namely (DRP), for which we get solution y. max
∀j ∈ J m
bi yi i=1 aij yi ≤ 0 i yi ≤ 1 4. Improve the solution to (D) by setting y  = y +
y. Here we determine
such that    y  is feasible and i bi yi > i bi yi . For feasibility, we must satisfy the condition     ∀j i aij yi ≤ cj . For j ∈ J, we must have i aij yi +
i aij y i ≤ cj . Since ∀j ∈  J i aij y i ≤ 0,
can be arbitrary positive for j ∈ J. Thus by taking
= min{j∈J s.t.  cj − i aij yi  i aij y i >0} i aij y i P we obtain our
> 0 such that y  is feasible. Also since Opt(DRP ) = Opt(RP ) > 0 and
> 0,
bi yi = i
bi yi +
i
bi y i >
i bi yi . i We note that in the above primal-dual algorithm, solving (DRP ) is usually easier than solving (P ) or (D). In fact, in this approach, programs (P ) and (RP ) are temporary programs and we want to solve (D). To this end, we first solve (DRP ) and then use the solution to improve y iteratively. 2.1 Example Consider the following formulation of the max-flow problem: 3
xsj − j f−
max f xjs − f ≤ 0 j
xjt + j ∀i = s, t

xtj ≤ 0 j xij −
j xji ≤ 0 j xij ≤ uij −xij ≤ 0 It is worth mentioning that in the original max-flow formulation, the first three sets of constraints are equalities. However in our new formulation by summing these three sets of inequalities, we get 0 ≤ 0 and thus these weaker sets of inequalities imply the equalities. Now, we consider the above formulation as (D). One feasible solution to (D) can be obtained by taking x as a zero vector. Now if we go directly to (DRP ) we have:
xsj − j f−
maxf xjs − f ≤ 0 j
xjt + j ∀i = s, t

xtj ≤ 0 j xij − j
xji ≤ 0 j xij ≤ 0 ∀i, j where xij = uij in (D) −xij ≤ 0 ∀i, j where xij = 0 in (D) xij ≤ 1 f ≤1 We can observe that (DRP ) has the following interpretation. Find a path from s to t (with a flow of value 1) that uses only the following arcs in the following ways: saturated arcs in the backward direction; arcs with zero flow in the forward direction; and other arcs in either direction. In other words, we need to find a path in the residual graph. This observation shows that the max-flow algorithm is in fact a primal-dual algorithm. 4 Finally, we note that primal-dual algorithms do not have polynomial running time guarantees. 5