The Quadratic Assignment Problem


Description:The Quadratic Assignment Problem is a classified NPhard optimization problem. It can be defined as: Input: Output: 

Statement of the ProblemIn 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 InstancesIn 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


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