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

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

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

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

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

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

Примеры [ править ]

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

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

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

Формальное определение [ править ]

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

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

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

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

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

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

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

Алгоритмы [ править ]

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

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

Сбалансированное назначение [ править ]

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

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

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

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

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

Несбалансированное назначение [ править ]

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

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

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

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

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

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

Задачу о назначении можно решить, представив ее в виде линейной программы . Для удобства представим задачу максимизации. Каждое ребро ( i , j ), где i находится в A, а j находится в T, имеет вес . Для каждого ребра (i, j) у нас есть переменная _.Переменная равна 1, если край содержится в сопоставлении, и 0 в противном случае, поэтому мы устанавливаем ограничения домена: ${\ displaystyle w_ {ij}}$ ${\ displaystyle x_ {ij}}$ ${\ 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}}$

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

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

{\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\leq x_{ij}\leq 1{\text{ for }}i,j\in A,T,\,

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

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

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

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

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

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

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

Обобщение [ править ]

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

См. Также [ править ]

Алгоритм аукциона
Обобщенная проблема присваивания
Задача о линейном назначении узких мест
Транспортная задача Монжа-Канторовича , более общая постановка
Квадратичная задача о назначении
Максимальное соответствие по рангу
Проблема стабильного брака
Проблема стабильных соседей по комнате
Проблема с назначением цели оружия

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

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

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

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

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

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

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

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

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

[7] Варгас, Маркос C .; Валенсия, Карлос Э .; Perez, Sergio L .; Альфаро, Карлос А. (2018-10-08). «Эквивалентность двух классических алгоритмов для задачи о назначении». arXiv : 1810.03562v1 [ math.OC ].

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

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

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

[1]