割当問題

$n$ 人の作業者を $n$ 個の仕事に 1 対 1 で割り当て、総コストを最小にする問題。 Assignment Problem。

$$\min \sum _{i,j}{c}_{ij}{x}_{ij}\text{s.t.}\sum _j{x}_{ij}=1,\sum _i{x}_{ij}=1,x_{ij}\in \{\mathrm{0,1}\}$$

多項式時間で解ける#

$n!$ 通りの割当があるのに、この問題は簡単。 Kuhn のハンガリアン法が $𝒪(n^3)$ で最適解を与える。

理由は制約行列が完全単模 (totally unimodular) であること。 このとき整数条件を外したLP 緩和の 頂点が自動的に整数になるので、 整数計画でありながら LP として解ける。

見た目が似ていても難易度が違う#

問題	計算量
割当問題（線形）	$𝒪(n^3)$
二次割当問題 (QAP)	NP 困難
TSP	NP 困難

コストが $c_{ij}$ の和（線形）なら簡単、 組の相互作用 $c_{ijkl}$ が入る（二次）と一気に難しくなる。 組合せ最適化で「どの問題に帰着するか」を先に確かめるべき理由がここにある。

参考文献#

• Harold W. Kuhn. The Hungarian method for the assignment problem. Naval Research Logistics Quarterly 2(1-2), 1955. https://doi.org/10.1002/nav.3800020109
• Rainer Burkard, Mauro Dell'Amico, Silvano Martello. Assignment Problems, Revised Reprint. SIAM, 2012. https://doi.org/10.1137/1.9781611972238
• Christos H. Papadimitriou, Kenneth Steiglitz. Combinatorial Optimization: Algorithms and Complexity. Prentice Hall, 1982 / Dover, 1998. https://store.doverpublications.com/products/9780486402581