概要
ナップザック問題を分岐限定法で爆速（$n<2000, v_i<10^{12}, w_i<10^{12}$を$1$秒）で解きます。実行時間ベースで今のところ3位です。提出はこちら
これは競技プログラミング 解説 Advent Calendar 2017の16日目の記事です。
ナップザック問題
ナップザック問題とは、重さ制約$W$と$n$個の荷物価値ペア($v_i, w_i$)が与えられて、$\displaystyle \max_{S \in 2^n, \sum_S w_i \le W} \sum_S v_i$を求める問題です。Atcoder ABC 32 - D - ナップザック問題は、様々な$n$, $v_i$, $w_i$の制約のもとで、この問題を解くという趣旨でした。
この問題は、以下の3つのDP解を、テストケースごとに作成することで通すことができます（提出）。
(1) $n$が少ない場合、半分全列挙によって$O(n 2^{n/2})$
(2) $v_i$が少ない場合、「$D_{i, j}$ = $i$個見て、今まで取ったものの価値総和を$j$にするために必要な最小重さ」としてDP
(3) $w_i$が少ない場合、「$D_{i, j}$ = $i$個見て、今まで取ったものの重さ総和を$j$であるもとでの最大価値」としてDP
一方、この問題は極めて歴史が長く研究されており、Expanding Coreなどの高速解法が知られています。もちろん、このような手法を淡々と解説する記事にしてもよいのですが、ナップザック問題に特化したものとなり一般性に欠けます。本記事では、より一般的に限定分岐法を解説し、それをナップザック問題に当てはめるという流れで解説したいと思います。
限定分岐法
限定分岐法とは、枝刈り全探索の一種です。普段から探索木の枝刈りをしている人は分かると思いますが、枝刈りは問題特有の性質を抽出する必要があります。一方、限定分岐法では最大最小問題に限り、「機械的に」枝刈りをすることができます！
いくつか用語を定義します。記号はかなりゆるふわです。
- $f(x) = f(S, T)$ : 最小化したい関数。確定した自由度$S$と確定していない自由度$T$があるとき、$\displaystyle f(x) = \min_T f(S+T, \phi)$
- 許容解=下界=$f(x)$の今までに見つかった解の中で最も良い解
- 緩和解=上界=$f(x)$の緩和問題$g(x)$の最適解。$\forall x\ f(x) \le g(x)$が満たされる関数$g$を想定します。
最も重要なのは、真の問題と緩和問題の関係です。これらの間には以下の関係が成り立つことがわかります。
- 緩和解<許容解ならば、$x \in T$は解になりえない（$f(S, T)$の自由度$T$をどう取ったとしても最適解を更新しない！！$T$は調べる必要がない！！）
- 緩和問題の最適解を与える$x$が真の制約を満たすならば、それは真の最適解（$g(S, T)$を解いただけで、$f(S, T)$の中で$T$の最適解が確定することがある！）
ll 許容解 = INF;
// 自由度sが確定していて、自由度tが未確定の時の最適解
ll dfs(state s, state t) {
緩和解 = g(s, t);
if (緩和解を与えるs, tが真の制約を満たす) return 許容解 = min(許容解, 緩和解);
if (緩和解>許容解) return INF;
ll ret = INF;
for (auto x : tの自由度のうち確定させたいものの集合) {
chmin(ret, dfs(s+x, t-x));
}
許容解 = min(許容解, 緩和解);
return ret;
}
int main(void) {
許容解 = 貪欲関数(); // あってもなくても良い
dfs(φ, all);
}
緩和問題
ここで、緩和問題の作り方はたくさんあるのですが、一般的に使えるテクニックを2つ紹介します。
1. ラグランジュ緩和
真の問題が
min xy
s.t. x>0, y>0, x+y<1
だとします。「制約違反度」をmin側に突っ込んでしまって、
min xy + s(x+y-1)
s.t. x>0, y>0
とすると、緩和問題を作ることができます。
2. 線形計画緩和
離散問題を連続問題にしてしまいます。
具体的には、真の問題が
min xy
s.t. x>0, y>0, x, yは整数
だとします。整数条件を取り払って、
min xy
s.t. x>0, y>0
とすると、緩和問題を作ることができます。離散最適化では指数計算量でしたが、この緩和問題は線形計画法で$O(n^3)$の多項式計算量で解ける問題になります！また、出てきた緩和問題の特有の性質を利用することで、更に計算量を下げることができるケースもあります（実際、今から紹介するナップザック問題の線形緩和は$O(n)$で解けます）。
ナップザック問題
今、ナップザック問題を整数計画問題として立式すると、以下になります。
$\max x_i v_i$
$s.t. x_i w_i \le W, 0 \le x_i \le 1$, $x_i$は整数
これを線形緩和して、
$\max x_i v_i$
$s.t. x_i w_i \le W, 0 \le x_i \le 1$
とします。この問題は、少なくとも線形計画法で$O(n^3)$の多項式計算量で解ける問題になります。更にこの問題をよく見ると、$v_i / w_i$が大きいものからなるべく多く詰めていく貪欲が最適であることがわかります。事前に$v_i, w_i$をソートしておくことで、この問題は$O(n)$で解くことができました。
以上で、最悪計算量$O(n 2^n)$（？）の探索アルゴリズムができました。え？遅そう？実際に計測してみると、何と$n<2000, v_i<10^{12}, w_i<10^{12}$を$1$秒程度で解けます！！
細かいが計算時間に効く話
探索のなるべく早い段階で良い解を見つけたいというモチベーションがあります。なぜなら、そのほうが枝刈りが強くなるからです。つまり、毎回$T$の自由度凍結において、できれば解が見つかりそうな方向に進んだほうが良いことがわかります。例えばナップザック問題では、$v_i/w_i$が大きい順に並べた時、初めの方は効率が良いので取ったほうがいいに決まっています。
実際、初めを先に取る探索では実行時間が$3$ msであるのに対して、初めを後に取る探索では実行時間が$1500$ msを超えています。大きな違いですね。このような変数選択の問題があるので、商用マシンの整数計画法なのでは、学習による変数選択を行っていると聞きます（要出典）。