Consider a directed graph G with source vertex s and target vertex t and associated costs cost(·) ≥ 0 on the edges. Let P denote the set of all the directed (simple) paths from s to t in G.
Consider the following (very large) integer program:
minimize
Σ
e∈E(G)
cost(e) xe
subject to xe ∈ {0, 1} ∀e ∈ E(G)
Σ
e∈
xe ≥ 1 ∀ ∈ P.
(A) What does this IP computes?
(B) Write down the relaxation of this IP into a linear program.
(C) Write down the dual of the LP from (B). What is the interpretation
of this new LP? What is it computing for the graph G (prove your answer)?
(D) The strong duality theorem states the following.
Theorem 0.1 If the primal LP problem has an optimal solution
x∗ =(x∗
1 , . . . , x∗
n) then the dual also has an optimal solution, y∗ =
(y∗
1, . . . , y∗
m), such that
Σ
j
cjx∗
j =
Σ
i
biy∗
i .
In the context of (A)-(C) what result is implied by this theorem if we apply it to the primal LP and its dual above? (For this, you can assume that the optimal solution to the LP of (B) is integral - which is not quite true - things are slightly more complicated than that.)