Введение
Проблема комбинаторной оптимизации. Проблема квадратичного назначения (QAP) является одной из фундаментальных задач комбинаторной оптимизации в области оптимизации или исследования операций в математике, относящаяся к классу задач размещения объектов, впервые представленных Купмансом и Бекманном. Задача моделирует следующую реальную проблему: заданы множество из n объектов и множество из n мест. Для каждой пары мест указано расстояние, а для каждой пары объектов – вес или поток (например, объем поставок, транспортируемых между двумя объектами). Задача состоит в том, чтобы назначить все объекты различным местам таким образом, чтобы минимизировать сумму произведений расстояний на соответствующие потоки. Интуитивно, целевая функция стимулирует размещение объектов с высоким потоком между собой ближе друг к другу. Постановка задачи схожа с задачей назначения, за исключением того, что целевая функция выражена через квадратичные неравенства, что и обуславливает название.
The quadratic assignment problem (QAP) is one of the fundamental combinatorial optimization problems in the branch of optimization or operations research in mathematics, from the category of the facilities location problems first introduced by Koopmans and Beckmann. 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. Intuitively, the cost function encourages facilities with high flows between each other to be placed close together. The problem statement resembles that of the assignment problem, except that the cost function is expressed in terms of quadratic inequalities, hence the name.
Комплексность вычислений
Проблема является NP-трудной, поэтому не существует известного алгоритма для её решения за полиномиальное время, и даже небольшие экземпляры могут потребовать значительного времени вычислений. Также доказано, что для этой задачи не существует алгоритма приближения, работающего за полиномиальное время с каким-либо (постоянным) коэффициентом, если только P не равно NP. Задача коммивояжера (TSP) можно рассматривать как частный случай QAP, если предположить, что потоки соединяют все объекты только по одному кольцу, все потоки имеют одинаковое ненулевое (постоянное) значение, а все расстояния равны соответствующим расстояниям в экземпляре TSP. Многие другие задачи стандартной комбинаторной оптимизации также могут быть представлены в этой форме.
Приложения
В дополнение к исходной формулировке задачи о размещении предприятия, QAP — это математическая модель для задачи размещения взаимосвязанных электронных компонентов на печатной плате или микросхеме, являющаяся частью этапа трассировки и размещения при автоматизированном проектировании в электронной промышленности.