Задача о назначении

Комбинаторная задача оптимизации

Рабочий пример распределения задач между неравным числом работников с использованием венгерского метода

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

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

Альтернативный вариант описания проблемы с использованием теории графов:

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

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

Примеры

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

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

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

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

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

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

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

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

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

${\displaystyle \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 .

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

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

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

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

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

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

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

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

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

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

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

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

Чтобы гарантировать, что переменные действительно представляют собой идеальное паросочетание, мы добавляем ограничения, говорящие, что каждая вершина смежна ровно с одним ребром в паросочетании, т. е . . $${\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{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}$$ $${\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] (см. Таблицу II). Их работа предлагает алгоритм приближения для задачи назначения (и более общей задачи максимального соответствия веса ), который выполняется за линейное время для любой фиксированной границы ошибки.

Обобщение

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

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

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

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

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

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. Торуп, Миккель (2004-11-01). «Целочисленные приоритетные очереди с уменьшающимся ключом за постоянное время и проблема кратчайших путей из одного источника». Журнал компьютерных и системных наук . Специальный выпуск по STOC 2003. 69 (3): 330–353. doi : 10.1016/j.jcss.2004.04.003 . ISSN  0022-0000.
4. Габов, Х.; Тарьян, Р. (1989-10-01). «Более быстрые алгоритмы масштабирования для сетевых задач». Журнал SIAM по вычислениям . 18 (5): 1013–1036. doi :10.1137/0218069. ISSN  0097-5397.
5. Голдберг, А.; Кеннеди, Р. (1997-11-01). «Глобальные обновления цен помогают». Журнал SIAM по дискретной математике . 10 (4): 551–572. doi :10.1137/S0895480194281185. ISSN  0895-4801.
6. Орлин, Джеймс Б.; Ахуджа, Равиндра К. (1992-02-01). «Новые алгоритмы масштабирования для задач назначения и минимального среднего цикла». Математическое программирование . 54 (1–3): 41–56. doi :10.1007/BF01586040. ISSN  0025-5610. S2CID  18213947.
7. Альфаро, Карлос А.; Перес, Серхио Л.; Валенсия, Карлос Э.; Варгас, Маркос К. (2022-06-01). «Повторное рассмотрение проблемы назначения». Optimization Letters . 16 (5): 1531–1548. doi :10.1007/s11590-021-01791-4. ISSN  1862-4480. S2CID  238644205.
8. Малмули, Кетан ; Вазирани, Умеш ; Вазирани, Виджай (1987). «Сопоставление так же просто, как инверсия матрицы». Комбинаторика . 7 (1): 105–113. дои : 10.1007/BF02579206. S2CID  47370049.
9. Дуань, Ран; Петти, Сет (2014-01-01). "Линейное приближение по времени для максимального соответствия весов" (PDF) . Журнал ACM . 61 : 1–23. doi :10.1145/2529989. S2CID  207208641.

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