Quadratic assignment problem
Encyclopedia
The quadratic assignment problem (QAP) is one of fundamental combinatorial optimization
problems in the branch of optimization
or operations research
in mathematics
, from the category of the facilities location problems.
The problem models the following real-life problem:
The problem statement resembles that of the assignment problem
, only the cost function is expressed in terms of quadratic inequalities, hence the name.
Usually weight and distance functions are viewed as square real-valued matrices
, so that the cost function is written down as:
Computational complexity
The problem is NP-hard
, so there is no known algorithm
for solving this problem in polynomial time, and even small instances may require long computation time. The Travelling salesman problem
may be seen as a special case of QAP if one assumes that the flows connect all facilities only along a single ring, all flows have the same non-zero (constant) value. Many other problems of standard combinatorial optimization
problems may be written in this form.
s onto a printed circuit board
or on a microchip
, which is part of the place and route
stage of computer aided design in the electronics industry.
Combinatorial optimization
In applied mathematics and theoretical computer science, combinatorial optimization is a topic that consists of finding an optimal object from a finite set of objects. In many such problems, exhaustive search is not feasible...
problems in the branch of optimization
Optimization (mathematics)
In mathematics, computational science, or management science, mathematical optimization refers to the selection of a best element from some set of available alternatives....
or operations research
Operations research
Operations research is an interdisciplinary mathematical science that focuses on the effective use of technology by organizations...
in mathematics
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, from the category of the facilities location problems.
The problem models the following real-life problem:
- There are a set of n facilities and a set of n locations. For each pair of locations, a distance is specified and for each pair of facilities a weight or flow is specified (e.g., the amount of supplies transported between the two facilities). The problem is to assign all facilities to different locations with the goal of minimizing the sum of the distances multiplied by the corresponding flows.
The problem statement resembles that of the assignment problem
Assignment problem
The assignment problem is one of the fundamental combinatorial optimization problems in the branch of optimization or operations research in mathematics...
, only the cost function is expressed in terms of quadratic inequalities, hence the name.
Formal mathematical definition
The formal definition of the quadratic assignment problem is as follows:- Given two sets, P ("facilities") and L ("locations"), of equal size, together with a weight functionWeight functionA weight function is a mathematical device used when performing a sum, integral, or average in order to give some elements more "weight" or influence on the result than other elements in the same set. They occur frequently in statistics and analysis, and are closely related to the concept of a...
w : P × P → RReal numberIn mathematics, a real number is a value that represents a quantity along a continuum, such as -5 , 4/3 , 8.6 , √2 and π...
and a distance function d : L × L → RReal numberIn mathematics, a real number is a value that represents a quantity along a continuum, such as -5 , 4/3 , 8.6 , √2 and π...
. Find the bijectionBijectionA bijection is a function giving an exact pairing of the elements of two sets. A bijection from the set X to the set Y has an inverse function from Y to X. If X and Y are finite sets, then the existence of a bijection means they have the same number of elements...
f : P → L ("assignment") such that the cost function:
-
- is minimized.
Usually weight and distance functions are viewed as square real-valued matrices
Matrix (mathematics)
In mathematics, a matrix is a rectangular array of numbers, symbols, or expressions. The individual items in a matrix are called its elements or entries. An example of a matrix with six elements isMatrices of the same size can be added or subtracted element by element...
, so that the cost function is written down as:
Computational complexityComputational ComplexityComputational Complexity may refer to:*Computational complexity theory*Computational Complexity...
The problem is NP-hardNP-hard
NP-hard , in computational complexity theory, is a class of problems that are, informally, "at least as hard as the hardest problems in NP". A problem H is NP-hard if and only if there is an NP-complete problem L that is polynomial time Turing-reducible to H...
, so there is no known algorithm
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
for solving this problem in polynomial time, and even small instances may require long computation time. The Travelling salesman problem
Travelling salesman problem
The travelling salesman problem is an NP-hard problem in combinatorial optimization studied in operations research and theoretical computer science. Given a list of cities and their pairwise distances, the task is to find the shortest possible tour that visits each city exactly once...
may be seen as a special case of QAP if one assumes that the flows connect all facilities only along a single ring, all flows have the same non-zero (constant) value. Many other problems of standard combinatorial optimization
Combinatorial optimization
In applied mathematics and theoretical computer science, combinatorial optimization is a topic that consists of finding an optimal object from a finite set of objects. In many such problems, exhaustive search is not feasible...
problems may be written in this form.
Applications
In addition to the original plant location formulation, QAP is a mathematical model for the problem of placement of interconnected electronic componentElectronic component
An electronic component is a basic electronic element and may be available in a discrete form having two or more electrical terminals . These are intended to be connected together, usually by soldering to a printed circuit board, in order to create an electronic circuit with a particular function...
s onto a printed circuit board
Printed circuit board
A printed circuit board, or PCB, is used to mechanically support and electrically connect electronic components using conductive pathways, tracks or signal traces etched from copper sheets laminated onto a non-conductive substrate. It is also referred to as printed wiring board or etched wiring...
or on a microchip
Integrated circuit
An integrated circuit or monolithic integrated circuit is an electronic circuit manufactured by the patterned diffusion of trace elements into the surface of a thin substrate of semiconductor material...
, which is part of the place and route
Place and route
Place and route is a stage in the design of printed circuit boards, integrated circuits, and field-programmable gate arrays. As implied by the name, it is composed of two steps, placement and routing. The first step, placement, involves deciding where to place all electronic components, circuitry,...
stage of computer aided design in the electronics industry.
External Links
- http://www.seas.upenn.edu/qaplib/ QAPLIB - A Quadratic Assignment Problem Library