- Quadratic assignment problem
The quadratic assignment problem (QAP) is one of fundamental
combinatorial optimizationproblems in the branch of optimization or operations researchin mathematics, from the category of the facilities locationproblems.
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, only the cost functionis expressed in terms of quadratic inequalities, hence the name.
Formal mathematical definition
The formal definition of the quadratic assignment problem is
:Given two sets, "P" ("facilities") and "L" ("locations"), of equal size, together with a
weight function"w" : "P" × "P" → R and a distance function "d" : "L" × "L" → R. Find the bijection"f" : "P" → "L" ("assignment") such that the cost function:
Usually weight and distance functions are viewed as square real-valued matrices, so that the cost function is written down as:
The problem is
NP-hard, so there is no known algorithmfor solving this problem in polynomial time, and even small instances may require long computation time. The Travelling salesman problemmay 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 optimizationproblems may be written in this form.
A considerable amount of research in
ant colony optimization, a biologically-inspired heuristic, has centered on solving the QAP by achieving as good an approximation as possible.
In addition to the original plant location formulation, QAP is a mathematical model for the problem of placement of interconnected
electronic components onto a printed circuit boardor on a microchip, which is part of the place and routestage of the computer aided designin electronics industry.
* A2.5: ND43, pg.218.
Wikimedia Foundation. 2010.
См. также в других словарях:
Assignment problem — The assignment problem is one of the fundamental combinatorial optimization problems in the branch of optimization or operations research in mathematics. It consists of finding a maximum weight matching in a weighted bipartite graph. In its most… … Wikipedia
Clique problem — The brute force algorithm finds a 4 clique in this 7 vertex graph (the complement of the 7 vertex path graph) by systematically checking all C(7,4)=35 4 vertex subgraphs for completeness. In computer science, the clique problem refers to any of… … Wikipedia
Ant colony optimization algorithms — Ant behavior was the inspiration for the metaheuristic optimization technique. In computer science and operations research, the ant colony optimization algorithm (ACO) is a probabilistic technique for solving computational problems which can be… … Wikipedia
List of NP-complete problems — Here are some of the more commonly known problems that are NP complete when expressed as decision problems. This list is in no way comprehensive (there are more than 3000 known NP complete problems). Most of the problems in this list are taken… … Wikipedia
Guided Local Search — is a metaheuristic search method. A meta heuristic method is a method that sits on top of a local search algorithm to change its behaviour. Guided Local Search builds up penalties during a search. It uses penalties to help local search algorithms … Wikipedia
Liste De Problèmes NP-Complets — Ceci est une liste des problèmes NP complets les plus connus en théorie de la complexité des algorithmes, exprimés sous la forme d un problèmes de la décision. Puisqu on connaît plus de 3000 problèmes NP complets, cette liste n est pas exhaustive … Wikipédia en Français
Liste de problemes NP-complets — Liste de problèmes NP complets Ceci est une liste des problèmes NP complets les plus connus en théorie de la complexité des algorithmes, exprimés sous la forme d un problèmes de la décision. Puisqu on connaît plus de 3000 problèmes NP complets,… … Wikipédia en Français
Liste de problèmes np-complets — Ceci est une liste des problèmes NP complets les plus connus en théorie de la complexité des algorithmes, exprimés sous la forme d un problèmes de la décision. Puisqu on connaît plus de 3000 problèmes NP complets, cette liste n est pas exhaustive … Wikipédia en Français
List of mathematics articles (Q) — NOTOC Q Q analog Q analysis Q derivative Q difference polynomial Q exponential Q factor Q Pochhammer symbol Q Q plot Q statistic Q systems Q test Q theta function Q Vandermonde identity Q.E.D. QED project QR algorithm QR decomposition Quadratic… … Wikipedia
Operations research — For the academic journal, see Operations Research: A Journal of the Institute for Operations Research and the Management Sciences. Operations research (also referred to as decision science, or management science) is an interdisciplinary… … Wikipedia