Problem przypisania kwadratowego - Quadratic assignment problem

Kwadratowego problemu przydziału ( QAP ) jest jednym z podstawowych optymalizacji kombinatorycznej problemów w oddziale optymalizacji lub operacji badania w matematyce , z kategorii Wyposażenie Lokalizacja problemami pierwszy wprowadzonych przez Koopmansa i Beckmann.

Problem ten modeluje następujący rzeczywisty problem:

Istnieje zestaw n obiektów i zestaw n lokalizacji. Dla każdej pary lokalizacji określana jest odległość, a dla każdej pary obiektów określana jest waga lub przepływ (np. ilość dostaw transportowanych pomiędzy dwoma obiektami). Problem polega na przypisaniu wszystkich obiektów do różnych lokalizacji w celu zminimalizowania sumy odległości pomnożonych przez odpowiednie przepływy.

Intuicyjnie funkcja kosztów zachęca obiekty o dużym przepływie między sobą do umieszczania blisko siebie.

Sformułowanie problemu przypomina zadanie przypisania , z tym wyjątkiem, że funkcja kosztu jest wyrażona w postaci nierówności kwadratowych, stąd nazwa.

Formalna definicja matematyczna

Formalna definicja problemu przypisania kwadratowego jest następująca:

Biorąc pod uwagę dwa zestawy, P ("obiekty") i L ("lokalizacje"), o jednakowej wielkości, wraz z funkcją wagi w  : P × P → R i funkcją odległości d  : L × L → R . Znajdź bijekcję f  : P → L ("przypisanie") taką, że funkcja kosztu:

${\ Displaystyle \ suma _ {a, b \ w P} w (a, b) \ cdot d (f (a), f (b))}$

jest zminimalizowany.

Zwykle funkcje wagi i odległości są postrzegane jako kwadratowe macierze wartości rzeczywistych , tak że funkcja kosztu jest zapisywana jako:

${\ Displaystyle \ suma _ {a, b \ w P} w_ {a, b} d_ {f (a), f (b)}}$

W notacji macierzowej:

${\ Displaystyle \ min _ {X \ w \ Pi _ {n}} \ nazwa operatora {ślad} (WXDX ^ {T})}$

gdzie jest zbiorem macierzy permutacji, jest macierzą wag i jest macierzą odległości. ${\ Displaystyle \ Pi _ {n}}$${\displaystyle n\razy n}$${\ Displaystyle W}$${\ Displaystyle D}$

Złożoność obliczeniowa

Problem jest NP-trudny , więc nie ma znanego algorytmu rozwiązania tego problemu w czasie wielomianowym, a nawet małe instancje mogą wymagać długiego czasu obliczeń. Wykazano również, że problem nie ma algorytmu aproksymacji działającego w czasie wielomianowym dla dowolnego (stałego) czynnika, chyba że P = NP. Problem komiwojażera można traktować jako szczególny przypadek QAP jeśli zakłada się, że przepływ połączenia wszystkich urządzeń tylko wzdłuż jednego pierścienia, wszystkie strumienie mają tę samą wartość niezerową (stały). W tej postaci można zapisać wiele innych problemów standardowych problemów optymalizacji kombinatorycznej .

Aplikacje

Oprócz oryginalnego sformułowania lokalizacji zakładu, QAP jest modelem matematycznym problemu umieszczania połączonych elementów elektronicznych na płytce drukowanej lub mikroczipie , co jest częścią etapu lokalizacji i trasy komputerowego wspomagania projektowania w przemyśle elektronicznym .

Zobacz też

• Kwadratowy problem przypisania wąskiego gardła

Bibliografia

Uwagi

Źródła

• Michael R. Garey i David S. Johnson (1979). Komputery i nierozwiązywalność: przewodnik po teorii NP-zupełności . WH Freemana. Numer ISBN 0-7167-1045-5. A2.5: ND43, str.218.

Linki zewnętrzne

• https://www.opt.math.tugraz.at/qaplib/ QAPLIB – Kwadratowa biblioteka problemów przypisania
• http://www.wiomax.com/team/xie/maos-qap-quadratic-assignment-problem-project-portal/ MAOS-QAP — narzędzie do rozwiązywania problemów przypisania kwadratowego oparte na Javie
• https://CRAN.R-project.org/package=qap - Pakiet R qap: Heurystyka problemu przypisania kwadratowego