The Quadratic Assignment Problem



The Quadratic Assignment Problem is a classified NP-hard optimization problem. It can be defined as:

-A set of facilities F={f1,...,fn}.
-A set of locations D={d1,...,dn}.
-Material flow Flow(i,j) between pairs of facilities fi,fj.
-Distance Dist(i,j) between pairs of locations di,dj.

-Assignment A defined as:



Statement of the Problem

In a standard QAP problem in location theory, we are given n facilities which are to be located in n locations. It has been defined a 'material' flow between pairs of facilities and a distance between the locations. To measure the cost of each possible assignment (there are n! of them) we multiply the prescribed flow between each pair of facilities by the distance between their assigned locations, and sum over all the pairs. The objective is to minimize the overall cost C of the layout.

Although, not required by the formulation, we will restrict our discussion to problems in which the flow matrix is symetric, i.e., the flow from facility i to j is the same as the flow from j to i.


Problem Instances

In order to define an instance of this problem we need to provide the full list of facilities and available locations. We also have to prescribe the flow between each pair of facilities and the distance between the locations of the instace.


Related Bibliography and Papers

Computers and Intractability: A Guide to the Theory of Np-Completeness
by Michael R. Garey, David S. Johnson
How to Solve It: Modern Heuristics
by Zbigniew Michalewicz, David B. Fogel
ACO Algorithms for the Quadratic Assignment Problem (download)
by Thomas Stützle, Marco Dorigo.
A compendium of NP optimization problems
Experiments for the Quadratic Assigment Problem. MALLBA Project

Last Updated: 15/07/03                                                                                                                 For any question or suggestion, click here to contact with us.