I need to find the solution for a combinatorial optimization problem which I reformulated into the following Integer Quadratic Program:
Given
- a family of $p$ integers $\{c_1,...c_p\}$
- and a $n\times n$ matrix $A$ with nonnegative entries and a null diagonal,
Find a family of $p$ binary vectors $(I_{P_k})_{1\le k\le p}$ which maximizes: $$\sum_{k=1}^p \ ^t I_{P_k}A I_{P_k} $$ Subject to $$\left\{ \begin{array}{ll} \displaystyle\forall k\in [|1,p|], \ \ %(1,1,...1) P_k= \sum_{i=1}^n (I_{P_k})_i=c_k \\ \displaystyle \sum_{k=1}^p I_{P_k}=\begin{pmatrix} 1 \\ \vdots \\ 1\end{pmatrix} \end{array} \right. $$ Note that all sums are computed with the usual, not binary addition.
The objective function in your model can be rewritten as: $$ \sum_k v_k^T A v_k $$ Let's just look at one term: $$ z = x^TAx = \sum_{i,j} a_{i,j} x_i x_j$$ where $x_i\in\{0,1\}$. We can replace $y_{i,j}=x_i \times x_j$ using:
$$\begin{align} &z = \sum_{i,j} a_{i,j} y_{i,j}\\ &y_{i,j} \le x_i\\ &y_{i,j} \le x_j\\ &y_{i,j} \ge x_i + x_j - 1\\ &x_i, y_{i,j} \in \{0,1\} \end{align}$$ This is now completely linear.
Note: this is a tight formulation. We can relax $y$ to be continuous between $0$ and $1$.