How quickly can this IQP or its MILP relaxation be solved

Question

Let $A\in\{0,1\}^{(n,n)}$ be a $n$ by $n$ boolean matrix (in particular think of an adjacency matrix of a graph), and consider the following optimization problem:

$$\begin{align*}&&\max_{P\in\{0,1\}^{(n,n)}}& \sum_{i =1}^n \sum_{j=i}^n (P^{t}AP)_{i,j} \\ &&\text{s.t}.\hspace{5mm}& (\vec{1})^{t}P=(\vec{1})^{t}\\ &&& \hspace{4.4mm}P\hspace{0.7mm}\vec{1} = \vec{1}\end{align*}$$

This optimization problem is asking how to reorder the rows/columns of a matrix through a permutation $P\in S_{n}$ (with its representation as a matrix) in such a way that the sum of the upper triangular is maximal, this is known to be an NP-Hard problem for adjacency matrices of general digraphs, but from my searches it seems that it is not yet known for tournaments (i.e. orientations of the complete graph).

This can also be implemented as a linear problem noting that $(P^{t}AP)_{i,j} = A_{\pi(i),\pi(j)}=\sum\limits_{k=1}^{n}\sum\limits_{l=1}^{n} A_{k,l}\min\{P_{k,i},P_{l,j}\}$, where $\pi$ is the permutation (as a function $\pi:[n]\to[n])$ given by the matrix $P$.

I've implemented the linearization on PySCIPOpt (Github link here), but it's really slow even for small matrices. I guess it's an inherent problem of optimizing over permutations, is there any "quick" way to solve (or optimize the solving algorithm) of this kind of problems?.

Answer 1

For binary $P$, we have $\min\{P_{k,i},P_{l,j}\} = P_{k,i} P_{l,j}$. In your linearization, you have introduced $r_{i,k,l,j}$ to represent this product. Because of the linear constraints $$\sum_k P_{k,i} = 1 \quad \text{for all $i$},$$ you can instead use compact linearization: \begin{align} \sum_k r_{k,i,l,j} &= P_{l,j} && \text{for all $i,l,j$} \\ r_{k,i,l,j} &\le P_{k,i} && \text{for all $k,i,l,j$} \end{align}