Lesson 6

Programming problem.

Implement an exact branch-and-bound program for the following constrained one-share index-tracking problem. There are \(n\) stocks. Each stock may be selected at most once. For stock \(i\), we know its price \(p_{i}\), target amount \(t_{i}\), and sector \(s_{i}\). We are also given a budget, an upper bound on the number of selected stocks, a spending cap for each sector, a list of conflicting pairs, and a list of dependencies. A conflicting pair \((u,v)\) means that \(u\) and \(v\) cannot both be selected. A dependency \((u,v)\) means that if \(u\) is selected, then \(v\) must also be selected.

• Input format.  The first line contains four integers \(1 \le n \le 30\), \(1 \le q \le 6\), \(0 \le c \le 200\), and \(0 \le d \le 200\): the number of stocks, sectors, conflicting pairs, and dependencies. The second line contains two integers \(0 \le B \le 10^{9}\) and \(0 \le k \le n\). The third line contains integer prices \(1 \le p_{1},\dotsc,p_{n} \le 10^{9}\). The fourth line contains integer target amounts \(0 \le t_{1},\dotsc,t_{n} \le 10^{9}\). The fifth line contains integer sector numbers \(1 \le s_{1},\dotsc,s_{n} \le q\). The sixth line contains integer sector caps \(0 \le C_{1},\dotsc,C_{q} \le B\). Then \(c\) lines each contain two integers \(u,v\) describing a conflict. Then \(d\) lines each contain two integers \(u,v\) describing a dependency.


• Output format.  Output one integer: the minimum possible tracking error among valid selected sets.

4 2 1 1
14 2
4 7 5 9
4 7 5 9
1 1 2 2
10 10
2 4
3 1

12

3 1 0 1
14 2
5 6 8
5 6 8
1 1 1
14
2 3

5