IT代考 comp3530 Assignment 4 s2 2021 – cscodehelp代写
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 ∑ cMxM
M∈M
subjectto ∑xM =1 ∀e∈E M∈M:e∈M
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 subjectto
∑ we xe e∈E
∑ xe≤2 e∈δ(u)
∑ xe≤|S|−1 e∈E(S)
∑ xe = |V| − 1
e∈E
∀u∈V ∀∅⊂S⊆V
∀ e ∈ E
xe ≥ 0
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.
a) 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.
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. 1
(LP)
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} andB={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.
a) Prove that the capacity of the cut (V + s, {t}) is −y(B).
b) Prove that for any ∅ ⊂ T ⊂ V the capacity of the cut (VT+s,T+t) is
2(|T| − x(E(T))) − y(B).
c) Use the above observations to design a polynomial time separation oracle for
(LP) using minimum cut.
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 subjectto
∑ we xe e∈E
∑ xe≤2 e∈δ(u)
∑ xe = |V| − 1
e∈E
∀u∈V
(AUX)
xe ≥ 0
a) Implement a separation oracle for (LP) using minimum cut.
b) Solve (LP) using delayed constraint generation starting form (AUX) and using the separation oracle to find violated constraints.
c) 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.
d) Plot the empirical expected time needed to solve (LP) as a function of n.
2
∀ e ∈ E
