ナップサック問題

ナップサック問題#

こちらでは、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$のコストのリスト$\bm{v}$と重さのリスト$\bm{w}$を作ることで、問題を表現することができます。

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

\[ \nonumber \bm{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によるモデル構築#

変数定義#

ナップサック問題で用いられている変数$\bm{v}, \bm{w}, N, W, x_i, i$を、以下のようにして定義しましょう。

import jijmodeling as jm

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

v = jm.Placeholder('v', ndim=1), w = jm.Placeholder('w', ndim=1)でナップサックに入れる物の価値と重さを表現する一次元のリストを定義し、さらにW = jm.Placeholder('W')ではナップサックの容量制限を表す$W$を定義しています。 N=v.len_at(0, latex="N")のようにすることで、先ほど定義したvの要素数を取得しています。これを用いて、最適化に用いるバイナリ変数のリストをx = jm.BinaryVar('x', shape=(N))を定義します。最後のi = jm.Element('i', (0, N))により$0 \leq i < N$を満たす$v_i, w_i, x_i$の添字を定義します。

制約と目的関数の実装#

式(1), (2)を実装しましょう。

# set problem
problem = jm.Problem('Knapsack', sense=jm.ProblemSense.MAXIMIZE) 
# set constraint: less than the capacity
problem += jm.Constraint("capacity", jm.sum(i, w[i]*x[i]) <= W)
# set objective function
problem += jm.sum(i, v[i]*x[i])

jm.sum(i, ...)のようにすることで、$\sum_i$を実装することができます。 jm.Constraint("capacity", ...)のようにすることで、”capacity”という名の制約を設定しています。　　実装した数理モデルを、Jupyter Notebookで表示してみましょう。

Constraint(制約名, 制約式)とすることで、制約式に適当な制約名を付与することができます。
実際に実装された数式をJupyter Notebookで表示してみましょう。

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{capacity} & \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}\]

インスタンスの作成#

先程の冒険家の物語を、インスタンスとして設定しましょう。ただし物の価値は$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} 

JijModeling Interpreterを用いてOMMX　Instanceを作成#

instance = jm.Interpreter(instance_data).eval_problem(problem)

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

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

import ommx_openjij_adapter as oj_ad
import openjij as oj

adapter = oj_ad.OMMXOpenJijSAAdapter(instance)
sampleset = adapter.sample(instance, num_reads=100)

解の表示#

sampleset.summary

	objective	feasible
sample_id
0	14.0	True
5	14.0	True
13	14.0	True
22	14.0	True
26	14.0	True
...	...	...
12	7.0	False
81	7.0	False
2	6.0	False
46	5.0	False
50	5.0	False

100 rows × 2 columns

x_value = sampleset.best_feasible_unrelaxed().extract_decision_variables("x")
items = [i[0] for i, v in x_value.items() if v == 1]
print("Items: ", items)
print("Total value: ", sum(inst_v[items]))
print("Total weight: ", sum(inst_w[items]))

Items:  [1, 4, 5]
Total value:  14
Total weight:  18