ナップサックの問題一覧

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

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

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

最大化する ∑ j ＝ 1 n p j × j {\displaystyle \sum _{j=1}^{n}p_{j}x_{j}}
対象となる ∑ j ＝ 1 n わ j × j ≤ W 、 {\displaystyle \sum _{j=1}^{n}w_{j}x_{j}\leq W,}
× j ∈ { 0 、 1 } {\displaystyle x_{j}\in \{0,1\}} た j ∈ { 1 、 … 、 n } {\displaystyle \forall j\in \{1,\ldots ,n\}}

直接的な一般化

よくあるバリエーションの一つは、各アイテムが複数回選択できるというものです。有界ナップサック問題では、各アイテムjについて、アイテムjが選択できる 回数の上限u j （正の整数または無限大）を指定します。

最大化する ∑ j ＝ 1 n p j × j {\displaystyle \sum _{j=1}^{n}p_{j}x_{j}}
対象となる ∑ j ＝ 1 n わ j × j ≤ W 、 {\displaystyle \sum _{j=1}^{n}w_{j}x_{j}\leq W,}
0 ≤ × j ≤ あなた j 、 × j {\displaystyle 0\leq x_{j}\leq u_{j},x_{j}} すべてのjについて積分

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

最大化する ∑ j ＝ 1 n p j × j {\displaystyle \sum _{j=1}^{n}p_{j}x_{j}}
対象となる ∑ j ＝ 1 n わ j × j ≤ W 、 {\displaystyle \sum _{j=1}^{n}w_{j}x_{j}\leq W,}
× j ≥ 0 、 × j {\displaystyle x_{j}\geq 0,x_{j}} すべてのjについて積分

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

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

最大化する ∑ 私 ＝ 1 け ∑ j ∈ 北 私 p 私 j × 私 j {\displaystyle \sum _{i=1}^{k}\sum _{j\in N_{i}}p_{ij}x_{ij}}
対象となる ∑ 私 ＝ 1 け ∑ j ∈ 北 私 わ 私 j × 私 j ≤ W 、 {\displaystyle \sum _{i=1}^{k}\sum _{j\in N_{i}}w_{ij}x_{ij}\leq W,}
∑ j ∈ 北 私 × 私 j ＝ 1 、 {\displaystyle \sum _{j\in N_{i}}x_{ij}=1,} すべての人のために 1 ≤ 私 ≤ け {\displaystyle 1\leq i\leq k}
x i j ∈ { 0 , 1 } {\displaystyle x_{ij}\in \{0,1\}} すべての人のために 1 ≤ i ≤ k {\displaystyle 1\leq i\leq k} j ∈ N i {\displaystyle j\in N_{i}}

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

最大化する ∑ j = 1 n p j x j {\displaystyle \sum _{j=1}^{n}p_{j}x_{j}}
対象となる ∑ j = 1 n p j x j ≤ W , {\displaystyle \sum _{j=1}^{n}p_{j}x_{j}\leq W,}
x j ∈ { 0 , 1 } {\displaystyle x_{j}\in \{0,1\}}

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

最大化する ∑ i = 1 m ∑ j = 1 n p j x i j {\displaystyle \sum _{i=1}^{m}\sum _{j=1}^{n}p_{j}x_{ij}}
対象となる ∑ j = 1 n w j x i j ≤ W i , {\displaystyle \sum _{j=1}^{n}w_{j}x_{ij}\leq W_{i},} すべての人のために 1 ≤ i ≤ m {\displaystyle 1\leq i\leq m}
∑ i = 1 m x i j ≤ 1 , {\displaystyle \sum _{i=1}^{m}x_{ij}\leq 1,} すべての人のために 1 ≤ j ≤ n {\displaystyle 1\leq j\leq n}
x i j ∈ { 0 , 1 } {\displaystyle x_{ij}\in \{0,1\}} すべての人のために 1 ≤ j ≤ n {\displaystyle 1\leq j\leq n} 1 ≤ i ≤ m {\displaystyle 1\leq i\leq m}

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

二次ナップサック問題：

最大化する ∑ j = 1 n p j x j + ∑ i = 1 n − 1 ∑ j = i + 1 n p i j x i x j {\displaystyle \sum _{j=1}^{n}p_{j}x_{j}+\sum _{i=1}^{n-1}\sum _{j=i+1}^{n}p_{ij}x_{i}x_{j}}
対象となる ∑ j = 1 n w j x j ≤ W , {\displaystyle \sum _{j=1}^{n}w_{j}x_{j}\leq W,}
x j ∈ { 0 , 1 } {\displaystyle x_{j}\in \{0,1\}} すべての人のために 1 ≤ j ≤ n {\displaystyle 1\leq j\leq n}

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

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

アイテムの集合といわゆる要素の集合が与えられたとき、各アイテムは要素集合の部分集合に対応する。アイテムは非負の利益、を持ち、要素は非負の重み、を持つ。アイテム集合の総重量は、対応する要素集合の和集合の要素の総重量によって与えられる。目的は、総重量がナップザックの容量を超えず、かつ利益が最大となるアイテムの部分集合を見つけることである。 n {\displaystyle n} N = { 1 , … , n } {\displaystyle N=\{1,\ldots ,n\}} m {\displaystyle m} P = { 1 , … , m } {\displaystyle P=\{1,\ldots ,m\}} j {\displaystyle j} P j {\displaystyle P_{j}} P {\displaystyle P} j {\displaystyle j} p j {\displaystyle p_{j}} j = 1 , … , n {\displaystyle j=1,\ldots ,n} i {\displaystyle i} w i {\displaystyle w_{i}} i = 1 , … , m {\displaystyle i=1,\ldots ,m}

複数の制約

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

最大化する ∑ j = 1 n p j x j {\displaystyle \sum _{j=1}^{n}p_{j}x_{j}}
対象となる ∑ j = 1 n w i j x j ≤ W i , {\displaystyle \sum _{j=1}^{n}w_{ij}x_{j}\leq W_{i},} すべての人のために 1 ≤ i ≤ m {\displaystyle 1\leq i\leq m}
x j ≥ 0 {\displaystyle x_{j}\geq 0} 、整数 x j {\displaystyle x_{j}} すべての人のために 1 ≤ j ≤ n {\displaystyle 1\leq j\leq n}

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

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

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

ナップサックのような問題

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

最大化する ∑ j = 1 n x j {\displaystyle \sum _{j=1}^{n}x_{j}}
対象となる ∑ j = 1 n w j x j ≤ W , {\displaystyle \sum _{j=1}^{n}w_{j}x_{j}\leq W,}
x j ∈ { 0 , 1 } , {\displaystyle x_{j}\in \{0,1\},} ∀ j ∈ { 1 , … , n } {\displaystyle \forall j\in \{1,\ldots ,n\}}

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

最小化 ∑ i = 1 n y i {\displaystyle \sum _{i=1}^{n}y_{i}}
対象となる ∑ j = 1 n w j x i j ≤ W y i , {\displaystyle \sum _{j=1}^{n}w_{j}x_{ij}\leq Wy_{i},} ∀ i ∈ { 1 , … , n } {\displaystyle \forall i\in \{1,\ldots ,n\}}
∑ i = 1 n x i j = 1 {\displaystyle \sum _{i=1}^{n}x_{ij}=1} ∀ j ∈ { 1 , … , n } {\displaystyle \forall j\in \{1,\ldots ,n\}}
y i ∈ { 0 , 1 } {\displaystyle y_{i}\in \{0,1\}} ∀ i ∈ { 1 , … , n } {\displaystyle \forall i\in \{1,\ldots ,n\}}
x i j ∈ { 0 , 1 } {\displaystyle x_{ij}\in \{0,1\}} ∀ i ∈ { 1 , … , n } ∧ ∀ j ∈ { 1 , … , n } {\displaystyle \forall i\in \{1,\ldots ,n\}\wedge \forall j\in \{1,\ldots ,n\}}

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

最小化 ∑ i = 1 m x i {\displaystyle \sum _{i=1}^{m}x_{i}}
対象となる ∑ i = 1 m b i j x i ≥ B j , {\displaystyle \sum _{i=1}^{m}b_{ij}x_{i}\geq B_{j},} すべての人のために 1 ≤ j ≤ n {\displaystyle 1\leq j\leq n}
x i ∈ { 0 , 1 , … , n } {\displaystyle x_{i}\in \{0,1,\ldots ,n\}} すべての人のために 1 ≤ i ≤ m {\displaystyle 1\leq i\leq m}

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

最大化する ∑ i = 1 k ∑ j = 1 n p i j x i j {\displaystyle \sum _{i=1}^{k}\sum _{j=1}^{n}p_{ij}x_{ij}}
対象となる ∑ i = 1 n x i j = 1 , {\displaystyle \sum _{i=1}^{n}x_{ij}=1,} すべての人のために 1 ≤ j ≤ n {\displaystyle 1\leq j\leq n}
∑ j = 1 n x i j = 1 , {\displaystyle \sum _{j=1}^{n}x_{ij}=1,} すべての人のために 1 ≤ i ≤ n {\displaystyle 1\leq i\leq n}
x i j ∈ { 0 , 1 } {\displaystyle x_{ij}\in \{0,1\}} すべての人のために 1 ≤ i ≤ k {\displaystyle 1\leq i\leq k} j ∈ N i {\displaystyle j\in N_{i}}

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

最大化する ∑ j = 1 n x j p j w 0 + ∑ j = 1 n x j w j {\displaystyle {\frac {\sum _{j=1}^{n}x_{j}p_{j}}{w_{0}+\sum _{j=1}^{n}x_{j}w_{j}}}}
対象となる ∑ j = 1 n w j x j ≤ W , {\displaystyle \sum _{j=1}^{n}w_{j}x_{j}\leq W,}
x j ∈ { 0 , 1 } , {\displaystyle x_{j}\in \{0,1\},} ∀ j ∈ { 1 , … , n } {\displaystyle \forall j\in \{1,\ldots ,n\}}

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

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

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

参考文献

  1. ^ Martello, Silvano and Toth, Paolo (1990). 『ナップサック問題：アルゴリズムとコンピュータ実装』John Wiley & Sons . ISBN 978-0471924203。{{cite book}}: CS1 maint: multiple names: authors list (link)
  2. ^ abcd ケラー、ハンスとフェルシー、ウルリッヒとパイジンジャー、デイヴィッド (2004)。ナップザックの問題。スプリンガー・フェルラーグ。ISBN 978-3-540-40286-2。{{cite book}}: CS1 maint: multiple names: authors list (link)
  3. ^ Lueker, GS (1975).非負整数計画法における2つのNP完全問題. レポートNo. 178, コンピュータサイエンス研究所, プリンストン.
  4. ^ Gens, GV; Levner, EV (1979). 「組合せ問題に対する計算量と近似アルゴリズム：概説」. ソ連科学アカデミー中央経済数学研究所, モスクワ.
  5. ^ 「高速近似法の存在について」非線形計画法. 4 : 415–437 . 1980.
  6. ^ Magazine, Michael J.; Chern, Maw-Sheng (1984). 「多次元ナップサック問題に対する近似スキームに関するノート」.オペレーションズ・リサーチ数学. 9 (2): 244– 247. doi :10.1287/moor.9.2.244.
  7. ^ Cohen, Reuven; Katzir, Liran (2008). 「一般化最大被覆問題」. Information Processing Letters . 108 : 15–22 . CiteSeerX 10.1.1.156.2073 . doi :10.1016/j.ipl.2008.03.017. 
  • 「ナップサック問題に対するアルゴリズム」、D. Pisinger。博士論文、DIKU、コペンハーゲン大学、レポート95/1（1995年）。
Retrieved from "https://en.wikipedia.org/w/index.php?title=List_of_knapsack_problems&oldid=1205447760"