Lesson 1

Integer constraints are what make the problem combinatorial. If we replace \(x_{i}\in\mathbb{Z}_{\ge 0}\) by \(x_{i}\ge 0\) and replace \(y_{i}\in\{0,1\}\) by \(0\le y_{i}\le 1\), we obtain the linear programming relaxation. The relaxed solution may buy fractional shares or use a fractional amount of a stock.

For index tracking, this relaxation can be much too optimistic. With one stock of price \(6\), target \(5\), maximum one share, and budget \(6\), the integer optimum has error \(1\). The LP relaxation buys \(5/6\) of a share and gets error \(0\). The gap is caused by exactly the feature that made the project interesting: shares are indivisible.