Проблема присваивания

редактировать

Задача комбинаторной оптимизации

Задача присваивания является фундаментальной комбинаторной оптимизацией проблема. В наиболее общем виде проблема выглядит следующим образом:

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

В качестве альтернативы, описывая проблему с использованием теории графов:

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

Если количество агентов и задач равно, то проблема называется сбалансированным распределением. В противном случае это называется несбалансированным назначением. Если общая стоимость назначения для всех задач равна сумме затрат для каждого агента (или сумме затрат для каждой задачи, что в данном случае одно и то же), то задача называется линейным назначением. Обычно, говоря о задаче о назначении без каких-либо дополнительных уточнений, имеется в виду линейная сбалансированная задача о назначении.

Содержание

1 Примеры
2 Формальное определение
3 Алгоритмы
- 3.1 Сбалансированное присвоение
- 3.2 Несбалансированное назначение
- 3.3 Решение посредством линейного программирования
- 3.4 Другие методы и алгоритмы аппроксимации
4 Обобщение
5 См. Также
6 Ссылки и дополнительная литература

Примеры

Предположим, что у таксомоторной компании есть три доступных такси (агентов) и три клиента (задачи), желающие быть поднятым как можно скорее. Фирма гордится своей быстрой доставкой, поэтому для каждого такси «стоимость» встречи с конкретным клиентом будет зависеть от времени, затрачиваемого такси на то, чтобы добраться до места посадки. Это проблема сбалансированного распределения. Ее решение - какое бы сочетание такси и клиентов ни привело к наименьшим общим затратам.

Теперь предположим, что есть четыре такси, но все еще только три клиента. Это проблема несбалансированного назначения. Один из способов решить эту проблему - изобрести четвертую фиктивную задачу, которая, возможно, называется «сидеть и ничего не делать», с назначенной ей стоимостью такси 0. Это сводит проблему к проблеме сбалансированного распределения, которая затем может быть решена обычным способом и по-прежнему дает наилучшее решение проблемы.

Аналогичные настройки могут быть выполнены для того, чтобы разрешить больше задач, чем агентов, задач, которым должно быть назначено несколько агентов (например, группа из большего количества клиентов, чем может поместиться в одном такси), или максимизации прибыли, а не минимизация стоимости.

Формальное определение

Формальное определение задачи о назначении (или линейной задачи о назначении ):

Даны два набора, A и T, равных size вместе с весовой функцией C: A × T → R. Найдите биекцию f: A → T, такую, что функция стоимости :

∑ a ∈ AC (a, f (a)) {\ displaystyle \ sum _ {a \ in A} C (a, f (a))}

\ sum _ {{a \ in A}} C (a, f (a))

минимизировано.

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

∑ a ∈ AC a, f (a) {\ displaystyle \ sum _ {a \ in A} C_ {a, f (a)}}

\ sum _ {{a \ in A}} C _ {{a, f (a)}}

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

Алгоритмы

Наивное решение проблемы назначения состоит в том, чтобы проверить все назначения и рассчитать стоимость каждого из них. Это может быть очень неэффективно, поскольку при n агентах и n задачах n! (факториал n) разные присваивания. К счастью, существует множество алгоритмов решения задачи за время, полиномиальное от n.

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

Сбалансированное присваивание

В задаче сбалансированного присваивания обе части двудольного графа имеют одинаковое количество вершин, обозначенное n.

Одним из первых полиномиальных алгоритмов сбалансированного присвоения был венгерский алгоритм. Это глобальный алгоритм - он основан на улучшении сопоставления по увеличивающимся путям (чередование путей между несовпадающими вершинами). Его сложность во время выполнения при использовании кучи Фибоначчи составляет $O (mn + n 2 log ⁡ n) {\ displaystyle O (mn + n ^ {2} \ log n)}$ ${\ displaystyle O (mn + n ^ {2} \ log n)}$ , где m - количество ребер. В настоящее время это самое быстрое время выполнения строго полиномиального алгоритма для этой проблемы. Если все веса являются целыми числами, время выполнения можно улучшить до $O (mn + n 2 log ⁡ log ⁡ n) {\ displaystyle O (mn + n ^ {2} \ log \ log n)}$ ${\ displaystyle O ( мн + п ^ {2} \ журнал \ журнал п)}$ , но полученный алгоритм является только слабо-полиномиальным. Если веса являются целыми числами и все веса не превосходит C (где C>1 - некоторое целое число), то проблема может быть решена за $O (mn log ⁡ (n ⋅ C)) {\ displaystyle O (m {\ sqrt {n}} \ log (n \ cdot C))}$ ${\ displaystyle O (m {\ sqrt {n}} \ log (n \ cdot C))}$ слабо-полиномиальное время в методе, называемом масштабированием веса.

В дополнение к глобальным методам существуют локальные методы, основанные на поиске локальных обновлений (а не на полных путях дополнения). Эти методы имеют худшие асимптотические гарантии времени выполнения, но на практике они часто работают лучше. Эти алгоритмы называются алгоритмами аукциона, алгоритмами push-relabel или алгоритмами предварительного потока. Было показано, что некоторые из этих алгоритмов эквивалентны.

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

Как показали Малмули, Вазирани и Вазирани, проблема идеального соответствия с минимальным весом преобразуется в поиск миноров в матрице смежности графа. Используя лемму об изоляции, идеальное соответствие минимального веса в графе может быть найдено с вероятностью не менее 1/2. Для графа с n вершинами требуется $O (log 2 ⁡ (n)) {\ displaystyle O (\ log ^ {2} (n))}$ ${\ displaystyle O (\ log ^ {2} (n))}$ времени.

Несбалансированное присвоение

В задаче несбалансированного присвоения большая часть двудольного графа имеет n вершин, а меньшая часть - r

Несбалансированное назначение может быть сокращено до сбалансированного назначение. Наивное сокращение состоит в том, чтобы добавить $n - r {\ displaystyle nr}$ $nr$ новых вершин к меньшей части и соединить их с большей частью, используя ребра стоимости 0. Однако для этого требуется $n (n - r) {\ displaystyle n (nr)}$ ${\ displaystyle n (nr)}$ новые ребра. Более эффективное сокращение называется методом удвоения. Здесь новый граф G 'построен из двух копий исходного графа G: прямой копии Gf и обратной копии Gb. Обратная копия «переворачивается», так что на каждой стороне G 'теперь есть n + r вершин. Между копиями нам нужно добавить два типа связывающих ребер:

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

Всего требуется не более $n + r {\ displaystyle n + r}$ $n + r$ новых ребер. Результирующий граф всегда имеет идеальное соответствие размера $n + r {\ displaystyle n + r}$ $n + r$ . Идеальное соответствие с минимальной стоимостью в этом графе должно состоять из сопоставлений с минимальной стоимостью и максимальной мощностью в Gf и Gb. Основная проблема с этой техникой удвоения заключается в том, что нет увеличения скорости, когда $r ≪ n {\ displaystyle r \ ll n}$ ${\ displaystyle r \ ll n}$ .

Вместо использования сокращения проблема несбалансированного присваивания может быть решена путем прямого обобщения существующих алгоритмов для сбалансированное назначение. Венгерский алгоритм может быть обобщен для решения проблемы в $O (ms + s 2 log ⁡ r) {\ displaystyle O (ms + s ^ {2} \ log r)}$ ${\ displaystyle O (ms + s ^ {2} \ log r)}$ сильно полиномиальное время. В частности, если s = r, то время выполнения будет $O (m r + r 2 log ⁡ r) {\ displaystyle O (mr + r ^ {2} \ log r)}$ ${\ displaystyle O (mr + r ^ {2} \ log r)}$ . Если веса являются целыми числами, то метод Торупа можно использовать для получения времени выполнения $O (ms + s 2 log ⁡ log ⁡ r) {\ displaystyle O (ms + s ^ {2} \ log \ log r) }$ ${\ displaystyle O (ms + s ^ {2} \ log \ log r)}$ .

Решение с помощью линейного программирования

Задачу о назначении можно решить, представив ее в виде линейной программы. Для удобства представим задачу максимизации. Каждое ребро (i, j), где i находится в A, а j находится в T, имеет вес $w i j {\ displaystyle w_ {ij}}$ $w_ {ij}$ . Для каждого ребра (i, j) у нас есть переменная $xij {\ displaystyle x_ {ij}}$ $x_ {ij}$ .Переменная равна 1, если ребро содержится в сопоставлении, и 0 в противном случае, поэтому мы устанавливаем ограничения домена: $0 ≤ xij ≤ 1 для i, j ∈ A, T, {\ displaystyle 0 \ leq x_ {ij} \ leq 1 {\ text {for}} i, j \ in A, T, \,}$ ${\ displaystyle 0 \ leq x_ {ij} \ leq 1 {\ text {for}} i, j \ in A, T, \,}$ $xij ∈ Z для i, j ∈ A, T. {\ displaystyle x_ {ij} \ in \ mathbb {Z} {\ text {for}} i, j \ in A, T.}$ ${\ displaystyle x_ {ij} \ in \ mathbb { Z} {\ text {for}} i, j \ in A, T.}$

Общий вес соответствия: $∑ (i, j) ∈ A × T wijxij {\ displaystyle \ sum _ {(i, j) \ in A \ times T} w_ {ij} x_ {ij}}$ ${\ displaystyle \ sum _ {(i, j) \ in A \ times T} w_ {ij} x_ {ij}}$ . Цель состоит в том, чтобы найти идеальное совпадение с максимальным весом.

Чтобы гарантировать, что переменные действительно представляют идеальное соответствие, мы добавляем ограничения, говорящие, что каждая вершина смежна ровно с одним ребром в сопоставлении, т. Е. $∑ j ∈ T xij = 1 для i ∈ A, ∑ я ∈ A xij = 1 для j ∈ T, {\ displaystyle \ sum _ {j \ in T} x_ {ij} = 1 {\ text {for}} i \ in A, \, ~~~ \ sum _ {i \ in A} x_ {ij} = 1 {\ text {for}} j \ in T, \,}$ ${\ displaystyle \ sum _ {j \ in T} x_ {ij} = 1 {\ text {for}} i \ in A, \ ~~~ \ sum _ {я \ in A} x_ {ij} = 1 {\ text {for}} j \ in T, \,}$ .

В итоге получаем следующий LP:

максимизировать ∑ (i, j) ∈ A × T wijxij {\ displaystyle {\ text {maximize}} ~~ \ sum _ {(i, j) \ in A \ times T} w_ {ij} x_ {ij}}

{\ displaystyle {\ text {maximize}} ~~ \ sum _ {(i, j) \ in A \ times T} w_ {ij} x_ { ij}}

при условии ∑ j ∈ T xij = 1 для i ∈ A, ∑ i ∈ A xij = 1 для j ∈ T {\ displaystyle {\ text {subject to}} ~~ \ sum _ {j \ in T} x_ {ij} = 1 {\ текст {for}} i \ in A, \, ~~~ \ sum _ {i \ in A} x_ {ij} = 1 {\ text {for}} j \ in T}

{\ displaystyle {\ text {subject to}} ~~ \ sum _ {j \ in T} x_ {ij} = 1 {\ text {for}} i \ in A, \, ~~~ \ sum _ {i \ in A} x_ {ij} = 1 {\ text {for}} j \ in T}

0 ≤ xij ≤ 1 для i, j ∈ A, T, {\ displaystyle 0 \ leq x_ {ij} \ leq 1 {\ text {for}} i, j \ in A, T, \,}

{\ displaystyle 0 \ leq x_ {ij} \ leq 1 {\ text {for}} i, j \ in A, T, \,}

xij ∈ Z для i, j ∈ A, T. {\ displaystyle x_ {ij} \ in \ mathbb {Z} {\ text {for}} i, j \ in A, T.}

{\ displaystyle x_ {ij} \ in \ mathbb { Z} {\ text {for}} i, j \ in A, T.}

Это целочисленная линейная программа. Тем не менее, мы можем решить ее без ограничений целостности (т. Е. Отбросить последнее ограничение), используя стандартные методы решения непрерывных линейных программ. Хотя эта формулировка допускает также дробные значения переменных, в этом частном случае LP всегда имеет оптимальное решение, в котором переменные принимают целые значения. Это связано с тем, что матрица ограничений дробного LP полностью унимодулярна - она удовлетворяет четырем условиям Хоффмана и Гейла.

Это тоже можно доказать напрямую. Пусть x - оптимальное решение дробной LP, w (x) - его общий вес, а k (x) - количество нецелых переменных. Если k (x) = 0, все готово. В противном случае существует дробная переменная, например $x i 1, j 2 {\ displaystyle x_ {i1, j2}}$ ${\ displaystyle x_ {i1, j2}}$ . Поскольку сумма переменных, смежных с j2, равна 1, что в целочисленном значении, должна быть другая переменная, смежная с j2, с дробным значением, например $xi 3, j 2 {\ displaystyle x_ {i3, j2}}$ ${\ displaystyle x_ {i3, j2}}$ . По аналогичным соображениям относительно i3, должна быть другая переменная рядом с i3 с дробным значением, скажем $x i 3, j 4 {\ displaystyle x_ {i3, j4}}$ ${\ displaystyle x_ {i3, j4} }$ . По аналогичным соображениям мы переходим от одной вершины к другой, собирая рёбра с дробными значениями. Поскольку граф конечен, в какой-то момент у нас должен быть цикл. Без ограничения общности мы можем предположить, что цикл заканчивается в вершине i1, поэтому последняя дробная переменная в цикле равна $xi 1, j 2 m {\ displaystyle x_ {i1, j_ {2m}}}$ ${\ Displaystyle х _ {i1, j_ {2m}}}$ . Таким образом, количество ребер в цикле равно 2m - оно должно быть четным, поскольку граф двудольный.

Предположим, мы добавляем некоторую константу e ко всем четным переменным в цикле и удаляем ту же константу e из всех нечетных переменных в цикле. Для любого такого e сумма переменных около каждой вершины остается прежней (1), поэтому ограничения на вершины по-прежнему выполняются. Более того, если e достаточно мало, все переменные остаются в пределах от 0 до 1, поэтому ограничения области все еще выполняются. Легко найти наибольшее e, которое поддерживает ограничения области: это либо наименьшая разница между нечетной переменной и 0, либо наименьшая разница между четной переменной и 1. Теперь у нас на одну дробную переменную меньше, поэтому k ( x) уменьшается на 1. Целевое значение остается прежним, поскольку в противном случае мы могли бы увеличить его, выбрав e как положительное или отрицательное, что противоречит предположению, что оно является максимальным.

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

Другие методы и алгоритмы аппроксимации

Существуют другие подходы к задаче назначения, которые рассмотрены Дуаном и Петти (см. Таблицу II). В их работе предлагается алгоритм аппроксимации для задачи присваивания (и более общая задача сопоставления максимального веса ), который выполняется за линейное время для любой фиксированной границы ошибки.

Обобщение

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

См. Также

Ссылки и дополнительная литература

Бруальди, Ричард А. (2006). Комбинаторные матричные классы. Энциклопедия математики и ее приложений. 108 . Кембридж: Cambridge University Press. ISBN 978-0-521-86565-4. Zbl 1106.05001.
Буркард, Райнер ; М. Делль'Амико; С. Мартелло (2012). Проблемы с назначением (Пересмотренная перепечатка). СИАМ. ISBN 978-1-61197-222-1.
Берцекас, Дмитрий (1998). Оптимизация сети: непрерывные и дискретные модели. Athena Scientific. ISBN 978-1-886529-02-1.