組合せ最適化

有限個の候補から最良のものを選ぶ問題。 順序、割り当て、選択といった離散的な決定を扱う。

難しさの正体#

候補は有限なので、原理的には全部試せば解ける。 問題は候補数が組合せ的に爆発すること。 $n$ 都市の巡回路は $(n-1)!/2$ 通りあり、 $n=20$ で $6\times {10}^{16}$ を超える。

多くが NP 困難で、多項式時間の厳密解法は知られていない。 そこで現実には次のどれかを選ぶ。

方針	内容
厳密解法	分枝限定法。規模が小さければ最適解が得られる
近似アルゴリズム	最適解の $k$ 倍以内を保証する
ヒューリスティック	保証はないが実用的に良い解。焼きなまし、進化計算

代表的な問題#

• 数分割問題
• 巡回セールスマン問題
• 割当問題
• ナップサック問題
• Max-Cut

これらの多くは QUBO として書き直せ、 量子アニーリングや QAOA の適用対象になる。

参考文献#

• Christos H. Papadimitriou, Kenneth Steiglitz. Combinatorial Optimization: Algorithms and Complexity. Prentice Hall, 1982 / Dover, 1998. https://store.doverpublications.com/products/9780486402581
• Bernhard Korte, Jens Vygen. Combinatorial Optimization: Theory and Algorithms, 6th ed. Springer, 2018. https://doi.org/10.1007/978-3-662-56039-6