The Quadratic Assignment Problem formulated as an integer program:

Minimize $$\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}$$ subject to $$\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.$$

A simple and natural linearization:

Minimize $$\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}$$ subject to $$\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.$$

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

asked 02 Dec '15, 04:23

f10w's gravatar image

accept rate: 0%

edited 02 Dec '15, 04:29

@Rob Pratt: Your comment answers my question. Please put it as an answer so that I can accept it. Thanks.

(09 Dec '15, 14:18) f10w

Liberti, L. (2007), "Compact Linearization for Binary Quadratic Problems," 4OR: A Quarterly Journal of Operations Research, 5, 231–245.

Attributes the "usual linearization" to Fortet (1960).


answered 03 Dec '15, 15:36

Rob%20Pratt's gravatar image

Rob Pratt
accept rate: 28%


answered 03 Dec '15, 03:20

Erling_MOSEK's gravatar image

accept rate: 3%

Thanks but I don't see the considered linearization being mentioned in that paper.

(09 Dec '15, 14:20) f10w

I once saw this paper where they list several linerizations. I do not recall if the one you propose is one of them, though.


answered 04 Dec '15, 02:50

Sune's gravatar image

accept rate: 20%

Thanks but the considered linearization is not in the list.

(09 Dec '15, 14:20) f10w
Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported



Asked: 02 Dec '15, 04:23

Seen: 735 times

Last updated: 09 Dec '15, 18:51

OR-Exchange! Your site for questions, answers, and announcements about operations research.