Задача квадратичного назначения

Квадратичная задача о назначениях ( QAP ) — одна из фундаментальных задач комбинаторной оптимизации в области оптимизации или исследования операций в математике , из категории задач размещения объектов, впервые предложенных Купмансом и Бекманном.

Задача моделирует следующую реальную проблему:

Имеется набор из n объектов и набор из n локаций. Для каждой пары объектов расстояние указывается , а для каждой пары объектов указывается вес или поток (например, количество материалов, транспортируемых между двумя объектами). Проблема состоит в том, чтобы распределить все объекты по разным местам с целью минимизировать сумму расстояний, умноженную на соответствующие потоки.

Интуитивно понятно, что функция затрат побуждает объекты с высокими потоками между собой располагаться близко друг к другу.

Постановка задачи напоминает постановку задачи о назначениях , за исключением того, что функция стоимости выражается через квадратичные неравенства, отсюда и название.

математическое

Формальное определение квадратичной задачи о назначениях выглядит следующим образом:

Даны два набора P («объекты») и L места») одинакового размера вместе с весовой функцией w : P × P → R и функцией расстояния d : L × L → R. ( « Найдите биекцию f : P → L («присваивание») такую, что функция стоимости:

$\sum _{a,b\in P}w(a,b)\cdot d(f(a),f(b))$

сведен к минимуму.

Обычно функции веса и расстояния рассматриваются как квадратные вещественные матрицы , так что функция стоимости записывается как:

$\sum _{a,b\in P}w_{a,b}d_{f(a),f(b)}$

В матричной записи:

$\min _{X\in \Pi _{n}}\operatorname {trace} (WXD^{T}X^{T})$

где $\Pi _{n}$ это набор $n\times n$ матрицы перестановок, $W$ - весовая матрица и $D$ - матрица расстояний.

сложность

Задача является NP-сложной , поэтому не существует известного алгоритма решения этой задачи за полиномиальное время, и даже небольшие случаи могут потребовать длительного времени вычислений. Также было доказано, что задача не имеет алгоритма аппроксимации, работающего за полиномиальное время для любого (постоянного) фактора, за исключением случаев, когда P = NP. ( Задачу коммивояжера ЗКП) можно рассматривать как частный случай QAP, если предположить, что потоки соединяют все предприятия только по одному кольцу, все потоки имеют одно и то же ненулевое (постоянное) значение и все расстояния равны соответствующие расстояния экземпляра TSP. Многие другие задачи стандартной комбинаторной оптимизации можно записать в этой форме.

Приложения

В дополнение к исходной формулировке местоположения завода, QAP представляет собой математическую модель проблемы размещения взаимосвязанных электронных компонентов на печатной плате или микрочипе , которая является частью размещения и маршрута этапа автоматизированного проектирования в электронной промышленности. .

См. также

• Задача о квадратичном назначении узких мест

Ссылки

Примечания

Источники

• Майкл Р. Гари и Дэвид С. Джонсон (1979). Компьютеры и трудноразрешимые проблемы: Руководство по теории NP-полноты . У. Х. Фриман. ISBN  0-7167-1045-5 . A2.5: ND43, стр. 218.

Внешние ссылки

• https://doi.org/10.7488/ds/3428 QAPLIB — библиотека задач квадратичного назначения
• http://www.wiomax.com/team/xie/maos-qap-quadratic-assignment-problem-project-portal/ MAOS-QAP — средство решения задач квадратичного присваивания на основе Java
• https://CRAN.R-project.org/package=qap - Пакет R qap: эвристика для квадратичной задачи о назначениях
• https://apps.microsoft.com/store/detail/qapsolver/9N7WMCFB6NZZ — метаэвристический решатель QAP для Windows 10/11