ナップサックの問題一覧

ナップサック問題は、組み合わせ最適化において最も研究されている問題の一つであり、多くの実生活での応用がある。このため、多くの特殊なケースや一般化が検討されてきた。^{[1] [2]}

すべてのバージョンに共通するのはn 個のアイテムのセットであり、各アイテムには関連する利益p _jと重みw _jがあります。バイナリ決定変数x _jはアイテムの選択に使用されます。目的は、選択したアイテムの最大合計重みがW を超えないようにしながら、合計利益が最大となるアイテムをいくつか選択することです。通常、これらの係数は整数になるようにスケーリングされ、ほとんどの場合正であると想定されます。 ${\displaystyle 1\leq j\leq n}$

最も基本的な形の ナップサック問題:

よくあるバリエーションの 1 つは、各アイテムを複数回選択できることです。制限付きナップサック問題では、各アイテムjについて、アイテムjを選択できる回数の上限u _j (正の整数または無限大) を指定します。

無制限ナップサック問題（整数ナップサック問題と呼ばれることもある）では、項目が選択される回数に上限は設定されません。

1975年にLuekerによって、無限の変種はNP完全であることが示されました。^[3]有限と無限の変種は両方ともFPTAS（0-1ナップサック問題で使用されるものと本質的に同じ）を許容します。

アイテムが と表記されるk個のクラスに分割され、各クラスから正確に 1 つのアイテムを選択する必要がある場合、複数選択ナップサック問題が発生します。 ${\displaystyle N_{i}}$

各項目の利益と重量が等しい場合、サブセットの合計問題が発生します(多くの場合、代わりに対応する決定問題が与えられます)。

n 個のアイテムと容量がm 個のナップサックがある場合、多重ナップサック問題が発生します。 ${\displaystyle W_{i}}$

複数ナップサック問題の特殊なケースとして、利益が重みに等しく、すべてのビンの容量が同じである場合、複数のサブセットの合計問題が発生する可能性があります。

二次ナップサック問題:

集合和ナップサック問題:

SUKPはケラーら^[2]（423ページ）によって次のように定義されています。

アイテムのセットといわゆる要素のセットが与えられた場合、各アイテムは要素セットのサブセットに対応します。アイテムは非負の利益、を持ち、要素は非負の重み、を持ちます。アイテムセットの合計重量は、対応する要素セットの和集合の要素の合計重量によって決まります。目的は、合計重量がナップザックの容量を超えず、利益が最大となるアイテムのサブセットを見つけることです。 ${\displaystyle n}$${\displaystyle N=\{1,\ldots ,n\}}$${\displaystyle m}$${\displaystyle P=\{1,\ldots ,m\}}$${\displaystyle j}$${\displaystyle P_{j}}$${\displaystyle P}$${\displaystyle j}$${\displaystyle p_{j}}$${\displaystyle j=1,\ldots ,n}$${\displaystyle i}$${\displaystyle w_{i}}$${\displaystyle i=1,\ldots ,m}$

制約が複数ある場合 (たとえば、各アイテムの体積と重量が関連していない場合の体積制限と重量制限の両方)、多重制約ナップサック問題、多次元ナップサック問題、またはm次元ナップサック問題が発生します(ここでの「次元」はアイテムの形状を指すものではないことに注意してください)。これには、0-1、制限付き、および制限なしのバリエーションがあり、制限なしのバリエーションを以下に示します。

0-1変種（任意の固定に対して）は1980年頃にNP完全であることが示され、さらに強く、P=NPでない限りFPTASは存在しないことが示された。 ^{[4] [5]}${\displaystyle m\geq 2}$

有界および非有界変種（任意の固定に対して）も同じ困難性を示す。^[6]${\displaystyle m\geq 2}$

任意の固定された に対して、これらの問題は擬似多項式時間アルゴリズム（基本的なナップサックの問題に類似）とPTAS を許容する。^[2]${\displaystyle m\geq 2}$

すべての利益が 1 の場合、ナップザックの容量を超えないアイテムの数を最大化しようとします。

複数のコンテナ（同じサイズ）があり、n 個のアイテムすべてをできるだけ少ないコンテナに詰め込みたい場合、ビンパッキング問題が発生します。これは、コンテナiが使用されているというインジケータ変数によってモデル化されます。 ${\displaystyle y_{i}=1\Leftrightarrow }$

カッティングストック問題はビンパッキング問題と同一ですが、実際の例ではアイテムの種類がはるかに少ないため、別の定式化がよく使用されます。アイテムjはB _j回必要であり、1 つのナップザックに収まるアイテムの各「パターン」には変数x _i (パターンはm個) があり、パターンi はアイテムj を b _ij回使用します。

多肢選択ナップサック問題に、各サブセットのサイズがnであるという制約を追加し、合計重量の制限を削除すると、割り当て問題が得られます。これは、最大二部マッチングを見つける問題でもあります。

最大密度ナップサック法では、初期重みがあり、容量制約に違反しない選択されたアイテムの密度を最大化します。 ^[7]${\displaystyle w_{0}}$

上記の問題ほど一般的ではありませんが、ナップサックのような問題は他にもいくつかあります。

• 入れ子になったナップサック問題
• ナップザックの折りたたみ問題
• 非線形ナップサック問題
• 逆パラメトリックナップサック問題

最後の3つについては、ケラーらの参考文献「ナップサック問題」で議論されています。^[2]

• 「ナップサック問題のためのアルゴリズム」、D. Pisinger。博士論文、DIKU、コペンハーゲン大学、レポート 95/1 (1995)。