Description
Exercise 1
Consider the following instance of the Vehicle Routing Problem: The depot is denoted by v0 and
customers by v1, . . . , v8. Demand of customers are, respectively: 3, 3, 6, 9, 9, 9, 12, 12. The capacity of
the trucks is 16. Distances between nodes are given by the table below.
v0 v1 v2 v3 v4 v5 v6 v7 v8
v0 –
v1 5 –
v2 7 4 –
v3 7 4 4 –
v4 3 6 10 10 –
v5 4 7 4 7 7 –
v6 10 7 3 3 13 6 –
v7 9 4 8 4 6 11 7 –
v8 9 8 8 8 6 11 11 4 –
a) Compute the savings as in the Clarke-Wright algorithm.
b) Solve the instance above with the Clarke-Wright algorithm.
c) What is the minimum number of trucks needed to serve all customers? Motivate your answer.
Exercise 2
Recall that in class we saw that the Maximum Matching problem (MM) and the Maximum Weighted
Matching problem (MWM) can be solved with efficient algorithms. Consider the following:
The Maximum Matching problem with a specific vertex (MMv)
Input: A graph G(V, E) and a vertex v ∈ V .
Output: A matching M of G of maximum cardinality among those that contain v.
a) Show that, assuming v has at least a neighbor, the value of the optimal solution to (MM) is equal
to the value of the optimal solution to (MMv) on the same input graph.
b) Give an algorithm that solves (MMv) (Hint: Reduce it to a problem you know how to solve)
c) In class we saw that we can formulate the problem of finding the maximum number of 2- and
3-way exchanges in a set of patients/donors as an Integer Program1
. Now suppose that patients
are ordered according to the time they spent waiting for a donation. This gives them priorities:
patient v1 has priority over v2, which has priority over v3, etc. We say that a solution S to the 2-
and 3-way exchange problem respects the priorities (RP) if the following happens:
1See the formulation from page 7 of the lecture notes from the 16th and 17th lectures.
1
v1
v2
v3
v4
v5
v6
Figure 1: An instance of the Kidney exchange problem. Consider the following three solutions: A: The
3-way exchange v1, v2, v3 plus the 2-way exchange v5, v6; B: The 3-way exchange v3, v6, v4 plus the 2-way
exchange v1, v2; B: The 3-way exchange v1, v3, v6. Solution C does not achieve the maximum number of
transplants, hence it is not RP. Both solutions A and B realize transplants for v1, v2, v3, but A does not
realize a transplant for v4, while B does. Hence, A is not RP. One can check that indeed B is an RP
solution.
– it achieves the maximum number of possible transplants with 2- and 3-way exchanges.
– take any other solution S
0
to the problem that achieves the same number of transplants with
2- and 3-way exchanges, and let vi be the first (according to the priorities given above) vertex
that receives a transplants only in one of S and S
0
. Then vi receives a transplant in S and
not in S
0
.
See Figure 1 for an example. Write an IP that finds a RP solution.
Exercise 3
Recall that, in the Kidney Exchange problem, deceased donors are voluntarily donating a kidney, without
asking for one back. When a deceased donor v enters the market, it can sparkle a sequence of donations:
v donates to v1, whose donor donates to v2, whose donor donates to v3, etc. Finding the longest
sequence of possible donation is called the longest chain problem (cfr. the notes and slides). Write
an IP formulation for the longest chain problem.
Exercise 4
Consider the file kidney.py. It contains an instance of the Kidney exchange problem with 100 nodes stored
as a list (called “data”) of directed edges in the associated directed graph. Nodes with no incoming edges
are deceased donors; all the others are patients, each with his/her own living donor.
a) Write an IP for the maximum possible number of 2-way exchanges in kidney.py, and solve it using
Gurobi.
b) Write an IP for the maximum possible number 2- and 3-way exchanges in kidney.py, and solve it
using Gurobi.
c) [Optional, bonus points] Now take into account the existence of deceased donors. Can you
find a solution containing chains from deceased donors, 2- and 3-way exchanges that lead to more
transplants than those found in part b)?
