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

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

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

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

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

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

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

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

Заданы два множества, 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)$

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

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

Лемма. Пусть $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).

Присваиваем начальные значения $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)$ — временна́я сложность проверки существования совершенного паросочетания. Мы можем использовать матричный алгоритм Ибарра и Морана для выяснения, существует ли совершенное паросочетание. Тогда оптимальное решение может быть найдено с битовой сложностью $O(n^{\beta }\log ^{k}n)$. Для умножения двух n × n матриц нужно $O(n^{\beta })$ арифметических операций и k — некоторое целое число, возникающее из действий над длинными целыми числами. Копперсмит (Coppersmith) и Виноград (Winograd) показали, что умножение матриц можно сделать с $\beta =2{,}376$. Если мы хотим получить соответствующее оптимальное решение, мы можем использовать метод Альта, Блюма, Мелхорна и Паула (Alt, Blum, Mehlhorn, Paul) и получим полную сложность $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. Этот граф содержит все рёбра предыдущего графа и как минимум одно новое ребро, так что мы можем начать поиск максимального паросочетания с уже найденного на предыдущем шаге. Продолжаем, пока не найдём совершенное паросочетание.

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

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

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

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

Пусть $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), то

$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).$