# On a Linearization of the Quadratic Assignment Problem

 2 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 33●4 accept rate: 0% @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

 1 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 Pratt 1.2k●2●6 accept rate: 28%
 1 It looks related to http://pubsonline.informs.org/doi/abs/10.1287/opre.43.5.781?journalCode=opre answered 03 Dec '15, 03:20 Erling_MOSEK 616●1●4 accept rate: 3% Thanks but I don't see the considered linearization being mentioned in that paper. (09 Dec '15, 14:20) f10w
 0 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 958●4●14 accept rate: 20% Thanks but the considered linearization is not in the list. (09 Dec '15, 14:20) f10w
 toggle preview community wiki

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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

Tags: