Линейная задача о назначениях в узких местах

В комбинаторной оптимизации под линейной задачей о назначениях на узкие места (linear bottleneck assignment problem, LBAP) понимается задача, похожая на задачу о назначениях^[1].

В простых словах задача ставится следующим образом:

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

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

Линейная задача о назначениях на узкие места была впервые изложена Фалкерсоном (Fulkerson), Гликсбергом (Glicksberg) и Гроссом (Gross) в работе, посвящённой распределению работ по машинам с целью минимизировать время выполнения заказа^[2].

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

Формальное определение задачи о назначениях на узкие места выглядит следующим образом:

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

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

минимальна.

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

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

Формулировка задачи как задачи математического программирования

\min \,\max _{i,j}c_{i,j}x_{i,j}

при условиях:

\sum _{j=1}^{n}x_{i,j}=1\ (i=1,2,\dots ,n),

\sum _{i=1}^{n}x_{i,j}=1\ (j=1,2,\dots ,n),

x_{i,j}\in \{0,1\}\ (i,j=1,2,\dots ,n)

Методы решения

Для решения задачи полезна следующая лемма:

Лемма.^[1] Пусть $C=(c_{i,j})$ — матрица цен задачи, Тогда

1. Оптимальное значение задачи определяется одним из элементов матрицы

c_{i,j}

.

2. Оптимальное решение зависит только от относительного порядка элементов матрицы, а не от их числовых значений

Пример. Пусть задана матрица

$C={\begin{pmatrix}\pi &{\sqrt {3}}&54392\\0&e^{3}&e^{3}\\{-}2&\sin {(\pi /8)}&4\\\end{pmatrix}}$

Упорядочиваем элементы матрицы $-2<0<\sin {(\pi /8)}<{\sqrt {3}}<\pi <4<e^{3}=e^{3}<54392$ .

Заменяем наименьший элемент −2 на 0, следующий за ним 0 заменяем на 1, затем $\sin {(\pi /8)}$ заменяем на 2 и так далее. Получим следующую матрицу: $C'={\begin{pmatrix}4&3&7\\1&6&6\\0&2&5\\\end{pmatrix}}$ .

Оптимальным решением задачи будет перестановка {2, 1, 3} с максимальным значением для матрицы $C'$ 5, что соответствует значению 4 в исходной матрице $C$ .

Пороговый алгоритм

Идея использования метода пороговых значений принадлежит Гарфинкелю (Garfinkel)^[3].

Присваиваем начальные значения  $t_{\min }=\min _{i,j}{c_{i,j}},t_{\max }=\max _{i,j}{c_{i,j}}$ .
Если  $t_{\min }=t_{\max }$ , то
  оптимальное значение =  $t_{\min }$  и любая перестановка {1, 2, . . . , n} оптимальна.
В противном случае, 
  пока существуют  $c_{i,j}:t_{\min }<c_{i,j}<t_{\max }$ , выполнить
    Находим медиану, t чисел  $t_{\min }<c_{i,j}<t_{\max }$ 
    Строим граф  $T$ 
    Если  $T$  содержит совершенное паросочетание, то принимаем 
       $t_{\min }=t$ 
    иначе принимаем 
       $t_{\max }=t$  
    конец если
  конец цикла
  Если проверка существования совершенного паросочетания для   $t_{\min }$  не выполнялась, выполним её.
  Строим граф  $T$  для  $t_{\min }$ 
  Если  $T$  содержит совершенное паросочетание, принимаем
     $t_{\max }=t_{\min }$ 
  конец если
конец если

Оптимальное значение будет равно $t_{\max }$ , и оптимальное решение можно найти из соответствующего графа.

Как видим, на каждом шаге цикла 'пороговый алгоритм' проходит два этапа. На первом этапе выбирается 'пороговое значение' $t$ и 'пороговая матрица' $T$ , которая определяется следующим образом:

T_{i,j}=

1, если

c_{ij}>t

0 в противном случае.

На втором этапе проверяется, существует ли назначение с нулевой ценой (для матрицы цен $T$ ). Для проверки этого конструируется двудольный граф G = (U, V; E) с |U| = |V| = n и дуги $[i,j]\in E$ тогда и только тогда, когда $T_{i,j}=0$ . (Другими словами, мы должны проверить, содержит ли двудольный граф, соответствующий пороговой матрице, совершенное паросочетание или нет). Минимальное пороговое значение $t$ , для которого соответствующий двудольный граф содержит совершенное паросочетание, является оптимальным значением задачи. Существует несколько путей реализации порогового алгоритма. Одна из возможностей — использовать двоичный поиск на первом этапе. Это приведёт к $O(M(n)\log(n))$ алгоритму, где $M(n)$ — временна́я сложность проверки существования совершенного паросочетания. Мы можем использовать матричный алгоритм Ибарра и Морана^[4] для выяснения, существует ли совершенное паросочетание. Тогда оптимальное решение может быть найдено с битовой сложностью $O(n^{\beta }\log ^{k}n)$ . Для умножения двух n × n матриц нужно $O(n^{\beta })$ арифметических операций и k — некоторое целое число, возникающее из действий над длинными целыми числами. Копперсмит (Coppersmith) и Виноград (Winograd)^[5] показали, что умножение матриц можно сделать с $\beta =2{,}376$ . Если мы хотим получить соответствующее оптимальное решение, мы можем использовать метод Альта, Блюма, Мелхорна и Паула (Alt, Blum, Mehlhorn, Paul)^[6] и получим полную сложность $O\left(n^{2{,}5}\left/{\sqrt {\log(n)}}\right.\right)$ в случае плотной матрицы. Здесь плотность означает, что число ненулевых элементов $T_{i,j}$ матрицы равно $O(n^{2})$ .

Этот метод теоретически является лучшим из известных методов решения задачи.

Двойственный алгоритм

Тесно связан с пороговым методом следующий двойственный алгоритм.

Вычислим  $t=\max _{k=1,2,\dots ,n}(\min _{r=1,2,\dots ,n}c_{r,k},\min _{j=1,2,\dots ,n}c_{k,j})$ 
Положим  $M=\varnothing$   (пустое множество).
Пока |M| < n, выполнять
  Определим двудольный граф G, соответствующий пороговому значению t.
  Найдем максимальное паросочетание в G.
  Если |M| < n, то
    Пусть  $R\subseteq U$  и  $J\subseteq V$  — множества вершин в минимальном покрытии графа G.
    Положим  $t=\min _{r\in R,j\in J}c_{r,j}$ 
  конец если
конец цикла

Алгоритм использует некоторую информацию о пороговом значении t, а именно — тот факт, что оптимальное значение не может быть меньше максимального значения из минимальных элементов в строках, а также максимального значения из минимальных элементов в столбцах матрицы C. Таким образом, в качестве первого порогового значения можно взять $t=\max _{1\leqslant k\leqslant n}(\min _{1\leqslant r\leqslant n}c_{r,k},\min _{1\leqslant j\leqslant n}c_{k,j})$

Двойтвенный метод начинает с этого значения t и создаёт минимальные наборы (индексов) столбцов $J$ и строк $R$ , покрывающие все элементы матрицы $c_{r,j}\leqslant t$ . Это можно сделать, найдя максимальный набор дуг в графе G, задающих паросочетание. Здесь граф G — это двудольный граф с дугами (r,j), для которых $c_{r,j}\leqslant t$ . Если паросочетание не содержит все строки и столбцы, существуют элементы матрицы, определяющие оптимальное значение, и эти элементы больше t. Вследствие этого, мы можем принять новое значение $t=\min _{r\in R,j\in J}c_{r,j}$ и построить новый граф G. Этот граф содержит все рёбра предыдущего графа и как минимум одно новое ребро, так что мы можем начать поиск максимального паросочетания с уже найденного на предыдущем шаге. Продолжаем, пока не найдём совершенное паросочетание.

Алгоритм последовательных приращений

Ещё одним подходом к решению задачи может служить использование идей венгерского метода^[7]. В России этот метод известен под названием 'Алгоритм Гросса'. Изложим метод в реализации Деригса и Циммермана^[8].

Введём несколько определений.

Дополняющим путём паросочетания называется путь, содержащий дуги паросочетания, при этом из двух соседних дуг одна обязательно принадлежит паросочетанию (т.е. дуги перемежаются — за дугой из паросочетания идёт дуга, не принадлежащая ему, и наоборот).

Пусть $P=([i_{1},j_{1}],[i_{2},j_{1}],[i_{2},j_{2}],\dots ,[i_{k},j_{k}])$ — дополняющий путь для паросочетания M.

Размер узкого места $\ell (P)$ определяется как

\ell (P)=\max(c([i_{1},j_{1}]),c([i_{2},j_{2}]),\dots ,c([i_{k},j_{k}]))

.

Дополняющий путь называется b-кратчайшим путём, если размер узкого места минимален среди всех дополняющих путей M.

Пусть  $G=(U,V;E)$  — двудольный граф с длинами дуг  $c_{i,j}$  для дуг  $[i,j]\in E$ 
Найдем нижнюю границу t для целевой функции
     (т.е.  $t=\max {(\max _{u\in U}\min _{v\in V}c_{u,v},\max _{v\in V}\min _{u\in U}c_{u},v)}$ )
Находим максимальное паросочетание M в графе G, имеющего дуги [i, j] если  $c_{i,j}\leqslant t$ 
если |M| = |U|, то мы получили оптимальное решение t с оптимальным отношением M, и завершаем работу.
конец если
Пусть L — множество элементов U, для которых нет паросочетания.
пока L не пусто, выполнить
  Выберем вершину  $i\in L$ 
  Положим  $L=L\backslash \{i\}$ 
  P = Dijkstra(i)
  Комментарий: Функция Dijkstra(i) возвращает дополняющий путь, начинающийся в вершине i
  Если путь не найден, то
    Положим  $M=M\ominus P$ 
    Положим  $t=\max(t,\ell (P))$ 
  конец если
конец пока
Комментарий: M — максимальное паросочетание с минимальной ценой t.

B-кратчайший дополняющий путь находится функцией Dijkstra().

Во время поиска b-кратчайшего пути помечаем вершину $x\in U$ значением $({\overline {\alpha }}(x),{\overline {\beta }}(x))$ , где ${\overline {\alpha }}(x)$ является размером узкого места b-кратчайшего пути из $i_{1}$ в эту вершину, а ${\overline {\beta }}(x)$ означает непосредственного предшественника в b-кратчайшем пути из $i_{1}$ в вершину $x$ .

Аналогичным образом помечаем вершину $x\in V$ значением $(\alpha (x),\beta (x))$ , где $\alpha (x)$ является размером узкого места b-кратчайшего пути из $i_{1}$ в эту вершину, а $\beta (x)$ означает непосредственного предшественника в b-кратчайшем пути из $i_{1}$ в вершину $x$ .

Функция Dijkstra(i)
Комментарий: Модифицированный алгоритм Дейкстры для задачи о назначениях для узких мест.
Помечаем все вершины  $j\in V$ , положив  $(\alpha (j),\beta (j))=(\infty ,\varnothing )$ .
Положим R = V Комментарий: R содержит непросмотренные вершины V
α(i) = t, P = пусто
Для всех соседей  $j\in R$  вершины i выполнить
  Если  $\alpha (j)>\max({\overline {\alpha }}(i),c_{i,j})$ , то
    Положим  $\alpha (j)=\max({\overline {\alpha }}(i),c_{i,j})$ 
     $\beta (j)=i$ 
  конец если
конец цикла
пока R пусто, выполнять
  Найдём вершину  $r\in R$  с минимальным  $\alpha (r)$ ;
  Если  $\alpha (r)=\infty$ , то 
    Положим  $R=\varnothing$ 
  иначе
    если r не входит в паросочетание, то
      Находим путь P, образованный последовательностью вершин  $(i,\dots ,{\overline {\beta }}(\beta (r)),\beta (r),r)$ 
      Положим  $\ell (P)=\alpha (r)$ 
       $R=\varnothing$ 
    Иначе
      Пусть [s, r] — ребро паросочетания
      Помечаем s:  $({\overline {\alpha }}(s),{\overline {\beta }}(s))=(\alpha (r),r)$ 
      Положим  $R=R\backslash \{r\}$ 
      Для всех соседей  $j\in R$  вершины s выполнить
        Если  $\alpha (j)>\max({\overline {\alpha }}(s),c_{s,j})$ , то
          Положим  $\alpha (j)=\max({\overline {\alpha }}(s),c_{s,j})$ 
           $\beta (j)=s$ 
        конец если
      конец цикла
    конец если
  конец если
конец пока

Асимптотическое поведение

Пусть $c_{n}^{*}$ обозначает оптимальное значение функции для n исполнителей и n работ. Если цены $c_{ij}$ выбираются из равномерного распределения на отрезке (0,1), то^[9]

E[c_{n}^{*}]={\frac {\log n+\log 2+\gamma }{n}}+O\left({\frac {(\log n)^{2}}{n^{7/5}}}\right)

и

\mathrm {Var} [c_{n}^{*}]={\frac {\zeta (2)-2(\log 2)^{2}}{n^{2}}}+O\left({\frac {(\log n)^{2}}{n^{7/3}}}\right).

Ссылки

↑ ¹ ² Assignment Problems Архивная копия от 8 июля 2013 на Wayback Machine, Rainer Burkard, Mauro Dell’Amico, Silvano Martello, 2009, глава 6.2 «Linear Bottleneck Assignment Problem» (стр. 172)
↑ D.R. Fulkerson, I. Glicksberg, and O. Gross. A production line assignment problem. Tech. Rep. RM-1102, The Rand Corporation, Santa Monica, CA, 1953.)
↑ R. Garfinkel. An improved algorithm for the bottleneck assignment problem. Oper. Res., 19:1747–1751, 1971.
↑ O.H. Ibarra and S. Moran. Deterministic and probabilistic algorithms for maximum bipartite matching via fast matrix multiplication. Inform. Process. Lett., 13:12–15, 1981.
↑ D. Coppersmith and S.Winograd. Matrix multiplication via arithmetic progressions. J. Symbolic Computing, 9:251–280, 1990.
↑ H. Alt, N. Blum, K. Mehlhorn, and M. Paul. Computing a maximum cardinality matching in a bipartite graph in time $O\left(n^{1{,}5}{\sqrt {m/\log n}}\right)$ . Inform. Process. Lett., 37:237–240, 1991.
↑ O. Gross. The bottleneck assignment problem. Tech. Rep. P-1630, The Rand Corporation,Santa Monica, CA, 1959.
↑ U. Derigs and U. Zimmermann. An augmenting path method for solving linear bottleneck assignment problems. Computing, 19:285–295, 1978.
↑ Michael Z. Spivey, "Asymptotic Moments of the Bottleneck Assignment Problem," Mathematics of Operations Research, 36 (2): 205-226, 2011.