Quadratic assignment problem

The Quadratic Assignment Problem (QAP) is a classic problem in combinatorial optimization. It can be defined as follows: Imagine you have two sets: 1. A set of **n** facilities (like warehouses, factories, etc.). 2. A set of **n** locations (like sites or areas where the facilities can be placed).

There are no discussions about this article yet.

 Articles by others on the same topic (1)

A permutation assigns facilities to locations, and the objective combines their pairwise interactions with pairwise location costs. Ordered-pair and unordered-pair conventions differ by a factor of two for symmetric data. The decision version is NP-complete: letting

A

record a directed cycle makes the objective exactly the length of a travelling salesman problem tour under the ordering given by the permutation. The optimization version is NP-hard.