Lesson 2

The tracking objective still contains absolute values. Introduce variables \(d_{i}\ge 0\) and require \[d_{i}\ge p_{i} x_{i}-t_{i},\qquad d_{i}\ge t_{i}-p_{i} x_{i}.\] Then minimizing \(\sum_{i} d_{i}\) forces \(d_{i}=|p_{i} x_{i}-t_{i}|\) in an optimal solution. This gives an ILP for index tracking with budget, maximum shares, conflicts, dependencies, and sector caps.

A valid inequality is an extra inequality that every feasible integer portfolio already satisfies. Adding it does not change the set of feasible integer solutions, but it can make search easier. For example, if every stock in a set \(U\) belongs to the same sector and their total price is larger than the sector cap, then not all of them can be selected: \[\sum_{i\in U}y_{i}\le |U|-1.\] Good solvers generate many such inequalities automatically.