Квадратичная задача о назначении

Комбинаторная задача оптимизации

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

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

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

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

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

Формальное математическое определение

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

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

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

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

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

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

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

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

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

Сложность вычислений

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

Приложения

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

QAP также использовался для моделирования стоимости размещения символов на клавиатуре. В этом случае местоположениями являются клавиши на клавиатуре, а их парные расстояния соответствуют времени, необходимому для нажатия данной пары клавиш. Объектами являются символы, а их веса пропорциональны частоте появления данной пары символов в текстовом корпусе. Этот тип модели QAP использовался при разработке французского стандарта клавиатуры (NF Z71-300). ^[3]

Смотрите также

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

Ссылки

1. Купманс TC, Бекманн M (1957). Задачи назначения и размещение экономической деятельности. Econometrica 25(1):53-76
2. Сахни, Сартай; Гонсалес, Теофило (июль 1976 г.). «P-полные аппроксимационные задачи». Журнал ACM . 23 (3): 555–565. doi :10.1145/321958.321975. hdl : 10338.dmlcz/103883 .
3. Джон, Максимилиан; Карренбауэр, Андреас (2019). «Динамическое разрежение для квадратичных задач о назначениях». Математическая теория оптимизации и исследование операций (PDF) . Том 11548. Cham: Springer International Publishing. стр. 232–246. doi :10.1007/978-3-030-22629-9_17. ISBN 978-3-030-22628-2.

Другие источники

• Майкл Р. Гэри и Дэвид С. Джонсон (1979). Компьютеры и неразрешимость: Руководство по теории NP-полноты . WH Freeman. 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