1
$\begingroup$

The Quadratic Assignment Problem formulated as an integer program: \begin{align} \mbox{minimize}\quad & \sum_{i=1}^n\sum_{j=1}^nc_{ij} x_{ij} + \sum_{i=1}^n\sum_{j=1}^n\sum_{k=1}^n\sum_{l=1}^n c_{ijkl}x_{ij}x_{kl}\\ \mbox{subject to}\quad &\sum_{i=1}^n x_{ij} = 1 \quad \forall j=1,\ldots,n,\\ &\sum_{j=1}^n x_{ij} = 1 \quad \forall i=1,\ldots,n,\\ &x_{ij}\in\{0,1\}\quad \forall i,j=1,\ldots,n. \end{align}

A simple and natural linearization: \begin{align} \mbox{minimize}\quad & \sum_{i=1}^n\sum_{j=1}^nc_{ij} x_{ij} + \sum_{i=1}^n\sum_{j=1}^n\sum_{k=1}^n\sum_{l=1}^n c_{ijkl}y_{ijkl}\\ \mbox{subject to}\quad &\sum_{i=1}^n x_{ij} = 1 \quad \forall j=1,\ldots,n,\\ &\sum_{j=1}^n x_{ij} = 1 \quad \forall i=1,\ldots,n,\\ & y_{ijkl} \le x_{ij} \quad \forall i,j,k,l=1,\ldots,n,\\ & x_{ij} + x_{kl} \le 1+y_{ijkl} \quad \forall i,j,k,l=1,\ldots,n,\\ & y_{ijkl} = y_{klij} \quad \forall i,j,k,l=1,\ldots,n,\\ &x_{ij},y_{ijkl}\in\{0,1\}\quad \forall i,j,k,l=1,\ldots,n. \end{align}

My question is: Has this linearization already been considered in the literature? I did not see it in any papers (this one for example).

$\endgroup$
1
$\begingroup$

I don't recall having seen this encoding anywhere in the literature. It would not be surprising if indeed no such academic literature exists, though.

First of all note that your trick to translate a binary quadratic programming problem to an integer programming one is pretty straight-forward. You can find a casual mentioning it on the web from 2005 here.

But there is more to it. Solving the Quadratic Assignment Problem is known to be NP-complete already, and you reduce it to an NP-hard problem. So in theory, you don't gain anything.

In practice, however, you might. But unless you have evidence that the ILP instances that you get are particularly easy to solve for modern solvers, I wouldn't use your encoding, and here is why: the efficiency from ILP solvers comes from the fact that they can use the convexity of the solution space to their advantage. This allows to perform a branch-and-bound search on the feasible solutions while using an LP solver to find not-quite-yet-valid candidate approximate solutions. But in your encoding, all values are binary! So the ILP solver can't really take advantage of it.

If we now have a look at state-of-the-art other methods to solve the problem, there seem to be both exact and heuristic methods (I found this page by following links from Wikipedia). One of the methods is reported to work well for problems with $n \leq 15$. For such instances, your encoding requires $15 \cdot 15$ variables of the type $x_{ij}$, and $15^4$ variables of the type $y_{ijkl}$. Even though we can reduce this number of variables by a factor of $16$ (I think), that is an awful lot of variables for an ILP problem where the ILP solver cannot really take advantage of the structure of the problem. So it is possible that the approach that you mention has been invented before but did not make it into any publication as it does not perform well.

$\endgroup$
  • $\begingroup$ Thanks for your discussion. I have got an answer on or-exchange.org/questions/13046/…: The above linearization was mentioned in Liberti, L. (2007), "Compact Linearization for Binary Quadratic Problems," 4OR: A Quarterly Journal of Operations Research, 5, 231–245. I will read further the references therein to see if there are discussions on the performance of the method (as you have discussed above). $\endgroup$ – Khue Dec 9 '15 at 19:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.