SCIPで最適化問題を解く#
jijmodeling
の使い方を理解するために、このページではナップサック問題を解いてみましょう。ただし、jijmodeling
は数理モデルを記述するためのツールであるため、単独では最適化問題を解くことはできません。なので、数理最適化ソルバーSCIPと組み合わせて解くこととします。
jijmodeling
とSCIPを組み合わせて使うには、 ommx-pyscipopt-adapter
(GitHub, PyPI) というPythonパッケージをインストールする必要があります。以下のコマンドでインストールしてください。
pip install ommx-pyscipopt-adapter
問題設定#
ナップサック問題は以下のように数理モデルとして定式化することができます:
Hint
ナップサック問題の定式化について詳しく知りたい場合は こちら を参照してください。
この数理モデルにあるそれぞれのパラメーターの意味は以下の通りです:
パラメーター |
説明 |
---|---|
\(N\) |
アイテムの総数 |
\(v_{i}\) |
アイテム \(i\) の価値 |
\(w_{i}\) |
アイテム \(i\) の重さ |
\(W\) |
ナップサックの耐荷重 |
今回の説明では、上記の数理モデルのパラメーター \(v_{i}, w_{i}, W\) に、次の値を入力して得られるインスタンスを解くことを考えます:
パラメーター |
値 |
---|---|
\(v_{i}\) |
|
\(w_{i}\) |
|
\(W\) |
|
インスタンスとは
jijmodeling
では、数理モデルのパラメータに具体的な値を入れたものを”インスタンス”と呼んでいます。
インスタンスの生成手順#
jijmodeling
を使うと、ソルバーに入力するためのインスタンスを次の3ステップで生成できます:
jijmodeling
でナップサック問題を定式化するInterpreter
オブジェクトにインスタンスデータを登録する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
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について詳しく知りたい場合はこちらを参照してください。