組合せ最適化の基礎 — 知識ノート

離散的な決定を扱うときに共通する考え方。

定式化の型#

多くの組合せ問題は 0-1 変数で書ける。

x_{i} = {\begin{matrix} 1 & i を選ぶ \\ 0 & 選ばない \end{matrix}

「ちょうど 1 つ選ぶ」は $\sum_{i} x_{i} = 1$ 、「両立しない」は $x_{i} + x_{j} \leq 1$ のように制約で表現する。この形にすれば整数計画のソルバに載せられる。

クラス	意味	例
P	多項式時間で解ける	最短経路、最小全域木、割当問題
NP 困難	多項式時間の解法が知られていない	TSP、Max-Cut

似た見た目でも難易度がまったく違うのがこの分野の特徴。割当問題は多項式時間で解けるのに、TSP は NP 困難。問題を定式化したら、まず既知のどの問題に帰着するかを確かめるのが定石。

整数条件を外して連続問題として解くのが緩和。得られる値は最適値の下界（最小化の場合）になるので、

半正定値計画への緩和（SDP 緩和）は、Max-Cut に対して 0.878 倍の近似保証を与えることが知られている。

Christos H. Papadimitriou, Kenneth Steiglitz. Combinatorial Optimization: Algorithms and Complexity. Prentice Hall, 1982 / Dover, 1998. https://store.doverpublications.com/products/9780486402581
Michel X. Goemans, David P. Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the ACM 42(6), 1995. https://doi.org/10.1145/227683.227684