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's gravatar image

accept rate: 0%


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

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: 08 Mar '16, 11:32

Seen: 491 times

Last updated: 09 Mar '16, 15:42

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