# The first reference which formulated k-means problem as MIQCP using big-M constraint

k-means, or MSS (minimum-sum-of-squares) clustering is a basic problem in statistics. To remind, for a set of points $$P_1, P_2, \dots, P_N$$ in $$\mathbb{R}^d$$, the problem is to find $$K$$ centres $$Q_1, Q_2, \dots, Q_K$$ (in $$\mathbb{R}^d$$) and assign the points to the centres with indicator-variables $$\left\{x_{nk}, \, n=1, \dots,N, \,k=1,\dots,K\right\}$$, so that this problem is minimized: $$\min\sum_{n=1}^N\sum_{k=1}^K x_{nk}\left\| P_n-Q_k\right\|^2_2 \\ \text{s.t. } \sum_{k=1}^K x_{nk} = 1, \; n=1, \dots, N \\ x_{nk} \in \left\{0, 1\right\}, \; Q_k \in \mathbb{R}^d$$ k-means problem can be reformulated the following way: $$\min\sum_{n=1}^N d_n \\ \text{s.t. } \\ \left\|P_1-Q_k\right\|_2^2 \leq d_1 + (1-x_{1k})M, \quad k=1,\dots,K, \\ \left\|P_2-Q_k\right\|_2^2 \leq d_2 + (1-x_{2k})M, \quad k=1,\dots,K,\\ \dots \\ \left\|P_N-Q_k\right\|_2^2 \leq d_N + (1-x_{Nk})M, \quad k=1,\dots,K$$ Here $$M$$ is a sufficiently large constant. In the thesis I have read, this is called the big-M technique''.

The above problem is a MIQCP (mixed-integer-quadratically-constrained-programming) problem and could be approached with, for example, gurobi.

I wonder who should be addressed (as a reference) to be the first one who has come up with such problem formulation.