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 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
f10w |

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.