Проблема с присвоением - Assignment problem

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

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

Как вариант, описав проблему с помощью теории графов:

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

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

Примеры

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

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

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

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

Формальное определение проблема назначения (или же линейная задача о назначении) является

Учитывая два набора, А и Т, равного размера, вместе с весовая функция C : А × Т → р. Найти биекция ж : А → Т так что функция стоимости:

{ Displaystyle сумма _ {а в А} С (а, е (а))}

сводится к минимуму.

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

{ displaystyle sum _ {a in A} C_ {a, f (a)}}

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

Алгоритмы

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

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

Сбалансированное назначение

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

Одним из первых полиномиальных алгоритмов сбалансированного назначения был алгоритм Венгерский алгоритм. Это Глобальный алгоритм - он основан на улучшении сопоставления по увеличивающимся путям (чередование путей между несовпадающими вершинами). Его сложность во время выполнения при использовании Куча Фибоначчи, является ${ Displaystyle О (мн + п ^ {2} журнал п)}$ ,^[2] куда м количество ребер. В настоящее время это самое быстрое время выполнения сильно полиномиальный алгоритм для этой проблемы. Если все веса являются целыми числами, время выполнения можно улучшить до ${ Displaystyle О (мн + п ^ {2} журнал журнал п)}$ , но полученный алгоритм является только слабо-полиномиальным.^[3] Если веса целые, а все веса не более C (куда C> 1 - некоторое целое число), то задача решается за ${ Displaystyle О (м { sqrt {n}} журнал (п cdot C))}$ слабо-полиномиальное время в методе, называемом масштабирование веса.^[4]^[5]^[6]

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

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

Как показали Малмулей, Вазирани и Вазирани,^[8] задача идеального совпадения минимального веса превращается в поиск несовершеннолетних в матрица смежности графа. С использованием лемма об изоляции, идеальное соответствие минимального веса в графе может быть найдено с вероятностью не менее 1/2. Для графика с п вершин, это требует ${ Displaystyle О ( журнал ^ {2} (п))}$ время.

Несбалансированное назначение

В задаче о несбалансированном назначении большая часть двудольного графа имеет п вершины и меньшая часть имеет р<п вершины. Также существует постоянный s что является не более чем максимальной мощностью сопоставления в графе. Цель состоит в том, чтобы найти подходящую по размеру минимальную стоимость s. Наиболее распространенный случай - это случай, когда граф допускает одностороннее идеальное соответствие (т. Е. Соответствие размера р), и s=р.

Несбалансированное назначение можно свести к сбалансированному назначению. Наивное сокращение состоит в том, чтобы добавить ${ displaystyle n-r}$ новые вершины к меньшей части и соедините их с большей частью, используя ребра стоимости 0. Однако для этого требуется ${ Displaystyle п (п-р)}$ новые края. Более эффективное сокращение называется техника удвоения. Вот новый график ГРАММ' построен из двух копий исходного графа грамм: прямая копия Gf и обратная копия Гб. Обратная копия «переворачивается», так что с каждой стороны ГРАММ', сейчас есть п+р вершины. Между копиями нам нужно добавить два вида связующих ребер:^[1]^:4–6

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

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

Вместо использования редукции проблема несбалансированного назначения может быть решена путем прямого обобщения существующих алгоритмов сбалансированного назначения. В Венгерский алгоритм можно обобщить, чтобы решить проблему в ${ displaystyle O (мс + s ^ {2} log r)}$ сильно полиномиальное время. В частности, если s=р тогда время выполнения ${ Displaystyle О (г-н + г ^ {2} журнал г)}$ . Если веса являются целыми числами, то метод Торупа можно использовать для получения времени выполнения ${ Displaystyle О (мс + s ^ {2} журнал журнал г)}$ .^[1]^:6

Решение методом линейного программирования

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

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

Чтобы гарантировать, что переменные действительно представляют собой идеальное соответствие, мы добавляем ограничения, говорящие, что каждая вершина смежна ровно с одним ребром в сопоставлении, т. Е. ${ 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, ,}$ .

В итоге получился такой LP:

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

{ displaystyle { text {при условии}} ~~ 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 0 leq x_ {ij} leq 1 { text {for}} i, j in A, T, ,}

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

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

Это тоже можно доказать напрямую.^[9]^:31–37 Позволять Икс - оптимальное решение дробной ЛП, ш (х) быть его общим весом, и к (х) - количество нецелых переменных. Если к (х)= 0 мы закончили. В противном случае есть дробная переменная, скажем ${ displaystyle x_ {i1, j2}}$ . Поскольку сумма переменных, смежных с j2 равно 1, что означает целое число, рядом с которым должна быть другая переменная. j2 с дробным значением, скажем ${ displaystyle x_ {i3, j2}}$ . По аналогичным соображениям относительно я3 должна быть другая переменная рядом с я3 с дробным значением, скажем ${ displaystyle x_ {i3, j4}}$ . По аналогичным соображениям мы переходим от одной вершины к другой, собирая рёбра с дробными значениями. Поскольку граф конечен, в какой-то момент у нас должен быть цикл. Без ограничения общности можно считать, что цикл заканчивается в вершине я1, поэтому последняя дробная переменная в цикле ${ displaystyle x_ {i1, j_ {2m}}}$ . Таким образом, количество ребер в цикле равно 2м - он должен быть четным, поскольку граф двудольный.

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

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

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

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

Обобщение

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

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

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

^ ^а ^б ^c ^d Лайл Рэмшоу, Роберт Э. Тарджан (2012). «О назначениях минимальной стоимости в несбалансированных двудольных графах» (PDF). Исследовательские лаборатории HP.
^ Фредман, Майкл Л .; Тарджан, Роберт Эндре (1987-07-01). «Кучи Фибоначчи и их использование в улучшенных алгоритмах оптимизации сети». J. ACM. 34 (3): 596–615. Дои:10.1145/28869.28874. ISSN 0004-5411. S2CID 7904683.
^ Торуп, Миккель (2004-11-01). «Очереди с целочисленным приоритетом с ключом уменьшения за постоянное время и проблема кратчайших путей из одного источника». Журнал компьютерных и системных наук. Спецвыпуск на STOC 2003. 69 (3): 330–353. Дои:10.1016 / j.jcss.2004.04.003. ISSN 0022-0000.
^ Gabow, H .; Тарьян, Р. (1989-10-01). «Более быстрые алгоритмы масштабирования для сетевых проблем». SIAM Журнал по вычислениям. 18 (5): 1013–1036. Дои:10.1137/0218069. ISSN 0097-5397.
^ Goldberg, A .; Кеннеди, Р. (1997-11-01). «Справка по глобальным обновлениям цен». Журнал SIAM по дискретной математике. 10 (4): 551–572. Дои:10.1137 / S0895480194281185. ISSN 0895-4801.
^ Орлин, Джеймс Б.; Ахуджа, Равиндра К. (1992-02-01). «Новые алгоритмы масштабирования для задач назначения и минимального среднего цикла». Математическое программирование. 54 (1–3): 41–56. Дои:10.1007 / BF01586040. ISSN 0025-5610. S2CID 18213947.
^ Варгас, Маркос С.; Валенсия, Карлос Э .; Perez, Sergio L .; Альфаро, Карлос А. (2018-10-08). «Эквивалентность двух классических алгоритмов для задачи о назначении». arXiv:1810.03562v1. Bibcode:2018arXiv181003562A. Цитировать журнал требует | журнал = (помощь)
^ Малмулей, Кетан; Вазирани, Умеш; Вазирани, Виджай (1987). «Сопоставление так же просто, как и обращение матрицы». Комбинаторика. 7 (1): 105–113. Дои:10.1007 / BF02579206. S2CID 47370049.CS1 maint: ref = harv (связь)
^ Гертнер, Бернд; Матушек, Иржи (2006). Понимание и использование линейного программирования. Берлин: Springer. ISBN 3-540-30697-8.
^ Дуан, Ран; Петти, Сет (01.01.2014). «Линейное приближение для согласования максимального веса» (PDF). Журнал ACM. 61: 1–23. Дои:10.1145/2529989. S2CID 207208641.

Бруальди, Ричард А. (2006). Комбинаторные матричные классы. Энциклопедия математики и ее приложений. 108. Кембридж: Издательство Кембриджского университета. 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.

[:0-1] а ^б ^c ^d Лайл Рэмшоу, Роберт Э. Тарджан (2012). «О назначениях минимальной стоимости в несбалансированных двудольных графах» (PDF). Исследовательские лаборатории HP.

[2] Фредман, Майкл Л .; Тарджан, Роберт Эндре (1987-07-01). «Кучи Фибоначчи и их использование в улучшенных алгоритмах оптимизации сети». J. ACM. 34 (3): 596–615. Дои:10.1145/28869.28874. ISSN 0004-5411. S2CID 7904683.

[3] Торуп, Миккель (2004-11-01). «Очереди с целочисленным приоритетом с ключом уменьшения за постоянное время и проблема кратчайших путей из одного источника». Журнал компьютерных и системных наук. Спецвыпуск на STOC 2003. 69 (3): 330–353. Дои:10.1016 / j.jcss.2004.04.003. ISSN 0022-0000.

[4] Gabow, H .; Тарьян, Р. (1989-10-01). «Более быстрые алгоритмы масштабирования для сетевых проблем». SIAM Журнал по вычислениям. 18 (5): 1013–1036. Дои:10.1137/0218069. ISSN 0097-5397.

[5] Goldberg, A .; Кеннеди, Р. (1997-11-01). «Справка по глобальным обновлениям цен». Журнал SIAM по дискретной математике. 10 (4): 551–572. Дои:10.1137 / S0895480194281185. ISSN 0895-4801.

[6] Орлин, Джеймс Б.; Ахуджа, Равиндра К. (1992-02-01). «Новые алгоритмы масштабирования для задач назначения и минимального среднего цикла». Математическое программирование. 54 (1–3): 41–56. Дои:10.1007 / BF01586040. ISSN 0025-5610. S2CID 18213947.

[7] Варгас, Маркос С.; Валенсия, Карлос Э .; Perez, Sergio L .; Альфаро, Карлос А. (2018-10-08). «Эквивалентность двух классических алгоритмов для задачи о назначении». arXiv:1810.03562v1. Bibcode:2018arXiv181003562A. Цитировать журнал требует | журнал = (помощь)

[8] Малмулей, Кетан; Вазирани, Умеш; Вазирани, Виджай (1987). «Сопоставление так же просто, как и обращение матрицы». Комбинаторика. 7 (1): 105–113. Дои:10.1007 / BF02579206. S2CID 47370049.CS1 maint: ref = harv (связь)

[9] Гертнер, Бернд; Матушек, Иржи (2006). Понимание и использование линейного программирования. Берлин: Springer. ISBN 3-540-30697-8.

[10] Дуан, Ран; Петти, Сет (01.01.2014). «Линейное приближение для согласования максимального веса» (PDF). Журнал ACM. 61: 1–23. Дои:10.1145/2529989. S2CID 207208641.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]