comp3530 Assignment 4 s2 2021
This assignment is due on Oct 22. All submitted work must be done individually
without consulting someone else’s solutions in accordance with the University’s
“Academic Dishonesty and Plagiarism” policies.
Problem 1. Let G = (V, E) be a bipartite graph with edge weights w : E → R+.
Let M be the collection of all possible matchings of G. The objective of maxi-
mum cost edge coloring problem is to partition E into a collection of matchings
M1, M2, . . . , Mk ∈ M with minimum total cost, where the cost of a matching M is
defined as the maximum edge weight in M, that is, cM = maxe∈M we.
Consider the following linear programming relaxation of this problem:
minimize ∑
M∈M
cMxM
subject to ∑
M∈M:e∈M
xM = 1 ∀ e ∈ E
xM ≥ 0 ∀ M ∈ M
Your task is to design an efficient algorithm that takes as input a feasible basis
and returns a non-basic variable with negative reduced cost or reports that there is
no such variable.
Problem 2. Let G = (V, E) be a complete graph and w : E → R+ be an edge
weight function. Consider the linear relaxation of the minimum weight spanning
path problem
minimize ∑
e∈E
wexe
subject to ∑
e∈δ(u)
xe ≤ 2 ∀ u ∈ V
∑
e∈E(S)
xe ≤ |S| − 1 ∀ ∅ ⊂ S ⊆ V
∑
e∈E
xe = |V| − 1
xe ≥ 0 ∀ e ∈ E
(LP)
For a given integer n, generate instances by sampling n points uniformly at
random from the unit square [0, 1]2 and setting the weight between two points p
and q to be the square of their Euclidean distance, namely, (p1 − q1)2 + (p2 − q2)2.
Let f (n) be the expected cost of (LP) on these random instances of size n.
For a given integer n, generate instances by sampling n points uniformly at
random from the unit square [0, 1]2 and set the weight between two points to
be their Euclidean distance.
a)
Plot the point estimate of f (n) for n from 2 up to the largest power of 2 you
can solve in under a minute.
b)
Plot the empirical expected time needed to solve (LP) as a function of n.c)
1
https://sydney.edu.au/students/academic-dishonesty.html
comp3530 Assignment 4 s2 2021
Problem 3. Given a (not necessarily feasible) solution x to (LP) for some graph
G = (V, E), we define yu = 2 − ∑e∈δ(u) xe for all u ∈ V. Let A = {u ∈ V : yu ≥ 0}
and B = {u ∈ V : yu < 0}.
Consider the following auxiliary undirected network flow instance with nodes
V ∪ {s, t}, where for each u ∈ A we have an edge (s, u) with capacity yu, for each
v ∈ B we have an edge (v, t) with capacity −yv and for each (u, v) ∈ E we have an
edge (u, v) with capacity xe.
Prove that the capacity of the cut (V + s, {t}) is −y(B).a)
Prove that for any ∅ ⊂ T ⊂ V the capacity of the cut (V \ T + s, T + t) is
2(|T| − x(E(T)))− y(B).
b)
Use the above observations to design a polynomial time separation oracle for
(LP) using minimum cut.
c)
Problem 4. We continue working with the same formulation for the minimum
spanning path problem and the same random instances. This time we aim to use
delayed constraint generation starting with
minimize ∑
e∈E
wexe
subject to ∑
e∈δ(u)
xe ≤ 2 ∀ u ∈ V
∑
e∈E
xe = |V| − 1
xe ≥ 0 ∀ e ∈ E
(AUX)
Implement a separation oracle for (LP) using minimum cut.a)
Solve (LP) using delayed constraint generation starting form (AUX) and using
the separation oracle to find violated constraints.
b)
Plot the point estimate of f (n) for n from 2 up to the largest power of 2 you
can solve in under a minute.
c)
Plot the empirical expected time needed to solve (LP) as a function of n.d)
2