SCIPで最適化問題を解く

jijmodeling の使い方を理解するために、このページではナップサック問題を解いてみましょう。ただし、jijmodeling は数理モデルを記述するためのツールであるため、単独では最適化問題を解くことはできません。なので、数理最適化ソルバーSCIPと組み合わせて解くこととします。

jijmodeling とSCIPを組み合わせて使うには、 ommx-pyscipopt-adapter (GitHub, PyPI) というPythonパッケージをインストールする必要があります。以下のコマンドでインストールしてください。

pip install ommx-pyscipopt-adapter

問題設定

ナップサック問題は以下のように数理モデルとして定式化することができます：

\[\begin{split} \begin{align*} \mathrm{maximize} \quad & \sum_{i=0}^{N-1} v_i x_i \\ \mathrm{s.t.} \quad & \sum_{i=0}^{n-1} w_i x_i \leq W, \\ & x_{i} \in \{ 0, 1\} \end{align*} \end{split}\]

Hint

ナップサック問題の定式化について詳しく知りたい場合は こちら を参照してください。

この数理モデルにあるそれぞれのパラメーターの意味は以下の通りです：

パラメーター	説明
\(N\)	アイテムの総数
\(v_{i}\)	アイテム \(i\) の価値
\(w_{i}\)	アイテム \(i\) の重さ
\(W\)	ナップサックの耐荷重

今回の説明では、上記の数理モデルのパラメーター \(v_{i}, w_{i}, W\) に、次の値を入力して得られるインスタンスを解くことを考えます：

パラメーター	値
\(v_{i}\)	[10, 13, 18, 31, 7, 15]
\(w_{i}\)	[11, 15, 20, 35, 10, 33]
\(W\)	47

インスタンスとは

jijmodeling では、数理モデルのパラメータに具体的な値を入れたものを”インスタンス”と呼んでいます。

インスタンスの生成手順

jijmodeling を使うと、ソルバーに入力するためのインスタンスを次の3ステップで生成できます：

1. jijmodeling でナップサック問題を定式化する

2. Interpreter オブジェクトにインスタンスデータを登録する

3. Interpreter オブジェクトを使って数理モデルをインスタンスに変換する

Step1. JijModelingでナップサック問題を定式化する

jijmodeling を使用してナップサック問題を定式化すると、以下のPythonコードになります：

import jijmodeling as jm

# アイテムの価値
v = jm.Placeholder("v", ndim=1)
# アイテムの重さ
w = jm.Placeholder("w", ndim=1)
# ナップサックの耐荷重
W = jm.Placeholder("W")
# アイテムの総数
N = v.len_at(0, latex="N")
# アイテムiをナップサックに入れる場合は1, 入れない場合は0を取る決定変数
x = jm.BinaryVar("x", shape=(N,)) 
# アイテムに割り当てられた番号を走る添え字
i = jm.Element("i", belong_to=(0, N))

problem = jm.Problem("problem", sense=jm.ProblemSense.MAXIMIZE)
# 目的関数
problem += jm.sum(i, v[i] * x[i])
# 制約条件: ナップサックの耐荷重を超えない
problem += jm.Constraint("重量制限", jm.sum(i, w[i] * x[i]) <= W)
problem

\[\begin{split}\begin{array}{cccc}\text{Problem:} & \text{problem} & & \\& & \max \quad \displaystyle \sum_{i = 0}^{N - 1} v_{i} \cdot x_{i} & \\\text{{s.t.}} & & & \\ & \text{重量制限} & \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}\]

Hint

jijmodeling での定式化の方法については詳しく知りたい場合はこちらを参照してください。

Step2. Interpreter オブジェクトにインスタンスデータを登録する

Step1で定式化した数理モデルの Placeholder に入力するインスタンスデータを用意し、 Interpreter オブジェクトに登録します。

Interpreter クラスのコンストラクタの引数に、以下のキーと値を持つ辞書を渡すことでインスタンスデータを登録できます：

• キー：Placeholder オブジェクトの name プロパティに設定した文字列

• 値：入力するデータ

instance_data = {
    "v": [10, 13, 18, 31, 7, 15],  # アイテムの価値のデータ
    "w": [11, 15, 20, 35, 10, 33], # アイテムの重さのデータ
    "W": 47,                       # ナップサックの耐荷重のデータ
}
interpreter = jm.Interpreter(instance_data)

Step3. Interpreter オブジェクトを使って数理モデルをインスタンスに変換する

数理モデルをインスタンスに変換するには、Interpreter.eval_problem メソッドを使用します。インスタンスデータが登録された Interpreter オブジェクトの eval_problem メソッドに Problem オブジェクトを渡すと、その Problem オブジェクトが持つ Placeholder にインスタンスデータを入力され、インスタンスに変換されます:

instance = interpreter.eval_problem(problem)

Hint

Interpreter.eval_problem の返却値は ommx.v1.Instance オブジェクトです。OMMXについて詳しく知りたい場合はこちらを参照してください。

最適化問題を解く

では、Step3で得られたインスタンスを最適化ソルバーSCIPで解いてみましょう。以下のPythonコードで目的関数の最適値を得ることができます:

from ommx_pyscipopt_adapter import instance_to_model, model_to_solution

# インスタンスをSCIPの読み取れる形に変換する
model = instance_to_model(instance)
# SCIPでインスタンスを解く
model.optimize()
# SCIPで得られた結果を取得する
solution = model_to_solution(model, instance)

print(f"目的関数の最適値: {solution.objective}")

目的関数の最適値: 41.0

また、solution の decision_variables プロパティを使うことで pandas.DataFrame オブジェクトとして決定変数の状態を表示できます:

solution.decision_variables[["name", "subscripts", "value"]]

	name	subscripts	value
id
0	x	[0]	1.0
1	x	[1]	1.0
2	x	[2]	1.0
3	x	[3]	0.0
4	x	[4]	0.0
5	x	[5]	0.0

Hint

ommx_pyscipopt_adapter の model_to_solution の返却値は ommx.v1.Solution オブジェクトです。OMMXについて詳しく知りたい場合はこちらを参照してください。