割り当て問題

割り当て問題は、基本的な組み合わせ最適化問題です。最も一般的な形では、この問題は次のようになります。

問題インスタンスには、複数のエージェントと複数のタスクが含まれます。任意のエージェントを任意のタスクに割り当てることができますが、そのコストはエージェントとタスクの割り当てに応じて変動します。各タスクに最大1つのエージェントを割り当て、各エージェントに最大1つのタスクを割り当てることで、割り当ての総コストを最小化しながら、可能な限り多くのタスクを実行する必要があります。

あるいは、グラフ理論を使って問題を説明すると次のようになります。

割り当て問題は、重み付き二部グラフで、エッジの重みの合計が最小となる最大サイズのマッチングを見つけることです。

エージェント数とタスク数が等しい場合、この問題はバランス割り当て問題と呼ばれ、グラフ理論的には最小コスト完全マッチング問題と呼ばれます。そうでない場合は、不バランス割り当て問題と呼ばれます。^[1]

すべてのタスクの割り当てにかかる総コストが、各エージェントのコストの合計（または各タスクのコストの合計。この場合は同じ意味）に等しい場合、この問題は線形割り当てと呼ばれます。一般的に、追加の修飾語なしに割り当て問題を指す場合は、線形均衡割り当て問題を指します。

例

あるタクシー会社が3台のタクシー（エージェント）と、できるだけ早く迎えに来てほしい3人の顧客（タスク）を保有しているとします。会社は迅速な迎えを誇りとしているため、各タクシーについて、特定の顧客を乗せるための「コスト」は、タクシーが乗車地点に到着するまでの時間に依存します。これは均衡割り当て問題です。この問題の解は、タクシーと顧客の組み合わせが総コストを最小にすることです。

さて、利用可能なタクシーが4台あると仮定しましょう。しかし、乗客は依然として3人しかいません。これは不均衡な割り当て問題です。この問題を解決する一つの方法は、例えば「何もせずにじっと座っている」という4つ目のダミータスクを作成し、そのタスクに割り当てられたタクシーのコストを0とすることです。これにより、問題は均衡な割り当て問題へと縮減され、通常の方法で解くことができ、依然として最適な解が得られます。

同様の調整は、エージェントよりも多くのタスク、複数のエージェントを割り当てる必要があるタスク (たとえば、1 台のタクシーに収まるよりも多くの顧客グループ)、またはコストを最小化するのではなく利益を最大化するために実行できます。

正式な定義

割り当て問題（または線形割り当て問題）の正式な定義は

2つの集合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の階乗）通り存在するため、この方法は非常に非効率的です。

もう一つの単純な解法は、まず最小コストのペアを貪欲に割り当て、頂点を削除し、残った頂点の中から最小コストのペアを割り当てる、というものです。このアルゴリズムは最適解にならない可能性があります。例えば、2つのタスクと2つのエージェントがあり、それぞれのコストが以下の通りだとします。

アリス: タスク 1 = 1、タスク 2 = 2。
ジョージ: タスク 1 = 5、タスク 2 = 8。

貪欲アルゴリズムでは、タスク 1 が Alice に、タスク 2 が George に割り当てられ、合計コストは 9 になりますが、逆の割り当てでは合計コストは 7 になります。

幸いなことに、 nの多項式時間で最適な割り当てを見つけるアルゴリズムは数多く存在します。割り当て問題は輸送問題の特殊ケースであり、輸送問題は最小費用フロー問題の特殊ケースであり、最小費用フロー問題は線形計画問題の特殊ケースです。これらの問題はいずれも単体法を用いて解くことができ、最悪の場合でも楕円体法を用いて多項式時間で解くことができますが、それぞれの特殊化は解空間が狭く、そのため、その特殊な構造を利用するように設計されたより効率的なアルゴリズムが存在します。

バランスの取れた割り当て

均衡割り当て問題では、二部グラフの両方の部分に同じ数の頂点があり、nで表されます。

均衡割り当てのための最初の多項式時間アルゴリズムの 1 つは、ハンガリアンアルゴリズムでした。これはグローバルアルゴリズムであり、増加パス (一致しない頂点間の交互パス) に沿った一致の改善に基づいています。フィボナッチヒープを使用した場合の実行時の複雑度はです^[2] 。ここで、mはエッジの数です。これは現在、この問題に対する強多項式アルゴリズムの最速実行時間です。ハンガリアンアルゴリズムのいくつかの変種は、GPU アクセラレーションなどの並列コンピューティングの恩恵も受けています。^[3]すべての重みが整数の場合、実行時間はまで改善できますが、結果として得られるアルゴリズムは弱多項式のみです。^[4]重みが整数で、すべての重みが最大でC ( C >1 は任意の整数) の場合、問題は重みスケーリングと呼ばれる方法で弱多項式時間で解くことができます。^[5]^[6]^[7] $O(mn+n^{2}\log n)$ $O(mn+n^{2}\log \log n)$ $O(m{\sqrt {n}}\log(n\cdot C))$

グローバル手法に加えて、局所的な更新（完全な増加経路ではなく）の探索に基づくローカル手法があります。これらの手法は漸近的な実行時間保証が劣りますが、実際にはより優れた動作をします。これらのアルゴリズムは、オークションアルゴリズム、プッシュ・リラベルアルゴリズム、またはプリフロー・プッシュアルゴリズムと呼ばれます。これらのアルゴリズムの中には、同等であることが示されています。^[8]

いくつかの局所的手法は、グラフが完全なマッチングを許容することを前提としています。そうでない場合、これらの手法のいくつかは永久に実行されてしまう可能性があります。^[1]^{: 3} この問題を解決する簡単な技術的方法は、入力グラフを完全な二部グラフに拡張し、非常に大きな重みを持つ人工的なエッジを追加することです。これらの重みは、可能な解に人工的なエッジが現れないように、既存のすべてのマッチングの重みよりも大きくする必要があります。

Mulmuley、Vazirani、Vazirani ^[9]が示したように、最小重み完全マッチング問題は、グラフの隣接行列におけるマイナーを見つける問題に変換されます。分離補題を用いると、グラフ内の最小重み完全マッチングは少なくとも1 ⁄ 2の確率で見つけることができます。n頂点のグラフの場合、この処理には時間がかかります。 $O(\log ^{2}(n))$

不均衡な割り当て

不均衡割り当て問題では、二部グラフの大きい部分にはn 個の頂点があり、小さい部分にはr < n個の頂点があります。また、グラフ内の最大マッチングの濃度以下となる定数sがあります。目標は、サイズがちょうどsである最小コストのマッチングを見つけることです。最も一般的なケースは、グラフが片側完全マッチング（つまり、サイズrのマッチング）を許容し、s = rとなる場合です。

不均衡な割り当ては均衡な割り当てに縮約できます。単純な縮約は、小さな部分に新しい頂点を追加し、コスト0の辺を使ってそれらを大きな部分に接続することです。しかし、これには新しい辺が必要です。より効率的な縮約は、倍加法と呼ばれます。ここでは、元のグラフGの2つのコピー、すなわち順方向コピーGfと逆方向コピーGbから新しいグラフG'を構築します。逆方向コピーは「反転」されるため、G'の各辺にはn + r個の頂点が存在することになります。コピー間には、2種類の連結辺を追加する必要があります。^[1]^{: 4–6} $nr$ $n(nr)$

大対大: Gfの大きい部分の各頂点から、 Gbの対応する頂点にゼロコストのエッジを追加します。
小対小: 元のグラフに片側完全マッチングがない場合、Gfの小さい方の部分の各頂点から、 Gbの対応する頂点に非常に高コストのエッジを追加します。

全体として、最大で個の新しい辺が必要になります。結果として得られるグラフには常にサイズの完全マッチングが存在します。このグラフにおける最小コストの完全マッチングは、GfとGb における最小コストで最大カーディナリティのマッチングから構成されなければなりません。 この倍加法の主な問題は、の場合に速度向上が見られないことです。 $n+r$ $n+r$ $r\ll n$

不均衡割り当て問題は、縮約法を用いる代わりに、均衡割り当てのための既存のアルゴリズムを直接一般化することで解決できる。ハンガリアンアルゴリズムを一般化することで、強多項式時間で問題を解くことができる。特に、s = rの場合、実行時間はである。重みが整数の場合、Thorup法を用いることで実行時間をとすることができる。^[1]^{: 6} $O(ms+s^{2}\log r)$ $O(mr+r^{2}\log r)$ $O(ms+s^{2}\log \log r)$

線形計画法による解

割り当て問題は線形計画問題として表すことで解くことができます。便宜上、最大化問題を提示します。各辺 $(i, j)$ （iは A に、jは T にそれぞれ属する）には重みが与えられます。各辺⁠ ⁠には変数が与えられます_。この変数は、辺がマッチングに含まれる場合は 1、含まれない場合は 0 です。そこで、ドメイン制約を設定します。 ${\textstyle w_{ij}}$ $(i,j)$ ${\textstyle x_{ij}}$ $0\leq x_{ij}\leq 1{\text{ }}i,j\in A,T,\,$ $x_{ij}\in \mathbb {Z} {\text{ }}i,j\in A,T.$

マッチングの合計重みはです。目標は、重みが最大となる完全なマッチングを見つけることです。 $\sum _{(i,j)\in A\times T}w_{ij}x_{ij}$

変数が完全なマッチングを表すことを保証するために、各頂点がマッチング内の 1 つのエッジに隣接しているという制約を追加します。 $\sum _{j\in T}x_{ij}=1{\text{ }}i\in A,\,~~~\sum _{i\in A}x_{ij}=1{\text{ }}j\in T,\,$

全体として、次の LP が得られます。

${\text{最大化}}~~\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{ }}i,j\in A,T,\,$ $x_{ij}\in \mathbb {Z} {\text{ }}i,j\in A,T.$ これは整数線形計画問題です。しかし、連続線形計画問題を解くための標準的な手法を用いれば、整数制約（つまり最後の制約を削除）なしで解くことができます。この定式化では変数が分数値を取ることも許容しますが、この特殊なケースでは、分数線形計画問題は常に変数が整数値を取る最適解を持ちます。これは、分数線形計画問題の制約行列が完全ユニモジュラ行列であるため、ホフマンとゲールの4つの条件を満たすためです。

その他の方法と近似アルゴリズム

割り当て問題に対する他のアプローチも存在し、DuanとPettie ^[10]によってレビューされています（表II参照）。彼らの研究では、割り当て問題（およびより一般的な最大重みマッチング問題）に対する近似アルゴリズムが提案されており、これは任意の固定誤差境界に対して線形時間で実行されます。

多対多の割り当て

基本的な割り当て問題では、各エージェントには最大 1 つのタスクが割り当てられ、各タスクには最大 1 人のエージェントが割り当てられます。多対多の割り当て問題では、^[11]各エージェントiは最大c _i個のタスクを実行でき（c _iはエージェントの容量と呼ばれる）、各タスクjは最大d _j個のエージェントによって同時に実行できます（d _jはタスクの容量と呼ばれる）。両側の容量の合計が等しい場合（）、問題は均衡しており、目標は完全なマッチング（各エージェントiにちょうどc _i個のタスクを割り当て、各タスクjにちょうどd _j個のエージェントを割り当てる）を見つけて、総コストが可能な限り小さくなるようにすることです。 $\sum _{i}c_{i}=\sum _{j}d_{j}$

この問題は最小コストネットワークフロー問題に還元することで解決できる。^[12]次の層を持つフローネットワークを構築する。

レイヤー 1: 1 つのソースノード。
レイヤー2：各エージェントのノード。sから各エージェントiへのアークが存在し、コストは0、容量はc _iです。
レベル3：各タスクに対応するノード。各エージェントiから各タスクjへのアークが存在し、対応するコストと容量1を持ちます。
レベル4: シンクノードtが1つ。各タスクからtへのアークが存在し、コストは0、容量はd _jです。

最小コストの積分最大フローは多項式時間で見つけることができます。ネットワークフロー問題を参照してください。このネットワークにおけるすべての積分最大フローは、各エージェントiに最大でc _i個のタスクが割り当てられ、各タスクjに最大でd _{j 個の}エージェントが割り当てられるマッチングに対応します（バランスの取れたケースでは、iにちょうどc _i個のタスクが割り当てられ、 jにちょうどd _{j 個の}エージェントが割り当てられます）。最小コスト最大フローは、最小コストの割り当てに対応します。

一般化

グラフ理論の問題として表現すると、割り当て問題は二部グラフから任意のグラフに拡張できます。これに対応する問題、すなわち重み付きグラフにおいて重みの合計が最大となるマッチングを求める問題は、最大重みマッチング問題と呼ばれます。

割り当て問題のもう一つの一般化は、マッチング対象となる集合の数を2つから複数に拡張することです。これにより、エージェントとタスクのマッチングという問題ではなく、エージェントとタスク、時間間隔、場所のマッチングという問題へと拡張されます。これは多次元割り当て問題（MAP）につながります。

参照

参考文献と参考文献

^ abcd Lyle Ramshaw, Robert E. Tarjan (2012). 「不均衡二部グラフにおける最小コスト割り当てについて」(PDF) . HP Research labs .
^ Fredman, Michael L.; Tarjan, Robert Endre (1987-07-01). 「フィボナッチヒープと改良ネットワーク最適化アルゴリズムにおけるその利用」. J. ACM . 34 (3): 596– 615. doi : 10.1145/28869.28874 . ISSN 0004-5411. S2CID 7904683.
^ Kawtikwar, Samiran; Nagi, Rakesh (2024-05-01). 「HyLAC: CUDAにおけるハイブリッド線形代入ソルバー」. Journal of Parallel and Distributed Computing . 187 104838. doi : 10.1016/j.jpdc.2024.104838 . ISSN 0743-7315.
^ Thorup, Mikkel (2004-11-01). 「定数時間で減少キーを持つ整数優先度キューと単一ソース最短経路問題」Journal of Computer and System Sciences . STOC 2003特集号. 69 (3): 330– 353. doi : 10.1016/j.jcss.2004.04.003 . ISSN 0022-0000.
^ Gabow, H.; Tarjan, R. (1989-10-01). 「ネットワーク問題のための高速スケーリングアルゴリズム」. SIAM Journal on Computing . 18 (5): 1013– 1036. doi :10.1137/0218069. ISSN 0097-5397.
^ Goldberg, A.; Kennedy, R. (1997-11-01). 「グローバル価格更新の助け」. SIAM Journal on Discrete Mathematics . 10 (4): 551– 572. doi :10.1137/S0895480194281185. ISSN 0895-4801.
^ Orlin, James B.; Ahuja, Ravindra K. (1992-02-01). 「割り当て問題と最小平均サイクル問題のための新しいスケーリングアルゴリズム」.数理計画. 54 ( 1–3 ): 41–56 . doi :10.1007/BF01586040. ISSN 0025-5610. S2CID 18213947.
^ Alfaro, Carlos A.; Perez, Sergio L.; Valencia, Carlos E.; Vargas, Marcos C. (2022-06-01). 「割り当て問題の再考」. Optimization Letters . 16 (5): 1531– 1548. doi :10.1007/s11590-021-01791-4. ISSN 1862-4480. S2CID 238644205.
^ キータン、マルムリー; Vazirani, ウメッシュ;ヴァジラニ、ビジェイ(1987)。「マッチングは行列の反転と同じくらい簡単です。」コンビナトリカ。7 (1): 105–113。土井:10.1007/BF02579206。S2CID 47370049。
^ Duan, Ran; Pettie, Seth (2014-01-01). 「最大重みマッチングのための線形時間近似」 . Journal of the ACM . 61 : 1– 23. doi :10.1145/2529989. S2CID 207208641.
^ Zhu, Haibin; Liu, Dongning; Zhang, Siqin; Zhu, Yu; Teng, Luyao; Teng, Shaohua (2016-03-07). 「バックトラッキングを用いたKuhn–Munkresアルゴリズムの改良による多対多割り当て問題の解決」 .理論計算機科学. 618 : 30– 41. doi :10.1016/j.tcs.2016.01.002. ISSN 0304-3975.
^ DW「高多重度最大重みマッチング」。Computer Science Stack Exchange 。2025年1月15日閲覧。

Brualdi, Richard A. (2006).組み合わせ行列クラス. 数学とその応用百科事典. 第108巻. ケンブリッジ:ケンブリッジ大学出版局. ISBN 978-0-521-86565-4. Zbl 1106.05001。
Burkard, Rainer ; M. Dell'Amico; S. Martello (2012). Assignment Problems (Revised reprint) . SIAM. ISBN 978-1-61197-222-1。
Bertsekas, Dimitri (1998).ネットワーク最適化：連続モデルと離散モデル. Athena Scientific. ISBN 978-1-886529-02-1。