SCIPで最適化問題を解く

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}\]

ヒント

ナップサック問題の定式化について詳しく知りたい場合は JijZeptチュートリアル を参照してください。

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

パラメーター

説明

\(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. ナップサック問題を定式化する

  2. インスタンスデータを用意する

  3. インスタンスを生成する

Diagram of the process to generate an instance from a mathematical model

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

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

import jijmodeling as jm

@jm.Problem.define("Knapsack", sense=jm.ProblemSense.MAXIMIZE)
def knapsack_problem(problem: jm.DecoratedProblem):
    # アイテムの総数
    N = problem.Natural("N")
    # アイテムの価値
    v = problem.Natural("v", shape=N)
    # アイテムの重さ
    w = problem.Natural("w", shape=N)
    # ナップサックの耐荷重
    W = problem.Natural("W")
    # アイテムiをナップサックに入れる場合は1, 入れない場合は0を取る決定変数
    x = problem.BinaryVar("x", shape=(N,)) 

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

knapsack_problem
\[\begin{split}\begin{array}{rl} \text{Problem}\colon &\text{Knapsack}\\\displaystyle \max &\displaystyle \sum _{i=0}^{N-1}{{v}_{i}\cdot {x}_{i}}\\&\\\text{s.t.}&\\&\begin{aligned} \text{重量制限}&\quad \displaystyle \sum _{i=0}^{N-1}{{w}_{i}\cdot {x}_{i}}\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}N&\in \mathbb{N}&\quad &\text{A scalar placeholder in }\mathbb{N}\\v&\in \mathop{\mathrm{Array}}\left[N;\mathbb{N}\right]&\quad &1\text{-dimensional array of placeholders with elements in }\mathbb{N}\\W&\in \mathbb{N}&\quad &\text{A scalar placeholder in }\mathbb{N}\\w&\in \mathop{\mathrm{Array}}\left[N;\mathbb{N}\right]&\quad &1\text{-dimensional array of placeholders with elements in }\mathbb{N}\\\end{alignedat}\end{array} \end{split}\]

ヒント

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

Step2. インスタンスデータを用意する#

次に、Step1 で定式化した数理モデルのパラメーター \(v_i, w_i, W\) のインスタンスデータを用意します。

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

Step3. インスタンスに変換する#

最後に、定式化した数理モデルと用意したインスタンスデータを用いてインスタンスを生成しましょう。

instance = knapsack_problem.eval(instance_data)

ヒント

Problem.eval の返却値は ommx.v1.Instance オブジェクトです。詳しくはインスタンスの生成 や ommx.v1.Instance を参照してください。

最適化問題を解く#

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

from ommx_pyscipopt_adapter import OMMXPySCIPOptAdapter

# SCIPを介して問題を解き、ommx.v1.Solutionとして解を取得
solution = OMMXPySCIPOptAdapter.solve(instance)

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

目的関数の最適値: 41.0

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

solution.decision_variables_df[["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

ヒント

OMMXPySCIPOptAdapter.solve の返却値は ommx.v1.Solution オブジェクトです。詳しくは ommx.v1.Solution を参照してください。

目次