Prof. F.

Eisenbrand EPFL - DISOPT

Combinatorial Optimization

Adrian Bock Fall 2011

Sheet 1 September 22, 2011

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 (⋆)

In the following, we consider undirected graphs without edge weights.

Suppose that we have an efficient algorithm to decide whether a graph contains a
perfect matching (i.e. each node is incident with exactly one edge).
Use that algorithm to determine efficiently the size of a maximum matching in a
given graph G = (V, E).

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

In order to prove correctness of the algorithm we have to show the following:

a) The algorithm terminates, and
b) value returned by the algorithm is the size of a maximum matching of G.
a) Let us consider the last iteration, i.e. the graph augmented by |V | artificial
nodes. By the constructions in the lines 6 and 7, G′ contains edges {vi , xi }, i =
1..|V | and thus a perfect matching.
3
b) Assume that the algorithm stops with step = t (The correctness is trivial if
the algorithms stops in line 2). We show that the following holds:
i) Matching of size |V 2|−t exists in G, and
ii) matching of the size |V 2|−t is the maximum in G.
i) In a perfect matching of G′ , each vertex xk , k = 1..t, must be joined to a vertex
vik ∈ V , since by the construction, there is no edge between xi and xj , 1 ≤ i, j ≤ t.
The remaining |V | − t vertices, all in V , are covered by a matching.
ii) Let us assume that there exists a matching of size S > |V 2|−t . Assume wlog that
the vertices v1 , . . . , v2S form that matching. Let t′ = |V | − 2S. Clearly t′ < t. For
step = t′ all the vertices v2S+1 , . . . , v2S+t′ are matched to the vertices x1 , . . . , xt′ ,
thus v2S+1 , . . . , v2S+t′ , x1 , . . . , xt′ are perfectly covered by a matching of size t′ . It
implies that G′ for step = t′ contains a perfect matching, a contradiction.
Note that it is possible to reduce the number of calls to A in the worst case to
|V |
2
, since you only have to consider the cases in which the total number of nodes
is even (otherwise there trivially is no perfect matching).

Exercise 4

Show the following: A face F of P = {x ∈ Rn : Ax ≤ b} is inclusion-wise minimal

if and only if it is of the form F = {x ∈ Rn | A′ x = b′ } for some subsystem
A′ x ≤ b′ of Ax ≤ b.

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.