👜

難しいナップサック問題はどこにある？

2021/03/27に公開・約10,500字

ナップサック問題

np困難

分枝限定法

tech

NP 困難な最適化問題の定番、みんな大好きナップサック問題の話です。話が発散しないよう、今回取り扱うのは 0-1 ナップサック問題に限ることとします。

TL; DR

理論的には NP 困難だけど、実用上ほとんどは簡単な問題
ちゃんと書いた分枝限定法ソルバーであれば、ランダムに作った問題だと n=1000 万でも 120 ミリ秒くらいで解けちゃう
- こうなると入出力の時間の方がボトルネック
profit-weight の分布を特徴的にしたとき、難しい問題が出てくることがある
- 特に貪欲法対策をやられるとつらい。対策し返してないと n=100 くらいまでしか解けなくなる
難しい問題のジェネレータもあるし、生成方法も簡単なんでちゃんと考えよう

はじめに

先日こんなツイートが RT で回ってきました。

これを見てこんな風に思いました。
「そうなんだよなー、みんな難しい問題の生成方法とか知らなくてランダムに作った問題インスタンスで試してる程度なんだよなー。Pisinger のページとか知らないんだよなー」
「そういや昔分枝限定法のソルバー書いたけど、ソースどっか行っちゃったしまた作るかー」

というわけで、その辺をちょっと解説する Zenn 記事です。

0-1ナップサック問題

0-1 ナップサック問題はざっくり以下で定義されます（ちゃんと数式でも書けます）。

$N$ 個のアイテム
- それぞれ価値(profit, $p_j$ )、重さ(weight, $w_j$ )が与えられる
容量(capacity, $c$ )

重さの合計が容量を超えない範囲で、価値の合計が最も高くなる組み合わせを求めたい、というのが 0-1 ナップサック問題です。世の中的には DP の説明で出てくることが多いですが、私の研究室時代は分枝限定法が中心の生活だったので分枝限定法で解くのが好きです。

0-1ナップサック問題に関する既存の研究、資料

David Pisinger's optimization codes

ナップサック問題で D 論書いたりその後も色々研究を続けている方です。ソルバーのコードもありますし、「難しい問題を生成する」ジェネレータもあります。

Knapsack ProbleMicrosoft

なんかナップサック問題の本の PDF が置いてあります。著者の所属機関の Web サイトですけど、いいのかな？　Chapter2 に 0-1 ナップサック問題の分枝限定法での解法について色々書いてあります。

作ったソルバー

勢いでえいやと作ったソルバーがこちら。ちょっと可視化ツールとかも入れてみました。今のところ Pisinger のソルバーの方が速いっぽいです。Pisinger のソルバーもそうですけど、オーバーフローとか考えていないです。というかバグが残っていてたまに最適解見つけられない。

0-1ナップサック問題の分枝限定法による解法の説明

ここからは 0-1 ナップサック問題の解法について説明していきます。毎回 0-1～と書くのも面倒なのでこれ以降で単にナップサック問題と書いたときは 0-1 ナップサック問題のことを指します。

事前準備

ナップサック問題の解法を考えるとき、良く出てくるのが価値を重さで割った値です。費用対効果(ratio, $r_j$ )とでも呼びましょうか。この後色々やるときに議論がしやすくなるので、ここから後はこの費用対効果の大きい順にソートしてあるものとします。解を得た後に「どのアイテムを入れたか」をたどるときにはソートしたときの対応付けを使えば問題なく元に戻せます。

上界値

ナップサック問題の解の上界値として、一番簡単なものは連続緩和した問題の解です。連続緩和というのは文章での説明だと、「入れる、入れない」の 0-1 だった制約条件を「半分入れる」とか「1/3 入れる」とかの小数値を許可するということです。離散から連続に緩和されているから連続緩和と言います。

連続緩和したナップサック問題は簡単に最適解が求められます。先に定義した費用対効果が大きいものから順に詰めていき、入りきらなくなるアイテムを入る大きさに「切って」入れれば、それよりも価値の合計が大きくなる解は他にありません。細かい話ですが、容量・価値が整数値として与えられることが保証されている場合はこの値を超えない最大の整数（いわゆる floor 関数）を上界値とできます。

切ることになるアイテムは高々1 つです。この「切った」アイテムのインデックスをクリティカルインデックスと呼び、 $s$ で表すことにします（色々考えるときに「切らなかった場合どうするか」が必要なのですが、説明が煩雑になるので省略します）。

先に紹介した本ではもうちょっと色々工夫したり、連続緩和でなくラグランジュ緩和を利用した上界値を使う方法も解説されています。

下界値

下界値は何らかの実行可能な解（容量制約、0-1 制約を満たしている）を持ってくればその価値の合計が下界値になります。

自明な実行可能解

「アイテムを 1 個も入れない」解はナップサック問題の自明な解（最適解とは限らない）の最も簡単なものです。とはいえ、さすがにこれはあんまり使いどころがないのでもうちょっとマシな解を考えましょう。

ヒューリスティック解法（貪欲法）

簡単なヒューリスティック解法として貪欲法があります。これも費用対効果をベースにしています。ざっくり言うと費用対効果の大きい順に「容量に納まるなら入れる。納まらないなら入れない」という操作を全部のアイテムに対して行うだけです。費用対効果の大きいアイテムが多く入るはずなので、それなりに良い解が期待できるというわけです。

変数のピン止め

上界値と下界値が求まると、ちょっと分析すると「より価値の合計の大きい解があるとしたら、このアイテムは入っていなければならない」「入れてはいけない」といえる場合があります。細かいところは上記の本を参照して欲しいですが、ざっくり言うと次のようになります。「このアイテムを入れないと上界値が今の下界値よりも下がる」ならば「より価値の合計の大きい解があるとしたら、このアイテムは入っていなければならない」ということになります。

こうやって一部のアイテムについて「入れる」「入れない」を固定することを変数のピン止めと呼ぶことにします（本ではReductionと呼んでます）。後は「入れる」とも「入れない」とも決まらなかった残りのアイテムについて考えれば、元の問題を解いたことになります。

分枝限定法

今回実装したのは次のような特徴を持つ分枝限定法のソルバーです。

分枝操作はシンプルにクリティカルインデックスで 0 と 1 に分枝する
子問題の上界値計算は親問題の情報（主にクリティカルインデックス）を活用して効率的に行う
上界値の計算方法は上記の本の連続緩和ベースで工夫した手法までは組み込んでおく
変数のピン止めにより問題を縮小する

問題インスタンスの分析

最初に定義したのはナップサック問題ですが、実際に具体的な値が決まったもの（容量、価値・重さ全部）のことを問題インスタンスと呼びます。

実用的にナップサック問題を活用するとしたら、現実の問題インスタンス（例えばスーパーで買い物するとき、とか）を持ってくることになるでしょう。一方で何らかのソルバーを作ってその性能を確認したいなどという場合は何らかのルールで問題インスタンスを生成することが多いです。

ルールと言いましたが、そんなに難しいものではなく、以下の 2 点のことです。

アイテムの個数の決定方法
価値と重さの決定方法
容量の決定方法

価値と重さの決定方法で良くあるのが、「決められた範囲からランダムに選ぶ」というものでしょう。容量の決定方法はちょっと置いておきます。

Pisingerのジェネレータ

いよいよ Pisinger のジェネレータの出番です。まずは一番シンプルなジェネレータ（A generator とあるリンク先）からです。

コメントによると、実行方法は以下とあります。

generator n r type i S

順に $N$ 、価値・重さの範囲、生成するタイプ、インスタンス No、シリーズ数、と説明があります。

まず、生成するタイプは、以下のように説明されています。無相関、弱相関、強相関、部分和問題の 4 つ、ですね。

type: 1=uncorr., 2=weakly corr., 3=strongly corr., 4=subset sum

それぞれの性質は後で見ていきます。

インスタンス No とシリーズ数についてですが、シリーズ数の個数の問題インスタンスを生成することを前提にしていています。インスタンス No が大きくなるにしたがって、容量が大きくなっていくようになっています。容量の違いによる変化まで追いかけると大変なので、インスタンス No をシリーズ数の半分にしたインスタンスを対象にすることとします。

ランダムに選んだ場合（無相関）

価値と容量をそれぞれランダムに選ぶということは、無相関である、ということになります。Pisinger のジェネレータだと type=1 の場合です。ランダムに選ぶ範囲を変えることでちょっと性質が変わる場合もありますが、ここでは $[0,r)$ の範囲のものに限っておきます。

アイテム 1 個 1 個に価値と容量の 2 つの値があるので、散布図（＋価値・重さのヒストグラム）で見てみましょう。

はい、相関の無い分布をしてますね。ちなみに、この散布図上で費用対効果のことを考えると、原点を中心に y 軸から x 軸まで直線を回していくと、費用対効果の大きいアイテムから小さいアイテムとぶつかっていくことになります。

この問題インスタンスを先のソルバーで解いて（ $N=300$ なので一瞬で終わります）、貪欲法の解と最適解について以下の塗り分けをしてみます。

貪欲法と最適解の両方で選ばれたアイテムは紫色
貪欲法でだけ選ばれたアイテムは青色
最適解でだけ選ばれたアイテムは赤色
どちらにも選ばれなかったアイテムは黒色

左上（費用対効果の大きいアイテム）は大体紫色、右下（費用対効果の小さいアイテム）は大体黒色になっています。赤色や青色はその境界領域にちらほら現れていますね。赤色と青色が少ないということは、貪欲法で見つかった解が最適解と比較的近かったということでもあります。

次は変数のピン止めの効果を見てみます。アイテムごとに以下の塗り分けをします。

入れる方にピン止めしたアイテムを青色（今回は 167 個）
入れない方にピン止めしたアイテムを赤色（90 個）
どちらにもピン止めされなかったアイテムを緑色（43 個）

大半のアイテムがピン止めされていて、緑色の部分はかなり限られていることが分かります。つまり、分枝限定法で探索する範囲はこの緑色の部分なので $N$ に比べてかなり少なくなっていて比較的高速に解けてしまうわけです。

ちなみに $N=10,000,000$ の場合でピン止めされなかったアイテムの数は 2800 個でした。1000 万個もアイテムがあっても、本質的なのはこの 2800 個ということです。

弱相関

次は弱相関（type=2）についてです。まずは散布図で見てみましょう。

重さと価値を近い値にすることで、弱い相関を作り出しています。

続けて解の分布とピン止め結果について見てみましょう。

ピン止めされなかったアイテムの数は 72 個と、無相関よりは多くなっているので、少し難しくなったということになります。

部分和問題

type3 を飛ばして先に type4 の説明をします。ナップサック問題の特殊形として、すべてのアイテムで価値と重さの等しい場合があります。このような問題は部分和問題と呼ばれ NP 完全であることが知られています。type4 は部分和問題を生成するようになっています。

まずは散布図です。斜め 45 度の直線上にすべてのアイテムが乗っていることになります。

解の分布とピン止め結果です。

すべてのアイテムがピン止めされていません。つまり、 $N$ 全体について解かなければならないわけです。このタイプの問題インスタンスはちょっとした工夫で多少対策が出来ます。先の説明ではアイテムの事前ソートを「費用対効果順」としていましたが、ここに「費用対効果が等しかったときは重さの大きい順」でソートするだけです。これにより貪欲法が大きいアイテムから入れていくことになり、容量の空きが少ない、比較的良い下界値を得ることができ、分枝限定法でもそれなりに効率よく分枝していくことができます。

強相関（というより貪欲法対策）

基本のジェネレータのラスボスともいえる type=3 です。ジェネレータのコメントには type3 は**3=strongly corr.**と書いてあるのですが、単純な相関係数の大小ではなく、ちょっと変わった性質を持っています。その性質は今回私が作成したソルバーのように対策を何も入れていないソルバーの弱点を的確についてきます。

本当に解けないのでこのタイプは $N=100$ にします。まずは散布図です。

ほぼ一直線のように見えますが、正確なところを説明するために、ソースコードの生成方法の部分を見てみましょう。

case 3: i->p = i->w + 10;

つまり、「価値は重さ+10」となっています。散布図でいうと斜め 45 度の直線をちょっとだけ上へ持ち上げた直線になっていたわけです。これをやられると何がつらいかというと、「小さな（重さの小さい）アイテムほど費用対効果が高い」ということになってしまうのです。こうなると例えば貪欲法で費用対効果が大きい順に入れていったとき、段々アイテムが大きくなっていきます。そして最終的には容量の余りが大きくなってしまいがちで、良い下界値とならなくなってしまうのです。

解の分布とピン止め結果についても見てみましょう。

ピン止めが全然出来ていません。今回の場合は 1 個もピン止めされていません。

つまり、全部のアイテムについて解かなければならない上、貪欲法も裏目に出て、分枝限定法もイマイチ効率の悪い探索となって…つまり、解くのが非常に難しい問題インスタンスになっています。

アドバンスドジェネレータ

"A more advanced generator" とあるリンク先には更に生成方法のバリエーションが増えたジェネレータのソースコードがあります。

  type: 1=uncorrelated, 2=weakly corr, 3=strongly corr, 
        4=inverse str.corr, 5=almost str.corr, 6=subset-sum, 
        7=even-odd subset-sum, 8=even-odd knapsack, 
        9=uncorrelated, similar weights,
        11=Avis subset-sum, 12=Avis knapsack, 13=collapsing KP,
        14=bounded strongly corr, 15=No small weights

たくさん増えてますね。また、"A generator for hard instances"というリンク先にもまた別のジェネレータがあります。

  type: 1=uncorrelated, 2=weakly corr, 3=strongly corr,
        4=inverse str.corr, 5=almost str.corr, 6=subset-sum,
        7=even-odd subset-sum, 8=even-odd knapsack,
        9=uncorrelated, similar weights,
      11=uncorr. span(2,10)
      12=weak. corr. span(2,10)
      13=str. corr. span(2,10)
      14=mstr(3R/10,2R/10,6)
      15=pceil(3)
      16=circle(2/3)

説明文だけだと分からないので散布図にプロットしてみましょう。

タイプ 1。無相関です。前のと同じですね。

タイプ 2。弱相関も同じです。

タイプ 3。強相関（貪欲法対策）はずらす量が少し大きくなっています。

タイプ 4。新しいタイプです。逆強相関…ってなんじゃそりゃってなりますけど、前のは斜め 45 度直線を上にずらしてましたけど、こちらは下にずらしたものです。

タイプ 5。大体強相関…ソースコード読むと、タイプ 3 がぴったり直線上に並んでいたのに対して少しばらつきを持たせているようです。

タイプ 6。のジェネレータにもあった部分和です。

タイプ 7。分枝限定法にとって微妙に嫌らしいタイプの部分和問題です。散布図だと分からないですが、すべてのアイテムが偶数の重さ（＝価値）を持っています。それでいて容量は奇数になっています。つまり、ぴったり詰め込んで最適性が保証されるパターンは発生せず、探索をすべて終わらせるまで解けないわけです。本当に嫌らしい。