Проблема с назначением

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

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

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

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

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

Примеры

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

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

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

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

Формальное определение задачи назначения (или линейной задачи назначения ) следующее:

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

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

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

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

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

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

Алгоритмы

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

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

Алиса: Задача 1 = 1, Задача 2 = 2.
Джордж: Задача 1 = 5, Задача 2 = 8.

Жадный алгоритм назначит задачу 1 Алисе, а задачу 2 Джорджу, общая стоимость которых составит 9; но обратное присвоение имеет общую стоимость 7.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Общий вес соответствия составляет: $\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,\,$ .

В итоге имеем следующий ЛП:

${\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.$ Это целочисленная линейная программа. Однако мы можем решить ее без ограничений целочисленности (т. е. отбросить последнее ограничение), используя стандартные методы решения непрерывных линейных программ. Хотя эта формулировка допускает также дробные значения переменных, в этом особом случае ЛП всегда имеет оптимальное решение, где переменные принимают целые значения. Это связано с тем, что матрица ограничений дробной ЛП полностью унимодулярна – она удовлетворяет четырем условиям Хоффмана и Гейла.

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

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

Обобщение

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

Другое обобщение проблемы назначения — увеличение количества сопоставляемых наборов с двух до многих. Таким образом, вместо сопоставления агентов с задачами проблема расширяется до сопоставления агентов с задачами, временными интервалами и местоположениями. Это приводит к многомерной задаче назначения (MAP) .

См. также

Ссылки и дальнейшее чтение

^ Перейти обратно: ^а ^б ^с ^д Лайл Рэмшоу, Роберт Э. Тарджан (2012). «О заданиях с минимальной стоимостью в несбалансированных двудольных графах» (PDF) . Исследовательские лаборатории HP .
^ Фредман, Майкл Л.; Тарьян, Роберт Эндре (1 июля 1987 г.). «Кучи Фибоначчи и их использование в улучшенных алгоритмах оптимизации сети» . Дж. АКМ . 34 (3): 596–615. дои : 10.1145/28869.28874 . ISSN 0004-5411 . S2CID 7904683 .
^ Торуп, Миккель (1 ноября 2004 г.). «Очереди с целочисленными приоритетами с уменьшающимся ключом за постоянное время и проблема кратчайших путей из одного источника» . Журнал компьютерных и системных наук . Специальный выпуск STOC 2003. 69 (3): 330–353. дои : 10.1016/j.jcss.2004.04.003 . ISSN 0022-0000 .
^ Габоу, Х.; Тарьян, Р. (1 октября 1989 г.). «Алгоритмы более быстрого масштабирования для сетевых проблем». SIAM Journal по вычислительной технике . 18 (5): 1013–1036. дои : 10.1137/0218069 . ISSN 0097-5397 .
^ Гольдберг, А.; Кеннеди, Р. (1 ноября 1997 г.). «Помощь по обновлению глобальных цен». SIAM Journal по дискретной математике . 10 (4): 551–572. дои : 10.1137/S0895480194281185 . ISSN 0895-4801 .
^ Орлин, Джеймс Б.; Ахуджа, Равиндра К. (1 февраля 1992 г.). «Новые алгоритмы масштабирования для задач назначения и минимального среднего цикла». Математическое программирование . 54 (1–3): 41–56. дои : 10.1007/BF01586040 . ISSN 0025-5610 . S2CID 18213947 .
^ Альфаро, Карлос А.; Перес, Серхио Л.; Валенсия, Карлос Э.; Варгас, Маркос К. (01 июня 2022 г.). «Ещё раз к проблеме назначения» . Письма об оптимизации . 16 (5): 1531–1548. дои : 10.1007/s11590-021-01791-4 . ISSN 1862-4480 . S2CID 238644205 .
^ Малмули, Кетан ; Вазирани, Умеш ; Вазирани, Виджай (1987). «Сопоставление так же просто, как инверсия матрицы». Комбинаторика . 7 (1): 105–113. дои : 10.1007/BF02579206 . S2CID 47370049 .
^ Дуан, Ран; Петти, Сет (01 января 2014 г.). «Приближение линейного времени для согласования максимального веса» (PDF) . Журнал АКМ . 61 : 1–23. дои : 10.1145/2529989 . S2CID 207208641 .

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

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

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

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

[4] Габоу, Х.; Тарьян, Р. (1 октября 1989 г.). «Алгоритмы более быстрого масштабирования для сетевых проблем». SIAM Journal по вычислительной технике . 18 (5): 1013–1036. дои : 10.1137/0218069 . ISSN 0097-5397 .

[5] Гольдберг, А.; Кеннеди, Р. (1 ноября 1997 г.). «Помощь по обновлению глобальных цен». SIAM Journal по дискретной математике . 10 (4): 551–572. дои : 10.1137/S0895480194281185 . ISSN 0895-4801 .

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

[7] Альфаро, Карлос А.; Перес, Серхио Л.; Валенсия, Карлос Э.; Варгас, Маркос К. (01 июня 2022 г.). «Ещё раз к проблеме назначения» . Письма об оптимизации . 16 (5): 1531–1548. дои : 10.1007/s11590-021-01791-4 . ISSN 1862-4480 . S2CID 238644205 .

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

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

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]