OpenJijで最適化問題を解く

OpenJijで最適化問題を解く#

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

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

pip install ommx-openjij-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 で得られたインスタンスを OpenJij のシュミレーテッドアニーリングで解いてみましょう。

from ommx_openjij_adapter import OMMXOpenJijSAAdapter

# OpenJijを介して問題を解き、ommx.v1.Solutionとして解を取得
solution = OMMXOpenJijSAAdapter.solve(
    instance,
    num_reads=100,
    num_sweeps=10,
    uniform_penalty_weight=1.6,
)

OMMXOpenJijSAAdapter を使えば、ommx.v1.Instance で定義されたインスタンスをペナルティ法やログエンコーディングで QUBO/HUBO 形式に変換して解く、という操作を簡単に行うことができます。 また、得られた解は decision_variable_df プロパティを使うことで pandas.DataFrame オブジェクトとして確認することができます:

df = solution.decision_variables_df
df[df["name"] == "x"][["name", "subscripts", "value"]]
name subscripts value
id
0 x [0] 0.0
1 x [1] 1.0
2 x [2] 1.0
3 x [3] 0.0
4 x [4] 1.0
5 x [5] 0.0

注釈

OMMXOpenJijSAAdapter は内部で QUBO/HUBO 形式への変換を行うため、入力値のインスタンスから決定変数が追加されたり、目的関数が変化しています。そのため、上記のような pandas.DataFrame による要素の絞り込みが必要になっています。

ヒント

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

目次