OMMX Adapterで最適化問題を解く

OMMX Adapterで最適化問題を解く#

OMMXでは、既存の数理最適化ツールと相互連携するためのソフトウェアとしてOMMX Adapterを提供しています。OMMX Adapterを使うことで、OMMXが規定するスキーマで表現された最適化問題を既存の数理最適化ツールに入力可能にしたり、既存の数理最適化ツールから得られた情報をOMMXが規定するスキーマに変換したりすることができます。

ここでは、0-1ナップサック問題をOMMX PySCIPOpt Adapterを介して解く方法を紹介します。

必要なライブラリのインストール#

まず、OMMX PySCIPOpt Adapterを準備しましょう。以下のコマンドでインストールできます。

pip install ommx-pyscipopt-adapter

最適化計算を実行するための2つのステップ#

0-1ナップサック問題をOMMX PySCIPOpt Adapterで解くフロー

Fig. 4 0-1ナップサック問題をOMMX PySCIPOpt Adapterで解くフロー。#

OMMX PySCIPOpt Adapterを介して0-1ナップサック問題を解くためには、次の2つのステップを踏む必要があります：

  1. 0-1ナップサック問題のインスタンスを用意する

  2. OMMX Adapterを介して最適化計算を実行する

ステップ1.では、OMMX MessageのInstanceスキーマで定義された ommx.v1.Instance オブジェクトを作成します。このオブジェクトを作成する方法は複数ありますが、ここではOMMX Python SDKを使用して直接記述する方法を採用します。

Tip

ommx.v1.Instance オブジェクトを用意する方法は4つあります：

  1. OMMX Python SDKを使って ommx.v1.Instance を直接記述する

  2. OMMX Python SDKを使ってMPSファイルを ommx.v1.Instance に変換する

  3. 数理最適化ツールで記述した問題インスタンスをOMMX Adapterで ommx.v1.Instance に変換する

  4. JijModelingを使って ommx.v1.Instance を出力する

ステップ2.では、 ommx.v1.Instance オブジェクトをPySCIPOptの Model オブジェクトに変換し、SCIPによる最適化計算を実行します。計算結果は、OMMX MessageのSolutionスキーマで定義された ommx.v1.Solution オブジェクトとして取得できます。

ステップ1: 0-1ナップサック問題のインスタンスを用意する#

0-1ナップサック問題は以下のように定式化されます：

\[\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 - W \leq 0, \\ & x_{i} \in \{ 0, 1\} \end{align*} \end{split}\]

ここでは、この数理モデルのパラメータに以下のデータを設定することとします:

# 0-1ナップサック問題のデータ
v = [10, 13, 18, 31, 7, 15]   # 各アイテムの価値
w = [11, 25, 20, 35, 10, 33] # 各アイテムの重さ
W = 47  # ナップサックの耐荷重
N = len(v)  # アイテムの総数

この数理モデルとデータに基づいて、OMMX Python SDKを使用して問題インスタンスを記述するコードは次のようになります：

from ommx.v1 import Instance, DecisionVariable, Constraint

# 決定変数を定義する
x = [
    # バイナリ変数 x_i を定義する
    DecisionVariable.binary(
        # 決定変数のIDを指定する
        id=i,
        # 決定変数の名前を指定する
        name="x",
        # 決定変数の添え字を指定する
        subscripts=[i],
    )
    # バイナリ変数をアイテムの個数だけ用意する
    for i in range(N)
]

# 目的関数を定義する
objective = sum(v[i] * x[i] for i in range(N))

# 制約条件を定義する
constraint = sum(w[i] * x[i] for i in range(N)) - W <= 0
# 制約条件の名前を指定する
constraint.add_name("重量制限")

# インスタンスを作成する
instance = Instance.from_components(
    # インスタンスに含まれる全ての決定変数を登録する
    decision_variables=x,
    # 目的関数を登録する
    objective=objective,
    # 全ての制約条件を登録する
    constraints=[constraint],
    # 最大化問題であることを指定する
    sense=Instance.MAXIMIZE,
)

ステップ2: OMMX Adapterを使って最適化計算を実行する#

ステップ1.で用意したインスタンスを最適化するには、次のようにOMMX PySCIPOpt Adapterを介して最適化計算を実行します:

from ommx_pyscipopt_adapter import instance_to_model, model_to_solution

# ommx.v1.InstanceオブジェクトからPySCIPOptのModelオブジェクトに変換する
model = instance_to_model(instance)
# PySCIPOptで最適化計算を実行する
model.optimize()
# 計算結果をommx.v1.Solutionオブジェクトに格納して書き出す
solution = model_to_solution(model, instance)

ここで得られた変数 solution は、SCIPによる最適化計算の結果が格納された ommx.v1.Solution オブジェクトになっています。

結果を分析する#

ステップ2. で得られた計算結果から

  • 最適解（アイテムの価値の合計が最も高くなるようなアイテムの選び方）

  • 最適値（最も高いアイテムの価値の合計）

  • 制約条件（重量制限に対するアイテムの重さの合計の余裕）

を確認・分析するためには、ommx.v1.Solution クラスに実装されているプロパティを使用します。

最適解の分析#

decision_variables プロパティは、決定変数のID、種類、名前、値などの情報を含む pandas.DataFrame オブジェクトを返します：

solution.decision_variables
kind lower upper name subscripts description substituted_value value
id
0 binary 0.0 1.0 x [0] <NA> <NA> 1.0
1 binary 0.0 1.0 x [1] <NA> <NA> 0.0
2 binary 0.0 1.0 x [2] <NA> <NA> 0.0
3 binary 0.0 1.0 x [3] <NA> <NA> 1.0
4 binary 0.0 1.0 x [4] <NA> <NA> 0.0
5 binary 0.0 1.0 x [5] <NA> <NA> 0.0

この pandas.DataFrame オブジェクトを使うことで、例えば「アイテムをナップサックに入れるかどうか」という判断をまとめた表を pandas で簡単に作成できます：

import pandas as pd

df = solution.decision_variables
pd.DataFrame.from_dict(
    {
        "アイテムの番号": df.index,
        "ナップサックに入れるか？": df["value"].apply(lambda x: "入れる" if x == 1.0 else "入れない"),
    }
)
アイテムの番号 ナップサックに入れるか？
id
0 0 入れる
1 1 入れない
2 2 入れない
3 3 入れる
4 4 入れない
5 5 入れない

この分析結果から、ナップサックの重量制限を満たしながらアイテムの価値の合計を最大化するためには、0番目と3番目のアイテムを選択すればよいことが分かります。

最適値の分析#

objective プロパティには最適値が格納されています。今回のケースでは、0番目と3番目のアイテムの価値の合計値が格納されているはずです：

import numpy as np
# 期待される値は0番目と3番目のアイテムの価値の合計値である
expected = v[0] + v[3]
assert np.isclose(solution.objective, expected)

制約条件の分析#

constraints プロパティは、制約条件の等号不等号、左辺の値 ("value")、名前などの情報を含む pandas.DataFrame オブジェクトを返します：

solution.constraints
equality value used_ids name subscripts description dual_variable removed_reason
id
0 <=0 -1.0 {0, 1, 2, 3, 4, 5} 重量制限 [] <NA> <NA> <NA>

特に "value" は制約条件にどの程度の余裕があるのかを知るために便利です。今回のケースでは、0番目のアイテム \(w_0\) の重さが 11、3番目のアイテムの重さ \(w_3\) が 35 であり、ナップサックの耐荷重 \(W\) は 47 なので、重量制約

\[ \begin{align*} \sum_{i=0}^{n-1} w_i x_i - W \leq 0 \end{align*} \]

の左辺の値 "value" は -1 となり、重量制限に対して 1 だけ余裕があることがわかります。