ナップサック問題

ナップサック問題#

こちらでは、Lucas, 2014, “Ising formulations of many NP problems”の 5.2. Knapsack with Integer Weights を OpenJij と JijModeling、そして ommx-openjij-adapter を用いて解く方法について説明します。

概要: ナップサック問題とは#

ナップサック問題は、具体的には以下のような状況で最適解を求める問題です。 最も有名なNP困難な整数計画問題の一つとして知られています。まずは具体例を考えてみましょう。

具体例#

この問題の具体例として、以下のような物語を考えます。

ある探検家がある洞窟を探検していました。しばらく洞窟の中を歩いていると、思いがけなく複数の宝物を発見しました。

宝物A

宝物B

宝物C

宝物D

宝物E

宝物F

値段

$5000

$7000

$2000

$1000

$4000

$3000

重さ

800g

1000g

600g

400g

500g

300g

しかし探検家の手持ちの荷物の中で宝物を運べるような袋としては、残念ながら小さなナップサックしか持ち合わせていませんでした。 このナップサックには2kgの荷物しか入れることができません。探検家はこのナップサックに入れる宝物の価値をできるだけ高くしたいのですが、どの荷物を選べば最も効率的に宝物を持って帰ることができるでしょうか。

問題の一般化#

この問題を一般化するには、ナップサックに入れる荷物\(N\)個の集合\(\{ 0, 1, \dots, i, \dots, N-1\}\)があり、各荷物が\(i\)をインデックスとして持っているものとして考えます。
ナップサックに入れる各荷物\(i\)のコストのリスト\(v\)と重さのリスト\(w\)を作ることで、問題を表現することができます。

\[ \nonumber v = \{v_0, v_1, \dots, v_i, \dots, v_{N-1}\} \]
\[ \nonumber w = \{w_0, w_1, \dots, w_i, \dots, w_{N-1}\} \]

さらに\(i\)番目の荷物を選んだことを表すバイナリ変数を\(x_i\)としましょう。この変数は\(i\)をナップサックに入れるとき\(x_i = 1\)、入れないとき\(x_i = 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を使って上記の数理モデルを定式化してみましょう。まず、ナップサック問題は目的関数を最大化する問題であるため、 sense=jm.ProblemSense.MAXIMIZE を設定します。

import jijmodeling as jm

problem = jm.Problem("Knapsack", sense=jm.ProblemSense.MAXIMIZE)

式(1), (2)で用いられている変数を、以下のようにして定義しましょう。

v = problem.Float('v', ndim=1)
N = problem.DependentVar("N", v.len_at(0))
w = problem.Float('w', ndim=1)
W = problem.Float('W')
x = problem.BinaryVar('x', shape=(N,))

v はアイテム \(i\) の価値 \(v_i\) のリスト、 w はアイテム \(i\) の重量 \(w_i\) のリストを定義しており、 N はアイテムの個数、 W はナップサックの容量を定義しています。また、\(x_i\) に相当するバイナリ変数として x を定義しています。

目的関数#

式(1)の目的関数は以下のように定式化できます。

problem += jm.sum(v * x)

jm.sum(...)で\(\sum_i\)を表せます。

制約#

式(2)の制約は以下のように定式化できます。

problem += problem.Constraint("capacity", jm.sum(w * x) <= W)

problem.Constraint("capacity", ...)で、”capacity”という名前の制約を設定できます。

実際に定式化された数式をJupyter Notebookで表示してみましょう。

problem
\[\begin{split}\begin{array}{rl} \text{Problem}\colon &\text{Knapsack}\\\displaystyle \max &\displaystyle \sum _{\vec{\imath }}{{{\left(v\cdot x\right)}}_{\vec{\imath }}}\\&\\\text{s.t.}&\\&\begin{aligned} \text{capacity}&\quad \displaystyle \sum _{\vec{\imath }}{{{\left(w\cdot x\right)}}_{\vec{\imath }}}\leq W\end{aligned} \\&\\\text{where}&\\&\text{Decision Variables:}\\&\qquad \begin{alignedat}{2}x&\in \mathop{\mathrm{Array}}\left[N;\left\{0, 1\right\}\right]&\quad &1\text{-dim binary variable}\\\end{alignedat}\\&\\&\text{Placeholders:}\\&\qquad \begin{alignedat}{2}v&\in \mathop{\mathrm{Array}}\left[(-);\mathbb{R}\right]&\quad &1\text{-dimensional array of placeholders with elements in }\mathbb{R}\\W&\in \mathbb{R}&\quad &\text{A scalar placeholder in }\mathbb{R}\\w&\in \mathop{\mathrm{Array}}\left[(-);\mathbb{R}\right]&\quad &1\text{-dimensional array of placeholders with elements in }\mathbb{R}\\\end{alignedat}\\&\\&\text{Dependent Variables:}\\&\qquad \begin{alignedat}{2}N&=\mathop{\mathtt{len\_{}at}}\left(v,0\right)&\quad &\in \mathbb{N}\\\end{alignedat}\end{array} \end{split}\]

インスタンスの作成#

先程の冒険家の物語を、インスタンスとして設定しましょう。 ただし物の価値は$1000で規格化、さらに物の重さも100gで規格化された値を用います。

import numpy as np

# set a list of values & weights 
inst_v = np.array([5, 7, 2, 1, 4, 3])
inst_w = np.array([8, 10, 6, 4, 5, 3])
# set maximum weight
inst_W = 20
instance_data = {'v': inst_v, 'w': inst_w, 'W': inst_W}

OpenJijによる最適化計算の実行#

OpenJijのシミュレーテッド・アニーリングを用いて、最適化問題を解いてみましょう。

from ommx_openjij_adapter import OMMXOpenJijSAAdapter

instance = problem.eval(instance_data)

adapter = OMMXOpenJijSAAdapter(instance)
best_sample = adapter.sample(instance, num_reads=100).best_feasible_unrelaxed

解の可視化#

得られた解を用いて、詰め込んだアイテムの価値と重量を表示してみましょう。

df = best_sample.decision_variables_df
obj = best_sample.objective
x_df = df[(df["name"] == "x") & (df["value"] > 0.5)]
indices = [sub[0] for sub in x_df["subscripts"]]
sum_w = np.sum(inst_w[indices])

print("Values of chosen items: ", inst_v[indices])
print("Weights of chosen items: ", inst_w[indices])
print("Total value from objective: ", obj)
print("Total weight: ", sum_w)

Values of chosen items:  [7 4 3]
Weights of chosen items:  [10  5  3]
Total value from objective:  14.0
Total weight:  18
Contents