ナップサック問題

ナップサック問題#

JijSolverとJijModelingを用いて、ナップサック問題を解く方法を紹介します。この問題はLucas, 2014, “Ising formulations of many NP problems” 5.2. Knapsack with Integer Weightsなどでも取り上げられています。

ナップサック問題とは#

ナップサック問題は、以下のような場合において最適解を見つける問題です。この問題はNP困難な整数計画問題として知られています。ナップサック問題の具体例として、以下のストーリーを考えてみましょう。

ある探検家が洞窟を冒険していると、思いがけず宝物を見つけました。

	Treasure A	Treasure B	Treasure C	Treasure D	Treasure E	Treasure F
Price	$5000	$7000	$2000	$1000	$4000	$3000
weight	800g	1000g	600g	400g	500g	300g

しかし、探検家が持っているのは容量2キロの小さなナップサックだけでした。当然、探検家はこのナップサックに出来るだけ価値の高い宝物を詰め込みたいと考えます。探検家は、どの宝物をナップサックに詰め込めば良いでしょうか？

このような状況下で最適解を求めるのがナップサック問題です。ナップサック問題はNP困難な整数計画問題として有名なものの1つです。

定式化#

上の例を一般化して数理モデルを定式化してみましょう。ナップサックに入れるアイテム（宝物）の集合を $\{ 0, 1, \dots, i, \dots, N-1 \}$ とし、各アイテム $i$ の価値を $v_i$、重量を $w_i$ と書くことにします。

\[ v = \{v_0, v_1, \dots, v_i, \dots, v_{N-1}\} \]

\[ w = \{w_0, w_1, \dots, w_i, \dots, w_{N-1}\} \]

さらに、アイテム $i$ を詰め込むかどうかを表現する決定変数として $x_i$ を導入します。 $x_i$ はアイテム $i$ をナップサックに詰め込む場合に1を取り、そうでない場合には0になるバイナリ変数です。また、ナップサックの容量を $W$ で表すことにします。
ナップサックに入れるアイテムの価値の合計を最大化することを目指します。そのために、ナップサックに入れるアイテムの価値の合計を数式で表現しましょう。そしてナップサックの容量制限を数式で表現する必要があります。最終的に、この問題の数理モデルは以下のようになります。

\[ \max \quad \sum_{i=0}^{N-1} v_i x_i \tag{1} \]

\[ \mathrm{s.t.} \quad \sum_{i=0}^{N-1} w_i x_i \leq W \tag{2} \]

\[ x_i \in \{0, 1\} \quad (\forall i \in \{0, 1, \dots, N-1\}) \tag{3} \]

JijModelingによる定式化#

次に、JijModelingを使って上記の数理モデルを実装してみましょう。まずは、数理モデルに現れる変数およびパラメーターを定義します。

import jijmodeling as jm

v = jm.Placeholder("v", ndim=1)
N = v.len_at(0, latex="N")
w = jm.Placeholder("w", ndim=1)
W = jm.Placeholder("W")
x = jm.BinaryVar("x", shape=(N,))
i = jm.Element("i", belong_to=(0, N))

ここで v はアイテム $i$ の価値 $v_i$ のリスト、 w はアイテム $i$ の重量 $w_i$ のリストを定義しており、 N はアイテムの個数、 W はナップサックの容量を定義しています。また、$x_i$ に相当するバイナリ変数として x を定義しています。 i は後の数理モデル構築のために用意された添字で、アイテム $i$ を相当します。

目的関数の実装#

目的関数として式(1)を実装すると以下のようになります。

problem = jm.Problem("Knapsack", sense=jm.ProblemSense.MAXIMIZE)
problem += jm.sum(i, v[i]*x[i])

ナップサック問題は目的関数を最大化する問題であるため、 sense=jm.ProblemSense.MAXIMIZE を設定しています。

制約条件の実装#

制約条件として式(2)を実装すると以下のようになります。

problem += jm.Constraint("weight", jm.sum(i, w[i]*x[i]) <= W)

これで数理モデルの実装は完了です。正しく数理モデルが実装されているかをLaTeX表示を通して確認してみましょう。

problem

\[\begin{split}\begin{array}{cccc}\text{Problem:} & \text{Knapsack} & & \\& & \max \quad \displaystyle \sum_{i = 0}^{N - 1} v_{i} \cdot x_{i} & \\\text{{s.t.}} & & & \\ & \text{weight} & \displaystyle \sum_{i = 0}^{N - 1} w_{i} \cdot x_{i} \leq W & \\\text{{where}} & & & \\& x & 1\text{-dim binary variable}\\\end{array}\end{split}\]

インスタンスデータの準備#

次にインスタンスデータを準備します。ここでは100個のアイテムをランダムに生成し、ナップサックの容量を100とするものとします。

import numpy as np

inst_v = np.random.randint(5,30,100)
inst_w = inst_v + np.random.randint(-2,20,100)
inst_W = 100
instance_data = {"v": inst_v, "w": inst_w, "W": inst_W}

inst_v , inst_w, inst_Wはそれぞれアイテムの価値のリスト、アイテムの重量のリスト、ナップサックの容量を表します。