# On the Continuous Relaxation of the Quadratic Assignment Problem

 0 Consider the Quadratic Assignment Problem: 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.$$ I remember reading somewhere that when we relax the integer constraint, i.e., $x_{ij}\in\{0,1\}$, to $x_{ij}\ge 0$, then we obtain an equivalent problem. Could anyone please suggest some references on this? A further question is, if the number of facilities ($n$) and the number of locations ($m$) are different (suppose that $n < m$): Minimize $$\sum_{i=1}^n\sum_{j=1}^m c_{ij} x_{ij} + \sum_{i=1}^n\sum_{j=1}^m\sum_{k=1}^n\sum_{l=1}^m c_{ijkl}x_{ij}x_{kl}$$ subject to $$\sum_{i=1}^n x_{ij} \le 1 \quad \forall j=1,\ldots,m,$$ $$\sum_{j=1}^m x_{ij} = 1 \quad \forall i=1,\ldots,n,$$ $$x_{ij}\in\{0,1\}\quad \forall i=1,\ldots,n, j=1,\ldots,m.$$ Then does the above statement (i.e. the equivalence) still hold? Thank you in advance for your discussions! asked 08 Mar '16, 11:32 f10w 33●4 accept rate: 0% 1 I think you might be mistaking QAP for the assignment problem (they both share the same feasible set, but have different objective functions). Since their feasible set is totally unimodular, optimizing a linear objective function over its LP relaxation would yield an integer optimal solution. AFAIK, that doesn't hold for QAP as it has a quadratic objective function. (09 Mar '16, 15:42) Ehsan ♦
Be the first one to answer this question!
 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: