Combinatorial Optimization: Sheet 1
Combinatorial Optimization: Sheet 1
Combinatorial Optimization: Sheet 1
Combinatorial Optimization
General remark:
In order to obtain a bonus for the final grading, you may hand in written solutions
to the exercise marked with a star at the beginning of the exercise session on
October 4.
Exercise 1
Let A ∈ Rm×n , b ∈ Rm and c ∈ Rn . Show that the dual of the linear program
max{cT x : x ∈ Rn , Ax ≤ b, x ≥ 0}
can be interpreted as the linear program
min{bT y : y ∈ Rm , AT y ≥ c, y ≥ 0}.
In addition, mark (and argue!) the entries of the following table corresponding to
possible outcomes in this primal/dual pair of linear programs:
Dual
Finite optimum Unbounded Infeasible
Finite optimum
Primal
Unbounded
Infeasible
Solution
First part: Understand the primal as max{cT x : x ∈ Rn , A
−I x ≤ b
0 }, and
re-interpret the dual of this LP.
Second part:
• Primal and dual feasible and bounded is possible: Example is c = b = (0)
and A = (0).
• Primal feasible and bounded, dual unbounded is impossible: Assume that
Ax ≤ b is has a solution x. Then by weak duality, cT x a lower bound
for all solutions to the dual, in contradiction to the fact that the dual is
unbounded.
• Primal feasible and bounded, dual infeasible is impossible: If the primal
has an optimal solution, the duality theorem tells us that the dual has an
optimal solution as well. In particular the dual is feasible.
• Primal unbounded and dual feasible and bounded is impossible: Assume
that AT y = c has a solution y. Then by weak duality, bT y is an upper
bound for all solutions to the primal, in contradiction to the fact that the
primal is unbounded.
• Primal unbounded, dual unbounded is impossible: As seen above, if the
primal is unbounded, then the dual is infeasible.
• Primal unbounded, dual infeasible is possible: Example is c = (1), b = (0)
and A = (0).
• Primal infeasible, dual feasible and bounded is impossible: With the strong
duality theorem, if the dual is feasible and bounded, so is the primal.
• Primal infeasible, dual unbounded is possible: Example is c = (0), b = (−1)
and A = (0).
• Primal and dual infeasible is possible: Example is c = (1), b = (−1) and
A = (0).
Exercise 2
Determine a maximum weight matching of the graph below. Provide of proof of
optimality by determining a feasible dual solution to the linear program
X
max w(e)x(e)
e∈E X
v∈V : x(e) ≤ 1
e∈δ(v)
U ⊆V
X
|U | odd : x(e) ≤ ⌊|U|/2⌋
e∈E(U )
e∈E: x(e) ≥ 0
whose objective value coincides with the weight of your matching.
4 1
1 2
1 2
Solution
The dual is
X X
min y(v) + ⌊|U|/2⌋z(U)
v∈V U ⊆V
X |U | odd X
e∈E: y(v) + z(U) ≥ w(e)
v∈e U ⊇e
|U | odd
U ⊆V
:
|U | odd z(U) ≥ 0
v∈V : y(v) ≥ 0
2
A feasible primal solution picks the red edges and has value 9. A feasible dual
solution is denoted in blue and has value 9. Thus both solutions are optimal.
6
1 1
5
4 4 1 1
1 2
1 1 2
1
0 1
Exercise 3 (⋆)
Solution
Let A be the efficient algorithm to decide whether a given graph contains perfect
matching. We will present an algorithm for determining the size of a maximum
matching in G that uses O(|V | calls to A.
Maximum-Matching-Size(G = (V, E))
1 if A(G) = true
2 return |V2 |
3 ⊲ We assume that V = {v1 , . . . , v|V | }.
4 G′ = G
5 for step ← 1 to |V |
6 V ′ = V ′ ∪ xstep
7 E ′ = E ′ ∪ {{vi, xstep } : vi ∈ V }
8 G′ = (V ′ , E ′ )
9 if A(G′ ) == true
10 return |V |−step
2
Exercise 4
Solution
Let F be an inclusion-wise minimal face. Write
F = {x ∈ P : A′ x = b′ }
where A′ x ≤ b′ is the maximal possible subsystem of Ax ≤ b with that property,
and let
G = {x ∈ Rn : A′ x = b′ }
Assume F 6= G, then there is a point z ∈ G\F . In particular, z ∈
/ P . Furthermore,
there exists a point y ∈ F . Consider the line segment parameterized by:
w(t) = (1 − t)y + tz, t ∈ [0, 1]
Let aT x ≤ β be the first inequality of Ax ≤ b that is violated as w(t) moves from
y to z, and let t ∈ [0, 1) such that aT w(t) = β. Then
F ′ = {x ∈ P : A′ x = b′ , aT x = β}
is a face of P by the theorem seen in lecture 1, it is clearly contained in F , and it
is non-empty because w(t) ∈ F ′ . Finally, note that aT x = β cannot be contained
in the system A′ x = b′ , because aT w(t) = β does not hold for all t ∈ [0, 1].
Therefore, F ′ is defined by a subsystem of equations that is strictly bigger than
any subsystem that defines F (remember that we chose A′ x = b′ to be maximal!)
and so F ′ 6= F . In conclusion, F ′ is a proper sub-face of F , which contradicts the
inclusion-wise minimality of F . So the assumption was wrong, in fact we have
F = G.
4
Let F be a face of P such that F = {x ∈ Rn : A′ x = b′ } for a subsystem A′ x ≤ b′
of Ax ≤ b. Assume that F is not inclusion-wise minimal, i.e. there is a proper
sub-face F ′ ⊆ F . We can write
F ′ = {x ∈ P : A′ x = b′ , A′′ x = b′′ }
for a subsystem A′′ x ≤ b′′ of Ax ≤ b. Let y ∈ F ′ and z ∈ F \ F ′ . Then the line
through y and z is contained entirely in F , however there will be one inequality
aT x ≤ β of the system A′′ x ≤ b′′ that is not parallel to the line through y and z.
This means that the line cannot be entirely contained in P . This is a contradiction,
and so F must be inclusion-wise minimal.