CO 250: Introduction to Optimization
Module 1: Formulations (Shortest Paths)
c©University of Waterloo 1 / 12
Recap: Shortest Paths
Input:
• Graph G = (V,E)
• Non-negative edge lengths ce
for all e ∈ E
• Vertices s, t ∈ V
Goal: Compute an s, t-path of
smallest total length.
Recall: P is an s, t-path if it is of
the form
v1v2, v2v3, . . . , vk−1vk
and
s t
a
b
3 2
1
24
1. vivi+1 ∈ E for all
i ∈ {1, . . . , k − 1},
2. vi 6= vj for all i 6= j, and
3. v1 = s and vk = t.
E.g., P = sa, ab, bt
c©University of Waterloo 2 / 12
Recap: Shortest Paths
Shortest Path Problem: Given
G = (V,E), ce ≥ 0 for all e ∈ E,
and s, t ∈ V , compute an s, t-path
of smallest total length.
Now: Formulate the problem as an
IP!
Useful Observation: Let C ⊆ E be a
set of edges whose removal
disconnects s and t.
−→Every s, t-path P must have at
least one edge in C.
s t
a
b
3 2
1
24
Definition
For S ⊆ V , we let δ(S) be the set of
edges with exactly one endpoint in
S.
δ(S) = {uv ∈ E : u ∈ S, v 6∈ S}
c©University of Waterloo 3 / 12
Cuts
Examples:
1. S = {s} → δ(S) = {sa, sb}
2. S = {s, a} → δ(S) = {ab, at, sb}
3. S = {a, b} → δ(S) = {sa, sb, at, bt}
Definition
δ(S) is an s, t-cut if s ∈ S and t 6∈ S.
E.g., 1 and 2 are s, t-cuts, 3 is not.
s t
a
b
3 2
1
24
Definition
For S ⊆ V , we let δ(S) be the
set of edges with exactly one
endpoint in S.
δ(S) = {uv ∈ E : u ∈ S, v 6∈ S}
c©University of Waterloo 4 / 12
Cuts
Definition
δ(S) is an s, t-cut if s ∈ S and t 6∈ S.
E.g., δ({s, a}) = {sb, ab, at} is an
s, t-cut.
Remark
If P is an s, t-path and δ(S) is an
s, t-cut, then P must have an edge from
δ(S).
E.g., P = sa, ab, bt.
s t
a
b
3 2
1
24
c©University of Waterloo 5 / 12
Cuts
Remark
If S ⊆ E contains at least one edge
from every s, t-cut, then S contains an
s, t-path.
Proof: (by contradiction)
• Suppose S has an edge from every
s, t-cut, but S has no s, t-path.
• Let R be the set of vertices
reachable from s in S:
R = {u ∈ V : S has an s, u−path}.
• δ(R) is an s, t-cut since s ∈ R and
t 6∈ R.
s t
a
b
3 2
1
24
R
• Note: There cannot be an
edge uv ∈ E with u ∈ R
and v 6∈ R. Otherwise: v
should have been in R!
−→ δ(R) ∩ S = ∅.
Contradiction!
c©University of Waterloo 6 / 12
S
An IP for Shortest Paths
Variables: We have one binary variable
xe for each edge e ∈ E. We want:
xe =
{
1 : e ∈ P
0 : otherwise
Constraints: We have one constraint for
each s, t-cut δ(U), forcing P to have an
edge from δ(S).∑
(xe : e ∈ δ(U)) ≥ 1 (1)
for all s, t-cuts δ(U).
Objective:
∑
(cexe : e ∈ E)
s t
a
b
3 2
1
24
R
Remark
If S ⊆ E contains at least one
edge from every s, t-cut, then S
contains an s, t-path.
c©University of Waterloo 7 / 12
An IP for Shortest Paths
min
∑
(cexe : e ∈ E)
s.t.
∑
(xe : e ∈ δ(U)) ≥ 1 (U ⊆ V, s ∈ U, t 6∈ U)
xe ≥ 0, xe integer (e ∈ E)
min (3, 4, 1, 2, 2)x
s.t.

sa sb ab at bt
{s} 1 1 0 0 0
{s, a} 0 1 1 1 0
{s, b} 1 0 1 0 1
{s, a, b} 0 0 0 1 1
x ≥ 1
x ≥ 0 x integer
s t
a
b
3 2
1
24
c©University of Waterloo 8 / 12
An IP for Shortest Paths
min
∑
(cexe : e ∈ E)
s.t.
∑
(xe : e ∈ δ(U)) ≥ 1 (U ⊆ V, s ∈ U, t 6∈ U)
xe ≥ 0, xe integer (e ∈ E)
Suppose: ce > 0 for all e ∈ E
Then: In an optimal solution, xe ≤ 1 for all e ∈ E. Why?
Suppose xe > 1.
Then let xe = 1. This is cheaper and maintains feasibility!
For a binary solution x, define
Sx = {e ∈ E : xe = 1}.
c©University of Waterloo 9 / 12
An IP for Shortest Paths
Note: If x is feasible for an IP, then Sx
satisfies the remark, but Sx may contain
more than just an s, t-path!
E.g., xe = 1 for all blue edges in the
figure and xe = 0 otherwise. Then,
Sx = {sa, ab, at}
Note: x cannot be optimal for the IP!
Why?
s t
a
b
3 2
1
24
Remark
If S ⊆ E contains at least one
edge from every s, t-cut, then S
contains an s, t-path.
c©University of Waterloo 10 / 12
An IP for Shortest Paths
min
∑
(cexe : e ∈ E)
s.t.
∑
(xe : e ∈ δ(U)) ≥ 1 (U ⊆ V, s ∈ U, t 6∈ U)
xe ≥ 0, xe integer (e ∈ E)
Remark
If x is an optimal solution for the above IP and ce > 0 for all e ∈ E, then
Sx contains the edges of a shortest s, t-path.
c©University of Waterloo 11 / 12
Shortest Paths
Recap
• Given G = (V,E) and U ⊆ V , we define
δ(U) = {uv ∈ E : u ∈ U, v 6∈ U}.
• δ(U) is an s, t-cut if s ∈ U and t 6∈ U .
• If S ⊆ E intersects every s, t-cut δ(U), then S contains an s, t-path.
• Feasible solutions to the shortest path LP correspond to edge-sets
that intersect every s, t-cut; optimal solutions are minimal in this
respect if ce > 0 for all e ∈ E.
c©University of Waterloo 12 / 12