## Description:

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

Input:
-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.

Output:
-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

 TextBook Computers and Intractability: A Guide to the Theory of Np-Completeness by Michael R. Garey, David S. Johnson TextBook How to Solve It: Modern Heuristics by Zbigniew Michalewicz, David B. Fogel TextBook ACO Algorithms for the Quadratic Assignment Problem (download) by Thomas Stützle, Marco Dorigo. URL OR LIBRARY - J.E. Beasley http://mscmga.ms.ic.ac.uk/jeb/orlib/qapinfo.html URL A compendium of NP optimization problems http://www.nada.kth.se/~viggo/problemlist/compendium.html URL Experiments for the Quadratic Assigment Problem. MALLBA Project http://www.lsi.upc.es/~mallba/public/library/TabuSearch/qap.html

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