Basics

Mixed integer programming is hard to solve (NP-hard), so here we just practically show some examples. Some algorithms to solve this is by relaxations and use the upper bounds / lower bounds of the optimal values to approach.

Stock Clustering

Consider a stock clustering problem, we have \(\rho_{i,j}\) measuring the similarity of the two stocks. We would like to choose \(k\) clusters, where in each cluster we have a representative.

One formulation can look like the following. \(x_{i,j}=1\) if stock \(i\) is in the cluster of stock \(j\). \(y_i\) indicates if stock \(i\) is a representative. Thus we have total representatives equal to \(k\) clusters. For each stock \(i\), it could only belong to one cluster. If \(j\) is not a representative, then \(x_{ij}=0\).

\[ \begin{array}{rlr} \max _{\mathbf{x}, \mathbf{y}} & \sum_{i=1}^n \sum_{j=1}^n \rho_{i j} x_{i j} & \\ & \sum_{j=1}^n y_j=k & \\ & \sum_{j=1}^n x_{i j}=1 & \text { for } i=1, \ldots, n \\ & x_{i j} \leq y_j & \text { for } i, j=1, \ldots, n \\ & x_{i j}, y_j \in\{0,1\} & \text { for } i, j=1, \ldots, n . \end{array} \]

See the next post to see how we could solve this problem in cvxpy.