Makeup for First Homework Set
Take home exam. Submit solutions via email, preferably in pdf format. Scanned images are OK.
Solutions are due by midnight on April 21, 2020 (SHARP!)
Problem 1: Let a ∈ Rn+ and b ∈ R+ be given parameters. Let us call a subset
S ⊆ E = {1, 2, ..., n} independent if a(S) =
∑
j∈S aj ≤ b. We know that this
defines an independence system.
• Consider n = 7, a = (1, 1, 1, 2, 3, 4, 6), b = 9, and X = {1, 2, 3, 4, 5, 6, 7}:
What are the values of r(X) and ρ(X)?
• Consider the values/weights c = (2, 2, 3, 4, 1, 5, 6). What is the Best-in-
Greedy independent set?
Problem 2: Consider the graph G = (V,E) on Figure 1. Let F ⊆ 2V (G) be
the family of independent (stable) sets of G, that is vertex subsets that do not
contain an edge inside.
1
3
2
4 5
Figure 1:
• Is (V (G),F) a matroid? Why?
• Recall that the associated independence polytope is defined as
PV (G),F =
{
x ∈ RV (G)
∣∣∣∣ x(S) ≤ r(S) ∀ S ⊆ V (G),xv ≥ 0 ∀ v ∈ V (G)
}
Write down the defining inequalities for PV (G),F . Eliminate the redundant
ones.
• How much is the maximum of 5x1 + 7x2 + 3x4 over PV (G),F?
1
Problem 3: Consider the graph G = (V,E) on Figure 2.
1 2 3
4 5 6
7 8 9
9
10 9
11
9 11 7
9
4 8
10
XXXXXXXXXX
3 10
Figure 2:
• What is the weight of the maximum-weight spanning tree?
• Compute the sequence of edges chosen by Kruskal’s algorithm.
Problem 4: Consider the following cutting stock problem, with input length
L = 31. These 31-feet pieces are to be cut into smaller ones to fulfill the following
orders:
length ordered
(in feet) #
3 13500
5 27800
11 3900
7 9750
8 15250
9 1700
Use the AMPL model to solve this problem. What is the optimal solution?
Problem 5: You manage a lawfirm, and you have 5 new important cases, C1,
C2, C3, C4 and C5, and five associates, Julie, John, Jim, Jonathan and Jack
to assign. You play mock-trials with your associates in all five cases, and see
the following chances:
Julie XXXXXXXXXX
John XXXXXXXXXX
Jim XXXXXXXXXX
Jonathan XXXXXXXXXX
Jack XXXXXXXXXX
2
1 3
2
4
6
5
7
8
3
5
3
4
6
5
4
2
5
6
7
3
9
2 1
7
54 3
Figure 3:
where each entry in the matrix is the chance in % that the assigned associate
will lose the trial. If all these cases expect to
ing in the same amount if
you win, and nothing if you loose, what is your best strategy to assign you
five associates to these 5 cases, one to one? Run the Hungarian algorithm and
document the steps it takes.
Problem 6: Consider the instance of the Chinese Postman problem shown in
Figure 3. The edge traversing times are shown along the edges in minutes.
• Assume that the post office is in area 2. What is the optimal, time mini-
mizing tour of the postman? How much time does he need to deliver all
letters and get back to the post office?
• Assume that the post office is in area 5. What is now the time he needs
to deliver all letters?
3