Description
Exercise 1
In this exercise, we will write and feed to Gurobi an IP for building an index fund that tracks S&P
500 index. In the same folder containing the assignment file, there is a file data.txt. This contains the
correlation between the stock options under consideration for the period of 3 years ending on June 30th,
2017. Now open the file Index.py. It contains a file that you can feed to Gurobi in a similar way as we
did for the TSP.py and TSPplus.py, but needs to be completed. In particular, constraints (other than
binary constraints on variables) are missing.
a) [20pt] Complete the file Index.py so that, when fed to Gurobi, it solves the IP for producing an
Index Fund seen in class1
. Note that the usage of this file is gurobi Index.py n, where n is the
number of stock options you want to be in your index.
b) [5pt] Launch it on Gurobi with n=20, 40, 60. Report the results you obtain and the running time.
Exercise 2
In the Knapsack problem, we are given n objects, where object i has weight wi and profit pi
, and a
capacity B, and we want to compute the set of objects of maximum total profit whose total weight does
not exceed the capacity. Define by IP1 the following formulation:
max p1x1 + … + pnxn : w1x1 + w2x2 + · · · + wnxn ≤ B, x ∈ {0, 1}
n
,
and by IP2 the following formulation:
max p1x1 + … + pnxn :
X
i∈I
xi ≤ |I| − 1 for all I ⊆ [n] : P
i∈I wi > B, x ∈ {0, 1}
n
.
a) [10pt] Show that IP1 is a valid IP formulation for the Knapsack problem.
b) [bonus] Show that IP2 is a valid IP formulation for the Knapsack problem.
Recall the concept of tighter formulation seen in class: we say that IP1 is tighter than IP2 if the
linear relaxation LP1 of IP1 is always contained in the linear relaxation LP2 of IP2.
c) [5pt] Show that there are knapsack instances where LP2 ⊆ LP1.
d) [5pt] Show that there are knapsack instances where LP1 ⊆ LP2.
e) [5pt] Show that there are knapsack instances where both LP2 * LP1 and LP1 * LP2.
Exercise 3
Consider again the most parsimonious tree problem seen in the previous assignment. Suppose now that
the following additional restriction hold:
Once a character has been developed, it cannot be undeveloped in future species.
1Use files TSP.py and TSPplus.py for reference.
1
We call this new problem the original most parsimonious tree problem (OMPTP). In this exercise, we
will write an IP formulation for OMPTP. A directed tree rooted at r is a directed graph with no directed
or undirected cycle, such that, for each vertex v, there is a directed path from r to v. An instance of
the Rooted Steiner Minimum Tree (RSMT) problem is given by a directed graph D(V, A) with weights
on the arcs, a node r ∈ V and a set of terminals T ⊆ V \ {r}. The goal is to find, among all subgraphs
of D, a directed tree rooted at r of minimum total weight that contains r and all terminals.
a) [10pt] Argue that the OMPTP can be formulated as a RSMT problem.
b) [7.5pt] Write an IP formulation for the RSMT.
c) [7.5pt] Now suppose we add the constraints that no species can evolve from the modern species
(i.e., the ones that are given as input) and that each character can only be developed once. Modify
your IP from part b) so that you now satisfy those constraints.
