Quadratic assignment problem

Quadratic assignment problem

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:

: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 function is 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:

::sum_{a,bin P}w(a,b)cdot d(f(a), f(b)):is minimized.

Usually weight and distance functions are viewed as square real-valued matrices, so that the cost function is written down as:

:sum_{a,bin A}w_{a,b}d_{f(a),f(b)}

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.

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.

Applications

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 board or on a microchip, which is part of the place and route stage of the computer aided design in electronics industry.

References

* 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


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»