割り当て問題

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

問題インスタンスには、エージェントとタスクが複数あります。任意のエージェントを任意のタスクの実行に割り当てることができますが、エージェントとタスクの割り当てに応じて異なるコストが発生します。割り当ての合計コストが最小になるように、各タスクに最大 1 つのエージェントを割り当て、各エージェントに最大 1 つのタスクを割り当てることで、できるだけ多くのタスクを実行する必要があります。

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

割り当て問題は、重み付き 二部グラフにおいて、辺の重みの合計が最小となる、指定されたサイズのマッチングを見つけることです。

エージェントとタスクの数が等しい場合、この問題は均衡割り当てと呼ばれます。それ以外の場合は、不均衡割り当てと呼ばれます。^[1]すべてのタスクの割り当ての総コストが各エージェントのコストの合計（または各タスクのコストの合計、この場合は同じもの）に等しい場合、問題は線形割り当てと呼ばれます。通常、追加の修飾語なしで割り当て問題について話すときは、線形均衡割り当て問題を意味します。

タクシー会社に 3 台のタクシー (エージェント) があり、できるだけ早く迎えに来てほしい顧客 (タスク) が 3 人いるとします。会社は迅速な迎えを誇りにしているので、各タクシーについて、特定の顧客を迎えに行く「コスト」は、タクシーが迎え地点に到着するまでの時間によって決まります。これはバランスの取れた割り当て問題です。その解決策は、タクシーと顧客の組み合わせが総コストを最小にすることです。

ここで、利用可能なタクシーが4 台あるが、客は 3 人しかいないと仮定します。これは不均衡な割り当て問題です。この問題を解決する 1 つの方法は、4 番目のダミー タスク (たとえば「何もせずにじっと座っている」) を作成し、そのタスクに割り当てられたタクシーのコストを 0 にすることです。これにより、問題は均衡のとれた割り当て問題に縮小され、通常の方法で解決でき、問題に対する最適なソリューションが得られます。

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

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

2つの集合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 つの単純な解決法は、まず最小コストのペアを貪欲に割り当て、頂点を削除し、次に残りの頂点の中で最小コストのペアを割り当てるというものです。このアルゴリズムでは、最適ではない解決法が生成される場合があります。たとえば、次のようなコストを持つ 2 つのタスクと 2 つのエージェントがあるとします。

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

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

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

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

バランスのとれた割り当てのための最初の多項式時間アルゴリズムの 1 つは、ハンガリアン アルゴリズムでした。これはグローバルアルゴリズムであり、増加パス (一致しない頂点間の交互パス) に沿ったマッチングの改善に基づいています。フィボナッチ ヒープ を使用する場合の実行時の複雑さはです^[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))}$

グローバルメソッドに加えて、ローカル更新（完全な拡張パスではなく）を見つけることに基づくローカルメソッドがあります。これらのメソッドは漸近的な実行時間保証が劣りますが、実際にはよりうまく機能することがよくあります。これらのアルゴリズムはオークションアルゴリズム、プッシュリラベルアルゴリズム、またはプリフロープッシュアルゴリズムと呼ばれます。これらのアルゴリズムのいくつかは同等であることが示されています。^[7]

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

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

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

不均衡な割り当ては均衡な割り当てに縮小できる。単純な縮小は、小さい部分に新しい頂点を追加し、コスト 0 の辺を使用して大きい部分に接続することである。しかし、これには新しい辺が必要である。より効率的な縮小は、倍増技法と呼ばれる。ここでは、新しいグラフG'は、元のグラフGの 2 つのコピー、つまり前方コピーGfと後方コピーGbから構築される。後方コピーは「反転」され、G'の各側にn + r個の頂点が存在するようになる。コピー間には、2 種類のリンク エッジを追加する必要がある: ^{[1] : 4–6}${\displaystyle nr}$${\displaystyle n(nr)}$

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

全体として、最大で 個の新しいエッジが必要になります。 結果のグラフには、常にサイズ の完全マッチングが含まれます。 このグラフの最小コスト完全マッチングは、 GfとGbの最小コスト最大カーディナリティ マッチングで構成されている必要があります。 この倍増手法の主な問題は、 の場合に速度が向上しないことです。 ${\displaystyle n+r}$${\displaystyle n+r}$${\displaystyle r\ll n}$

不均衡割り当て問題は、縮約法を使用する代わりに、均衡割り当ての既存のアルゴリズムを直接一般化することで解決できます。ハンガリーアルゴリズムを一般化して、問題を強多項式時間で解決できます。特に、s = rの場合、実行時間は です。重みが整数の場合、Thorup 法を使用して実行時間を にすることができます。^{[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{ }}i,j\in A,T,\,}$$ $${\displaystyle x_{ij}\in \mathbb {Z} {\text{ }}i,j\in A,T.}$$

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

変数が完全なマッチングを表すことを保証するために、各頂点がマッチング内の 1 つのエッジに隣接しているという制約を追加します 。 $${\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{最大化}}~~\sum _{(i,j)\in A\times T}w_{ij}x_{ij}}$$$${\displaystyle {\text{subject to}}~~\sum _{i\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{ }}i,j\in A,T,\,}$$$${\displaystyle x_{ij}\in \mathbb {Z} {\text{ }}i,j\in A,T.}$$これは整数線形計画です。ただし、連続線形計画を解くための標準的な方法を使用して、整数制約なしで (つまり、最後の制約を削除して) 解くことができます。この定式化では分数変数値も許可されますが、この特殊なケースでは、LP には常に変数が整数値を取る最適解があります。これは、分数 LP の制約行列が完全にユニモジュラであるためです。つまり 、Hoffman と Gale の 4 つの条件を満たしています。

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

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

割り当て問題のもう 1 つの一般化は、マッチングするセットの数を 2 から多数に拡張することです。これにより、エージェントをタスクにマッチングするのではなく、エージェントをタスクに、時間間隔に、場所にマッチングするという問題に拡張されます。この結果、多次元割り当て問題 (MAP)が生まれます。

• オークションアルゴリズム
• 一般化割り当て問題
• 線形ボトルネック割り当て問題
• モンジュ・カントロヴィッチ輸送問題、より一般的な定式化
• 全国レジデントマッチングプログラム
• 二次方程式の割り当て問題
• ランク最大マッチング
• 秘書問題
• 安定した結婚生活の問題
• 安定したルームメイト問題
• 兵器のターゲット割り当て問題
• 住宅割り当て問題
• 多次元割り当て問題 (MAP)

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