Class Notes
(807,450)

Canada
(492,626)

University of Waterloo
(18,164)

Computer Science
(752)

CS 251
(3)

Uzma Rehman
(1)

Lecture

# extra.pdf

Unlock Document

University of Waterloo

Computer Science

CS 251

Uzma Rehman

Fall

Description

Chapter A
Duality through examples
In this chapter we will consider two classical optimization problems, namely the problem of
ﬁnding a shortest path between a ﬁxed pair of vertices in an undirected graph and the the prob-
lem of ﬁnding a minimum cost perfect matching in a bipartite graph. These two optimization
problems were introduced in Chapter 1. We will present efﬁcient algorithms for both these
problems and show in the process that the natural framework for understanding these prob-
lems is the theory of linear programming duality. This theory will be further developed in
Chapter B.
A note to the reader, Section A.1 on shortest paths, and Section A.2 on minimum cost
perfect matchings are independent and introduce the same basic concepts of duality theory.
Moreover, the material in these sections is not essential for the remainder of the book. Hence,
it is possible for the reader to focus on one of these two sections only.
A.1 The shortest path problem
Recall the shortest path problem from Chapter 1. We are given a graph G =( V,E), non-
negative lengths e for all edges e ▯ E, and two distinct vertices s,t ▯ V. An st-path P is a
sequence of edges
v1 2,v2 3,...,k▯2 k▯1 ,vk▯1 k
such that 1 = s, k =t, and i ▯= j for all i ▯= j. The length c(P) of an st-path is deﬁned as the
sum of the length of the edges of P, i.e▯ (e : e ▯ P). We wish to ﬁnd among all possible
st-paths, one that is of minimum length.
1 A.1. THE SHORTEST PATH PROBLEM 2
Example 4. In the following ﬁgure we show an instance of this problem. Each of the edges
in the graph is labeled by its length. The thick black edges in the graph form an st-path
P = sa,ac,cb,bt of total length 3+1+2+1 = 7. This st-path is of minimum length, hence
is a solution to our problem.
a b
4
3 1
s 1 2
t
2
4
c 2
d
A.1.1 An intuitive lower bound
We claimed in the previous example that the path P = sa,ac,cb,bt of length 7 is a shortest
st-path. How could you convince someone of that fact? Of course we could list all possible
st-paths and verify that P is indeed a shortest one. This is not a practical way of proceeding
however, as we may have a huge (exponential) number of such st-paths. Our goal in this
section is to ﬁnd a certiﬁcate that can be used to quickly convince someone that a shortest st-
path is indeed shortest. Note, such a certiﬁcate is not only desirable for the user of a shortest
path algorithm but it is also essential for designing such an algorithm.
We will prove that the path P in Example 4 is indeed a shortest st-path. However, before
we do so it will be helpful to ﬁrst consider the special case of the shortest st-path problem
where all edges e have edge length c = e. In that case we are looking for an st-path with as
few edges as possible. We refer to this case as the cardinality case. Consider the following
graph G =(V,E),
a b c
d
h
s t
j i g
Let us show that the path P = sj, ji,ig,gt is a shortest st-path of G. It has length 4. To show
that it is a shortest path, it sufﬁces to show that every st-path has length at least 4. To do this
▯Department of Combinatorics and Optimization, University of Waterloo Winter2012 CHAPTER A. DUALITY THROUGH EXAMPLES 3
we exhibit the following collection of st-cuts (see the next ﬁgure),
▯(U 1= {sa,sj} ▯(U )2 {ab,ah,ij}
▯(U )= {bc,hc,ig} ▯(U )= {dt,gt}.
3 4
where,
U 1 {s}, U 2 {s,a, j}, U 3 {s,a, j,b,h,i}, and U4=V \{t}.
Observe, that no two of these st-cuts share an edge. Let Q be an arbitrary st-path. We know
from Theorem 1 that every st-path and st-cut have a common edge. Hence, Q must contains
an edge e if ▯(U ),ifor i = 1,2,3,4. Since these st-cuts are disjoint, e ,e 1e ,2 a3e 4istinct
edges. In particular, Q contains at least 4 edges. As Q was an arbitrary st-path, every st-path
contains at least 4 edges. It follows that P = sj, ji,ig,gt is a shortest st-path of G. The
a b c
d
h
s t
▯(U1) ▯(4 )
j i g
▯(U2) ▯(U3)
collection of st-cuts ▯(U )i(i = 1,2,3,4) is our certiﬁcate of optimality. More generally, if a
graph has k pairwise disjoint st-cuts then every st-path has length at least k and any st-path
with k edges is a shortest st-path.
Let us now go back to the problem where the edges e of G can have arbitrary lengths
ce▯ 0. Rather than selecting a subset of st-cuts as in the cardinality case, we will assign to
1
every st-cut ▯(U), a non-negative number y U that we call the width of the st-cut ▯(U). We
say that the widths {y U :U ▯V,s ▯U,t ▯ / U} are feasible if they satisfy,
Feasibility condition: For every edge e ▯ E,
The total width of all st-cuts that contain e does not exceed the length of e. (A.1)
1while it might be more natural to use the nota¯ion to denote the width of the st-cut ▯(U) the notation
▯(U)
¯Uis more compact while being unambiguous.
▯Department of Combinatorics and Optimization, University of Waterloo Winter2012 A.1. THE SHORTEST PATH PROBLEM 4
Example 4, continued. We assign the following widths for the graph G in Example 4.
¯U = 3 ¯ yU = 1
1 2
¯ = 2 ¯ y = 1
U3 U4
where
U 1 {s}, U 2 {s,a}, U 3 {s,a,c}, and U 4 {s,a,c,b,d}.
The other st-cuts are assigned a width of zero. The non-zero widths are represented in the
following ﬁgure. We claim that the widths are feasible. Let us check the condition for edge
yU2 =1
a b
4
3 1
1 2
s t
4 2
y =3
U1 c 2 d y =1
yU3=2 U4
ab for instance. The two st-cuts that have non-zero width and that contain ab are ▯(U ) a2d
▯(U 3 which have respectively width y ¯U1 = 1 and y¯U2 = 2. Thus the total width of all st-cuts
that contain the edge ab is 1+2 = 3 which does not exceed the length c ab = 4 of ab. We leave
it as an exercise to verify the feasibility condition for every other edge of the graph.
Suppose now we have an graph G =(V,E) (with s,t ▯V and c ▯ 0 foreall e ▯ E) that has
feasible widths. Let Q denote an arbitrary st-path. By the feasibility condition, for every edge
e of Q, the total width of all st-cuts using e is at mostec . It follows that the total width of all
st-cuts using some edge of Q is at most ▯ (ce: e ▯ Q), i.e. the length of Q. We know however
from Theorem 1 that every st-cut of G contains some edge of Q. Hence, the length of Q is at
least equal to the total width of all st-cuts. We summarize this result,
Proposition 15 (Optimality Conditions for Shortest Paths). If the widths are feasible, then the
total width of all st-cuts is a lower bound on the length of any st-path. In particular, if an
st-path has length equal to the total width of all st-cuts, then it is a shortest st-path.
Example 4, continued. We can now prove that the path P = sa,ac,cb,bt is a shortest st-path.
We found a set of feasible widths, with total width,
yU 1+y U 2+y U 3+y U 4= 3+1+2+1 = 7.
▯Department of Combinatorics and Optimization, University of Waterloo Winter2012 CHAPTER A. DUALITY THROUGH EXAMPLES 5
As c(P)= 7, it follows from Proposition 15 that P is a shortest st-path.
The arguments used to prove Proposition 15 are fairly elementary. We will see however,
that this result is surprisingly powerful. Indeed we will be able to design an efﬁcient algo-
rithm based on this optimality condition. Deriving good optimality conditions is a key step in
designing an algorithm.
A.1.2 A general argument - weak duality
We used an Ad hoc argument argument to obtain Proposition 15. At a ﬁrst glance it is not
obvious at all where the idea of assigning width to st-cuts arises from. We will show however,
that it is a natural idea when we look at the problem through the lens of duality theory. In this
section, we derive a natural bound on the values a certain class of linear programs can obtain.
In Section A.1.3 we show that Proposition 15 is a direct consequence of that result.
Example 5. Consider the linear program
min{z(x)= c x : Ax ▯ b,x ▯ 0}, (A.2)
where ▯ ▯ ▯ ▯
21 20 ▯ ▯
A = ▯ 11 ▯ b = ▯ 18▯ c = 2 .
3
▯11 8
T T
It is easy to verify that the vectors (8,16) and (5,13) are all feasible for the linear pro-
gram (A.2). Their objective values are 64 and 49, respectively, and hence the ﬁrst feasible
solution is clearly not optimal. We will show however that (5,13) is an optimal solution by
proving that ¯) ▯ 49 for every feasible so¯.tion x
How can we ﬁnd (and prove) such a lower bound? Let us pick non-negative1va2ues y ,y
and y and create a new inequality by multiplying the ﬁrst inequality of Ax ▯ b by y , the
3 1
second inequality b2 y , the thi3d by y and by adding the resulting inequalities. This can be
expressed as y Ax ▯ y b or in this case,
▯ ▯ ▯ ▯
21 20
(y ,y ,y ) 11 ▯ x ▯ (y ,y ,y )18▯ . (A.3)
1 2 3 1 2 3
▯11 8
It is important to observe that we must require that y is non-negative in order to preserve the
direction of the inequalities. If we choose 1 = 0,¯2= 2 and ¯3= 1 we obtain the
inequality,
(1,3)x ▯ 44 or equivalently 0 ▯ 44▯(1,3)x.
▯Department of Combinatorics and Optimization, University of Waterloo Wint2012 A.1. THE SHORTEST PATH PROBLEM 6
This inequality holds for every feasible solution of (A.2). Adding this inequality to the objec-
tive function z(x) = (2,3)x yields,
z(x) ▯ (2,3)x+44▯(1,3)x = 44+(1,0)x.
Let¯ be any feasible soluti¯▯0 and (1,0)▯0 we have (1,0¯▯0. Hence, ¯)▯44.
Thus, we have proved that no feasible solution has value smaller than 44. Note, this is not
T
quite sufﬁcient to prove that (5,13) is optimal. It shows however, that the optimum value for
(A.2) is between 44 and 49. It is at most 49, as we have a feasible solution with that value,
and it cannot be smaller than 44 by the previous argument.
Let us search 1or2y3,y ,y ▯ 0 in a systematic way. We rewrite (A.3) as
▯ 20▯ ▯ 21 ▯
0 ▯ (1 ,2 3y )18▯ ▯(y1,2 ,3 ) 11 ▯ x
8 ▯11
and add it to the objective function z(x) = (2,3)x, to obtain,
▯ ▯ ▯ ▯ ▯▯
20 21
▯ ▯ ▯ ▯ ▯▯
z(x) ▯ 1y 2y3,y )8 + (2,3)▯(y 1y2,y3) 11 x. (A.4)
8 ▯11
Suppose that we pic1,2y 3y ,y ▯ 0 such that
▯ ▯
21
(2,3)▯(y1,y2,3 ) 11 ▯ ▯ 0 .
▯11
Then for any feasible so¯, inequality (A.4) and the fact that x ▯ 0 implies that
▯ ▯
20
▯ ▯
z¯) ▯ (1 2y 3y )8 .
8
For a minimization problem the larger the lower bound the better. Thus, the best possible
upper bound for (A.2) we can achieve using the above argument is given by the optimal value
▯Department of Combinatorics and Optimization, University of WaterlWint2012 CHAPTER A. DUALITY THROUGH EXAMPLES 7
to the following linear program,
▯ ▯
20
max (y1,y2,3 ) 18▯
8
subject to
▯ ▯
21
▯ ▯ T
(2,3)▯(y 1y2,y3) 11 ▯ 0
▯11
y1,y2,3 ▯ 0
which we can rewrite as,
max (20,18,8)y
subject to
▯ ▯ T
21 ▯ ▯ (A.5)
▯ 11 ▯ y ▯ 2
3
▯11
y ▯ 0.
Solving this linear program gives
5 1
y1 = 0,2 = , and¯3= ,
2 2
T
and this solution has objective value 49. Since solution (5,13) has value 49, it is optimal.
Let us generalize the previous argument and consider the following linear program,
min{c x : Ax ▯ b,x ▯ 0} (A.6)
We ﬁrst choose a vector y ▯ 0 and create a new inequality,
y Ax ▯ y b.
This last inequality is obtained from Ax ▯ b by multiplying the 1st in1quality by y ▯ 0 the
2nd by 2 ▯ 0 the 3rd by3y ▯ 0 etc, and by adding all of the resulting inequalities together.
This inequality can be rewritten as
T T
0 ▯ y b▯y Ax
▯Department of Combinatorics and Optimization, University of Waterloo Wint2012 A.1. THE SHORTEST PATH PROBLEM 8
which holds for every feasible solution ¯ of (A.6). Thus, adding this inequality to the objective
function z(x)= c x yields,
z(x) ▯ y b+c x▯y Ax = y b+(c ▯y A)x. T T (A.7)
Suppose that because of the choice of y, c ▯y A ▯ 0 . Let x ¯ be any feasible solution. As
¯ ▯ 0 we have that (c ▯y A)x ¯ ▯ 0. It then follows by (A.7) that z¯) ▯ y b. Thus, we have
shown that for all y ▯ 0 such that c ▯y A ▯ 0 the value y b is an lower bound on the
T T T
value of the objective function. Finally, note that the condition c ▯y A ▯ 0 is equivalent to
T T T
y A ▯ c , i.e. to A y ▯ c.
The best lower bound we can get in this way is the optimal value of
T T
max{b y : A y ▯ c,y ▯ 0}. (A.8)
Let us summarize our result and provide a more direct proof.
Theorem 16 (Weak Duality - Special form). Consider the following pair of linear programs,
T
min{c x : Ax ▯ b,x ▯ 0} (P)
max{b y : A y ▯ c,y ▯ 0} (D)
Let ¯ be a feasible solution for (P) and y¯ be a feasible solution for (D). Then c x ¯ ▯ b y¯.
Moreover, if equality holds then ¯ is an optimal solution for (P).
In the previous theorem we deﬁne (D) to be the dual of (P).
Proof of Theorem 16. Let x ¯ be a feasible solution of (P) and let¯ be a feasible solution (D).
Then
T T T T T T T
b y¯ = ¯ b ▯ y (Ax ¯) = (y A)x¯ =( A y¯) x¯ ▯ c ¯.
The ﬁrst inequality follows from the fact that ¯ ▯ 0 and that Ax¯ ▯ b. The second inequality
follows from the fact that A y¯ ▯ c and that ¯ ▯ 0. Finally, as b ¯ is a lower bound on (P), if
T T
c x¯ = b y¯ it follows tha¯ is optimal for (P).
A.1.3 Revisiting the intuitive lower bound
Suppose we are given a graph G =( V,E) with distinct vertices s,t and edge lengths c ▯ 0e
for every e ▯ E. The following is an Integer Programming formulation for the shortest st-path
▯Department of Combinatorics and Optimization, University of Waterloo Winter2012 CHAPTER A. DUALITY THROUGH EXAMPLES 9
problem (see Section 1.2.2),
▯ ▯
min ▯ ce e: e ▯ E
subject to
▯ ▯
▯ xe: e ▯ ▯(U) ▯ 1 (U ▯V,s ▯U,t ▯/ U) (A.9)
xe▯ 0 (e ▯ E)
xeinteger (e ▯ E)
Example 6. In the following ﬁgure we show a simple instance of the shortest path problem.
Each of the edges in the graph is labeled by its length.
a
3 2
1
s t
4 2
b
T
Let x :=(sa sb ab ,at,bt) . Then (A.9) specializes to the following in this case,
min (3,4,1,2,2)x
subject to
▯ sa sb ab at bt▯
{s} ▯ 1 1 0 0 0 ▯
▯ ▯ (A.10)
{s,a} ▯ 0 1 1 1 0 ▯
▯ ▯ x ▯ 1.
{s,b} ▯ 1 0 1 0 1 ▯
{s,a,b} 0 0 0 1 1
x ▯ 0 integer
Each of the ﬁrst 4 constraints correspond to one of the 4 distinct st-cuts ▯(U). For instance
the second constraint, corresponding to ▯({s,a})= {sb,ab,at}, ssbteabthaatx +x +x ▯ 1.
For an integer program (IP) we call the linear program, obtained by removing the condition
that some variables have to take integer values, the linear programming relaxation of (IP).
Consider an instance of the shortest path problem G =(V,E) with s,te▯ V and c ▯ 0 for all
▯Department of Combinatorics and Optimization, University of Waterloo Winte2012 A.1. THE SHORTEST PATH PROBLEM 10
e ▯ E. Suppose P is some arbitrary st-path of G. Then we can construct ¯ feasible solution x
to the integer program (A.9) as follows:
▯
▯
1 if e is an edge of P
xe =▯ (A.11)
0 otherwise.
Moreover, the length c(P) of the st-path P is equal ¯ for (A.9). It follows in
particular that c(P) is greater of equal to the optimal value of (A.9). Let (P) denote the linear
programming relaxation of (A.9). Since the constraints of (P) are a subset of the constraints
of (A.9) and since (A.9) is a minimization problem, the optimal value of (A.9) is greater or
equal to the optimal value of (P). Let (D) be the dual of (P). We know from the Weak duality
theorem 16 that the optimal value of (P) is greater or equal to the value of any feasible solution
¯ of (D). Hence, we have proved the following result,
Remark 17. If (D) is the dual of the linear programming relaxation of (A.9) then the value
of any feasible solution of (D) is a lower bound on the length of any st-path.
Example 6, continued. Let us compute the dual of the linear programming relaxation of (A.10),
as deﬁned in Theorem 16. Observe that by taking the dual we interchange the role of the
variables and the constraints. We now hav▯ Uafor each st-cut▯▯(U) and one con-
straint for each edge of G. Hence, let us deﬁ,y y,y= y,y T. The dual is
{s} {s,a}{s,b}{s,a,b}
given by,
max 1y
subject to
{s}{ s,a}{ s,b}{ s,a,b}
▯ ▯
sa 1 0 1 0 ▯ ▯
▯ ▯ 3
sb▯ 1 1 0 0 ▯ ▯ 4 (A.12)
▯ ▯ ▯ ▯
ab▯ 0 1 1 0 ▯ y ▯▯ ▯ .
▯ ▯ ▯ 2
at▯ 0 1 0 1 ▯ 2
bt 0 0 1 1
y ▯ 0
Note, a feasible solution to (A.12) assigns some non-nUgative width y to every st-cut ▯(U).
The constraint for edge sb stat{s}yh{s,a} 4. Observe that ▯({s})= {sa,sb} and
▯({s,a})= {at,ab,sb} are the two st-cuts of G that contain edge sb. Finally, 4 is the length
▯Department of Combinatorics and Optimization, University of WateWinte2012 CHAPTER A. DUALITY THROUGH EXAMPLES 11
of the edge sb. Hence the constrain{s}+y {s,a}▯ 4 says that the total width of all st-cuts of
G that contain edge sb does not exceed the length of sb. The corresponding condition holds
for every other edge. Hence, if y is feasible for (A.12) the widths y satisfy the Feasibility
Conditions (A.1). The objective function 1y calculates the total width of all st-cuts. Hence, it
follows from Remark 17 that if the width are feasible, then the total width of all st-cuts is a
lower bound on the length of any st-path. This was precisely the statement of Proposition 15.
Consider now a general instance of the shortest path problem. We are given a graph
G =( V,E), vertices s,t ▯ V, and lengths ce▯ 0 for all e ▯ E. We can rewrite the linear
programming relaxation of (A.9) as,
T
min{c x : Ax ▯ 1,x ▯ 0}, (A.13)
where c is the vector of edge lengths, and the matrix A is deﬁned as follows:
1. the rows of A are indexed by sets U ▯V with s ▯U,t / U,
2. columns are indexed by edges e ▯ E, and
3. for every row U and every column e:
▯
▯ 1 if e is an edge in ▯(U),
A[U,e]=
▯ 0 otherwise.
Remark 18.
(1) In row U of A, entries with a 1 correspond to the edges in ▯(U).
(2) In column e of A, entries with a 1 correspond to the st-cuts containing edge e.
The dual of (A.13), as deﬁned in Theorem 16, is given by,
max{1 y : A y ▯ c,y ▯ 0}. (A.14)
Let us try to understand this dual. There is a varUable y for every st-cut ▯(U) and a constraint
for every edge e ▯ E. Consider the constraint for edge e ▯ E. The right-hand side of this
constraint is the lengte c of the edge, and the left-hand side corresponds to column e of A.
▯Department of Combinatorics and Optimization, University of Waterloo Winte2012 A.1. THE SHORTEST PATH PROBLEM 12
Remark 18(2) implies that the left-hand side of this constraint is the sum of the variables y
U
over all st-cuts ▯(U) that contain e. We can therefore rewrite (A.14) as follows:
▯ ▯
max ▯ yU : ▯(U) is an st-cut
subject to
▯ ▯ (A.15)
▯ yU : ▯(U) is an st-cut containing e ▯ e (e ▯ E)
yU▯ 0 (▯(U) is an st-cut)
A feasible solution¯ to (A.15) assigns non-negative width U to every st-cut ▯(U). The
constraint for each edge e states that the total width of all st-cuts of G that contain edge e does
not exceed the length of e. Hence,¯ is feasible for (A.15) the wid¯ satisfy the Feasibility
Conditions (A.1). The objective function 1y calculates the total width of all st-cuts. Hence,
as in the previous example, it follows from Remark 17 that if the width are feasible, then the
total width of all st-cuts is a lower bound on the length of any st-path. Hence, we now have
an alternate proof for Proposition 15.
While the derivation of Proposition 15 using duality may, at ﬁrst glance, seem more tech-
nical than the ad-hoc argument we had in Section A.1.1, notice that our derivation was com-
pletely mechanical: We formulated the shortest path problem as an integer program, wrote
the dual of its linear programming relaxation, and used weak duality to obtain bounds on the
possible values of our original optimization problem. After generalizing the notion of duals
in Chapter B, we will be able to apply the aforementioned strategy to arbitrary optimization
problems that can be formulated as integer programs. The success of such a strategy will
depend on the quality of the linear programming relaxation.
A.1.4 An algorithm
We will present an algorithm to solve the shortest path problem based on the optimality condi-
tions given in Proposition 15. Before we do so, however, we require a number of deﬁnitions.
We will need to generalize our deﬁnition of a graph G =(V,E) by allowing both edges and
arcs. Recall that an edge is an unordered pair of vertices. We call an ordered pair of vertices,
say uv, an arc. Vertex u is the tail of uv and vertex v is the head of uv. We represent an arc as
an arrow going from the tail of the arc to the head of the arc. A directed st-path is a sequence
of arcs,
v1 2,v2 3,...,vk▯2 k▯1,vk▯1 k
▯Department of Combinatorics and Optimization, University of Waterloo Winte2012 CHAPTER A. DUALITY THROUGH EXAMPLES 13
such that v1= s, vk= t and v i= v fjr all i ▯= j. In other words a directed st-path is an st-path
in the graph obtained by ignoring the orientation, with the additional property that for any two
consecutive arcs, the head of the ﬁrst arc, is the tail of the second arc. The following ﬁgure
gives an example of a graph with both edges and arcs. The thick arcs form a directed st-path.
a b
c d
t
g s
Consider now a general instance of the shortest path problem. We are given a graph
G =( V,E), vertices s,t ▯ V, and lengths c ▯ 0 for all e ▯ E. Suppose that y ¯ is a feasible
e
solution to (A.15). In other words every st-cut ▯(U) has a non-negative width y ¯U▯ 0 and the
Feasibility Condition (A.1) holds, namely, for every edge e the total width of all st-cuts using
e is smaller or equal to the length of e. We deﬁne the slack of edge e for¯ to be the quantity,
▯ ▯
slack (e) := c ▯ y¯ : ▯(U) is an st-cut containing e .
y¯ e ▯ U
In other words, slacky¯e) is the length of e minus the total width of all st-cuts using e.
2
We are now ready to describe our algorithm.
Algorithm 1 Shortest-path.
Input: Graph G =(V,E), costs c ▯ 0 eor all e ▯ E, s,t ▯V where s ▯= t.
Output: A shortest st-path P
1: yW := 0 for all st-cuts ▯(W). Set U := {s}
2: while t ▯▯U do
3: Let ab be an edge in ▯(U) of smallest slack for y¯ where a ▯U, b ▯ / U
4: ¯U:= slack (y¯)
5: U :=U ▯{b}
6: change edge ab into an arc ab
7: end while
8: return A directed st-path P.
2We will assume that at least one st-path exists in the graph G.
▯Department of Combinatorics and Optimization, University of Waterloo Winter2012 A.1. THE SHORTEST PATH PROBLEM 14
Example 7. Consider the shortest path problem described in Figure A.1(i). We star¯=0ith y
yU=1
yU=2 y U1
s 6 a s 6 a s 6 a
1 1 1
4 c 4 c 4 c
2 4 2 4 2 4
2 2
1 1 1 2
5 5 5
b t b t b t
(i) (ii) (iii)
s a s a
6 6
1
4 1 4
yU=1 c c
2 4 2 4
1 2 1 2
b 5 t b 5 t
(iv) (v)
Figure A.1: Shortest path algorithm - an example.
and U = {s}. We compute the slack of the edges in ▯({s}),
slacky¯sa)= 6, slacky¯sb)= 2, slacy¯(sc)= 4,
and therefore sb is the edge in ▯({s}) of smallest slack¯. We let y{s}= 2, we set U :=
{s,b} and change edge sb into an arc sb. See ﬁgure (ii).
Since t/ U = {s,b} we compute the slack of the edges in ▯({s,b}),
slacky¯sa)= 6▯y {s}= 6▯2 = 4
slacky¯sc)= 4▯y {s}= 4▯2 = 2
slacky¯bc)= 1
slacky¯bt)= 5,
and therefore bc is the edge in ▯({s,b}) with smallest slack ¯. We let¯{s,b} 1, we set
U = {s,b,c} and change edge bc into an arc bc. See ﬁgure (iii).
c
▯Department of Combinatorics and Optimization, University of Waterloo Winte2012 CHAPTER A. DUALITY THROUGH EXAMPLES 15
Since t / U = {s,b,c} we compute the slack of the edges in ▯({s,b,c}),
slack y¯a)= 6▯y {s}▯y {s,b}= 6▯2▯1 = 3
slack y¯a)= 1
slacky¯ct)= 2
slacky¯bt)= 5▯y {s,b}= 5▯1 = 4,
and therefore ca is the edge in ▯({s,b,c}) with smallest slack for y¯. We let ¯{s,b,c} 1, we set
U = {s,b,c,a} and change edge ca into an arc ca. See ﬁgure (iv).
Since t / U = {s,b,c,a} we compute the slack of the edges in ▯({s,b,c,a}),
slacky¯at)= 4
slack (ct)= 2▯y = 2▯1 = 1
y¯ {s,b,c}
slack (bt)= 5▯y ▯y = 5▯1▯1 = 3,
y¯ {s,b} {s,b,c}
and therefore ct is the edge in ▯({s,b,c,a}) with smallest slack for y¯. We let ¯ = 1, we
{s,b,c,a}
set U = {s,b,c,a,t} and change edge ct into an arc ct. See ﬁgure (v). Note, now that t ▯ U
and there exists a directed st-path P, namely P = sb,bc,ct. It can be readily checked that y ¯
are feasible width. Moreover, the total width of all st-cut is equal to 2+1+1+1 = 5 and the
length c(P) of P is equal to 2+1+2 = 5. It follows from Proposition 15 that P is a shortest
st-path.
We will prove that this simple algorithm is guaranteed to always ﬁnd a shortest st-path in
the next section. Suppose after running the algorithm and ﬁnding a shortest path P we deﬁne
variables x¯ as in (A.11). Then x¯ is a feasible solution to the linear program (A.9) and y ¯ is a
feasible solution to the dual linear program (A.15). Moreover, we will see that the algorithm
will guarantee that the total width of all st-cuts is equal to the length of the shortest st-path.
In other words that the value of x ¯ in (A.9) is equal to the value ¯ in (A.15). It follows from
Weak Duality (Theorem 16), that x ¯ is an optimal solution to (A.9). Hence, correctness of the
algorithm will imply the following result,
Theorem 19. If c ▯ e for all e ▯ E then the linear program (A.9) has an optimal solution
that is an integer solution.
Note that our shortest path algorithm preserves at each step a feasible solution to the dual
linear program (A.15). This is an example of a dual algorithm.
▯Department of Combinatorics and Optimization, University of Waterloo Winter2012 A.1. THE SHORTEST PATH PROBLEM 16
A.1.5 Correctness of the algorithm
Consider a graph G =( V,E) with distinct vertices s,t ▯ V and lengthsec ▯ 0 for all e ▯ E.
Suppose that ¯ is a feasible solution to (A.15). We say that an edge (resp. an arc) uv is an
equality edge (resp. arc) if its slack ¯ is zero, i.e. if sy¯ck (uv)= 0. We say that an cut
▯(U) is active for¯ i¯U> 0.
We shall ﬁrst reﬁne our optimality condition given in Proposition 15.
Proposition 20. Let ¯ be feasible widths and let P be an st-path. Then P is a shortest st-path
if both of the following conditions hold:
(P1) all edges of P are equality edges f¯, y
(P2) all active cuts f¯ contain exactly one edge of P.
Proof. Suppose that P is an st-path that satisﬁes both (P1) and (P2) for feasible ¯. For y
every edge e of P, denote by e the set of all active st-cuts that contain edge e. To prove that
P is a shortest path it sufﬁces (because of Proposition 15) to verify that the following relations
hold,
▯ ▯
Total width of st-cuts = y : ▯(U) is an active st-cut
▯ U
(a) ▯ ▯ ▯▯
= ▯ ▯ yU : ▯(U) ▯ Ce
e▯P
(b)
= ▯ ce= length of P.
e▯P
Finally, note that (a) holds because (P2) and that (b) holds because (P1).
Note that the algorithm is guaranteed to terminate after at most |V| iterations since at every
step one vertex is added to the setU. Hence, to show that the algorithm is correct it will sufﬁce
to verify the following result,
Proposition 21 (Correctness of Shortest Path algorithm).
In STEP 8 a directed st-path P exists and it is a shortest st-path.
Proof. Consider the following properties:
(I1) ¯ are feasible width,
▯Department of Combinatorics and Optimization, University of Waterloo Winte2012 CHAPTER A. DUALITY THROUGH EXAMPLES 17
(I2) all arcs are equality arcs fo¯,y
(I3) there is no active cut ▯(U) for ¯ and arc uv with u/ U and v ▯U,
(I4) for every u ▯U where u ▯= s there exists a directed su-path,
(I5) all arcs have both ends in U.
Claim. If (I1)-(I4) hold in STEP 8 then a directed st-path P exists and it is a shortest st-path.
Proof of claim: Since the loop completed, t ▯U and by (I4) there exists a directed st-path P.
We will show that P is a shortest st-path. (I1) states that ¯ is feasible. (I2) implies that all
arcs of P are equality arcs. Because of Proposition 20
it sufﬁces to verify that active cuts fo¯ contain ex-
s
actly one edge of P. Suppose for a contradiction
there is an active cut ▯(U) that contains at least two
edges of P (it contains at least one edge because of U f
Theorem 1). Denote by f the second arc of P, start-
ing from s, that in ▯(U). Then (see ﬁgure on the
t
right), the tail of f is not in U but the head of f is in
U, contradicting (I3). ▯
We leave it as an exercise to verify that (I1)-(I5) hold at the end ofTEP 1. Assume that
(I1)-(I5) hold at the beginning of theLOOP we will show that (I1)-(I5) hold at the end of the
LOOP . Together with the Claim this will complete the proof. In the following argumentU and
¯ represent the quantities at the start of tLOOP and U and y the end of the LOOP . The only
difference between y ¯ and y is that¯U= 0 and that y =Uslack (aby¯ Hence, to verify (I1) it
sufﬁces to consider f ▯ ▯(U). Then
▯ ▯
▯
slacky(f)= c ▯f ▯ yU : ▯(U) is an st-cut containing f
▯ ▯
= c f ▯ ¯U : ▯(U) is an st-cut containing f ▯y ▯ (▯)
U
= slack y¯)▯slack (ay¯.
▯
By the choice of ab in STEP 3, slacky¯f) ▯ slacky¯ab). Hence, (▯) implies that slacky(f) ▯ 0.
Thus the feasibility condition (A.1) holds for y , i.e. (I1) holds at the end of LOOP . By (▯)
we have slack (yb)= 0. Since ab is the only new arc between the start and the end of the
▯
LOOP , (I2) holds at the end of theLOOP . The only cut that is active in y but not ¯ is ▯(U).
▯Department of Combinatorics and Optimization, University of Waterloo Winter2012 A.2. MINIMUM COST PERFECT MATCHING IN BIPARTITE GRAPHS 18
By (I5) all arcs different from ab have both ends in U. Arc ab has tail in U and head outside
U. It follows that (I3) holds at the end ofLOOP . By (I4) there exists an sa-directed path
Q. Moreover, by (I5) all arcs of Q have both tail and head in U. Hence, b is distinct from all
vertices in Q, and adding arc ab at the end of Q gives a directed sb-path. It follows that (I4)
holds at the end of tLOOP . Finally, since the only new arc is ab and a,b ▯U , (I5) holds at
the end of thLOOP .
A.2 Minimum cost perfect matching in bipartite graphs
Recall the minimum cost perfect matching problem from Chapter 1. We are given a graph
G =( V,E) and costs c eor all edges e ▯ E. (Note, we allow the costs to be negative.) A
perfect matching M is a subset of the edges with the property that for every vertex v exactly
one edge of M is incident to v. The cost c(M) of a perfect matching is deﬁned as the sum of
the costs of the edges of M, i.e▯ (ce: e ▯ M). We wish to ﬁnd among all possible perfect
matchings, one that is of minimum cost.
Example 8. In the following ﬁgure we show an instance of this problem. Each of the edges
in the graph is labeled by its cost. The thick edges in the graph form a perfect matching
M = {ag,hb,cd} of total cost 3+2+1 = 6. This perfect matching is of minimum cost, hence
is a solution to our problem.
a
3 6
g 1
b
1 h 2
7 3
4 0
d c
1
A.2.1 An intuitive lower bound
We claimed in the previous example that the matching M = {ag,hb,cd} of cost 6 is a min-
imum cost perfect matching. How could you convince someone of that fact? Of course we
could list all possible perfect matchings and verify that M is indeed the one of minimum cost.
▯Department of Combinatorics and Optimization, University of Waterloo Winte2012 CHAPTER A. DUALITY THROUGH EXAMPLES 19
This is not a practical way of proceeding however, as we may have a huge (exponential) num-
ber of perfect matchings. Our goal in this section is to ﬁnd a certiﬁcate that can be used to
quickly convince someone that a perfect matching is indeed a minimum cost perfect match-
ing. Note, such a certiﬁcate is not only desirable for the user of a matching algorithm but it is
also essential for designing such an algorithm.
Example 8 continued. Suppose that for every edge incident to vertex b we decrease the cost of
all edges incident to vertex b by the value 3, see ﬁgure A.2(i). Since every perfect matching
has exactly one edge that is incident to vertex b this will decrease the cost of every perfect
matching by exactly 3. In particular, if a matching M is a minimum cost perfect matching
with these new costs, then it must be a minimum cost perfect matching with the original costs.
In ﬁgure A.2(ii) we pick values for every vertex in the graph and repeat the same argument
for each vertex. For instance if as we choose value 3 for vertex b and value 2 for vertex a the
new cost of edge ab is given by 6▯3▯2 = 1. We indicate in (ii) the new cost for every edge.
Observe now, that for the graph given in (ii), every edge has non-negative cost. This implies
2
a 6 a
3 ▯ 0 1
3
1 0
g b g b
1 h 3 3 1 h 0 3
2▯ 1 ▯1
7 3 3 2
4 0 3▯ 2 3
d c d c
1 3 0 ▯2
(i) (ii)
Figure A.2: Reduced costs
in particular, that every perfect matching has non-negative cost. However, as the matching
M = {ag,hb,cd} has cost 0, M must be a minimum cost perfect matching with these new
costs. But then M must be a minimum cost perfect matching with the original costs.
Let us try to extend these ideas to an arbitrary graph G =(V,E) with edge cests c for all
e ▯ E. Let us assign to every vertex u, a num¯uthat we call the potential of the vertex u.
The reduced cost of the edge uv is deﬁned as
cuv := cuvy ¯u▯y¯v.
▯Department of Combinatorics and Optimization, University of Waterloo Winte2012 A.2. MINIMUM COST PERFECT MATCHING IN BIPARTITE GRAPHS 20
Let M be a perfect matching. Since by deﬁnition M has exactly one edge that is incident to
every vertex u, the difference between the cost of M with costs c and costs c ¯ is given by the
▯ ▯
sum of all the potentials u over every vertex u, i.e. by▯ y¯uu ▯ V . Since this quantity is a
constant (for a ﬁxed y¯) it follows in particular that if M is a minimum cost perfect matching
with the reduced costs c¯, then it must be a minimum cost perfect matching with the original
costs c. If we selected the potential¯ so that every reduced costs has non-negative costs then
every perfect matching has non-negative costs. If in addition all edges in the perfect matching
M has zero reduced costs, then M must be a minimum costs perfect matching with respect to
the reduced costs c¯. But then, it means that M is a minimum cost perfect matching with the
original costs c.
We formalize this result by introducing a few deﬁnitions. Let we say that an edge uv is an
equality edge with respect to some potentials y¯ if its reduced cos¯ c= c ▯y ¯ ▯y ¯ = 0. We
uv uv u v
say that potentials¯ are feasible if they satisfy the following,
Feasibility condition: For every edge e ▯ E,
cuv = c uv u ▯y¯v▯ 0. (A.16)
We have thus proved the following,
Proposition 22 (Optimality Condition for perfect matchings). If the potentials y ¯ are feasible
and all edges of M are equality edges with respect to y ¯ then M is a minimum cost perfect
matching.
The arguments used to prove Proposition 22 are fairly elementary. We will see however,
that this result is surprisingly powerful. Indeed we will be able to design an efﬁcient algorithm,
for the class of bipartite graphs, based on this optimality condition. Deriving good optimal
conditions is a key step in designing an algorithm.
A.2.2 A general argument - weak duality
We used an Ad hoc argument argument to obtain Proposition 22. At a ﬁrst glance it is not
obvious at all where the idea of assigning potentials to vertices arises from. We will show
however, that is a natural idea when we look at this problem through the lens of duality theory.
In this section, we derive a natural bound on the values a certain class of linear program can
obtain. In Section A.2.3 we then show that Proposition 22 is a direct consequence of that
result.
▯Department of Combinatorics and Optimization, University of Waterloo Winte2012 CHAPTER A. DUALITY THROUGH EXAMPLES 21
Example 9. Consider the linear program
min{z(x)= c x : Ax ▯ b,x ▯ 0}, (A.17)
where ▯ ▯
▯ ▯21 ▯10 ▯ ▯▯2 ▯ 4
▯ 3 ▯
A = ▯ 9 2 1 1▯ b = ▯ 7 ▯ c =▯ ▯ .
5 1 0 3 7 ▯2
3
It is easy to verify that the vectors (1/2,0,1,3/2) and (0,1,3,2) are both feasible for the
linear program (A.17). Their objective values are 9/2 and 3, respectively, and hence the ﬁrst
T
feasible solution is clearly not optimal. We will show however that (0,1,3,2) is an optimal
solution by proving t¯) ▯ 3 for every feasible ¯.lution x
How can we ﬁnd (and prove) such a lower bound? Let us pic1 v2lues3y ,y and y and
create a new equality by multiplying the ﬁrst inequali1y of Ax = b by y , the second inequality
T
by 2 , the thir3 by y and by adding the resulting equalities. This can be expressed as y Ax =
y b or in this case,
▯ ▯21 ▯10 ▯ ▯ ▯2▯
(1 ,2 3y ) 9211 ▯x =( 1 ,2 3y ) 7▯ (A.18)
5103 7
If we choose valu¯ = 1¯ = ▯1 and ¯ = 1 we obtain the equality,
1 2 3
(▯6,0,▯2,2)x = ▯2 or equivalent0 = ▯2▯(▯6,0,▯2,2)x.
This equality holds for every feasible solution of (A.17). Adding this equality to the objective
function z(x) = (4,3,▯2,3)x yields,
T
z(x) = (4,3,▯2,3) x▯(▯6,0,▯2,2)x▯2 =( 10,3,0,1)x▯2.
T
Let ¯ be any feasible solutio¯ ▯ 0 and (10,3,0,1) ▯ 0 we have (10,3,¯ ▯ 0.
Hence, z¯) ▯▯ 2. Thus, we have proved that no feasible solution has value smaller than ▯2.
Note, this is not quite sufﬁcient to prove that (0,1,3,2) is optimal. It shows however, that the
optimum value for (A.17) is between ▯2 and 3. It is at most 3, as we have a feasible solution
with that value, and it cannot be smaller than ▯2 by the previous argument.
Let us search for y ,y ,y in a systematic way. We rewrite (A.18) as
1 2 3
▯ ▯2▯ ▯ ▯21 ▯10 ▯
0 =( 1 ,2 3y )7 ▯ ▯(y1,y2,3 ) 9 2 1 1▯ x
7 5 1 0 3
▯Department of Combinatorics and Optimization, University of WaterWint2012 A.2. MINIMUM COST PERFECT MATCHING IN BIPARTITE GRAPHS 22
and add it to the objective function z(x) = (4,3,▯2,3) x, to obtain,
▯ ▯ ▯ ▯ ▯▯
▯2 ▯21 ▯10
z(x) = (y ,y ,y ) ▯+ (4,3,▯2,3)▯(y ,y ,y ) 9 2 1 1▯▯ x. (A.19)
1 2 3 1 2 3
7 5 1 0 3
Suppose that we pick, y ,y ,y such that
1 2 3
▯ ▯
▯21 ▯10
(4,3,▯2,3)▯(y ,y ,y )9 2 1 1▯ ▯ 0 .
1 2 3
5 1 0 3
Then for any feasible s¯, inequality (A.19) and the¯ ▯ 0 implies that
▯ ▯
▯2
z(¯) ▯ (y ,y ,y )▯ .
1 2 3
7
For a minimization problem the larger the lower bound the better. Thus, the best possible
upper bound for (A.17) we can achieve using the above argument is given by the optimal
value to the following linear program,
▯ ▯
▯2
max (1 ,2 3y )7 ▯
7
subject to
▯ ▯
▯21 ▯10
(4,3,▯2,3)▯(y ,y ,y )9 2 1 1 ▯ 0
1 2 3
5 1 0 3
y1,2 3y ▯ 0
which we can rewrite as,
max (▯2,7,7)y
subject to
▯ ▯
▯ ▯ T 4
▯21 ▯10 ▯ ▯ (A.20)
▯ 9 2 1 1▯ y ▯▯ 3▯
▯ ▯2▯
5 1 0 3 3
y ▯ 0.
▯Department of Combinatorics and Optimization, University of WaWinte2012 CHAPTER A. DUALITY THROUGH EXAMPLES 23
Solving this linear program gives
y1 = 2,y¯2= 0, and y 3 = 1,
and this solution has objective value 3. Since solution (0,1,3,2) has value 3, it is optimal.
Let us generalize the previous argument and consider the following linear program,
min{c x : Ax = b,x ▯ 0} (A.21)
We ﬁrst choose a vector y and create a new equality,
T T
y Ax = y b.
This last equality is obtained from Ax = b by multiplying the 1st equality by y1the 2nd by y 2
the 3rd by y3etc, and by adding all of the resulting equalities together. This equality can be
rewritten as
T T
0 = y b▯y Ax
which holds for every feasible solution ¯ of (A.6). Thus, adding this equality to the objective
T
function z(x)= c x yields,
T T T T T T
z(x)= y b+c x▯y Ax = y b+(c ▯y A)x. (A.22)
T T T
Suppose that because of the choice of y, c ▯y A ▯ 0 . Let x ¯ be any feasible solution. As
¯ ▯ 0 we have that (c ▯y A)xT ¯ ▯ 0. It then follows by (A.7) that z(x¯) ▯ y b. Thus, we
have shown that for all y such that c ▯y A ▯ 0 the value y b is an lower bound on the
value of the objective function. Finally, note that the condition c ▯y A ▯ 0 is equivalent to
y A ▯ c , i.e. to A y ▯ c.
The best lower bound we can get in this way is the optimal value of
T T
max{b y : A y ▯ c,y free}. (A.23)
Let us summarize our result and provide a more direct proof.
Theorem 23 (Weak Duality - Special form). Consider the following pair of linear programs,
min{c x : Ax = b,x ▯ 0}

More
Less
Related notes for CS 251