背景
この記事はJij Advent Calendar 2024 5日目の記事です。
Jijでは、数理最適化の相互運用性を向上させるためのソフトウェアである「OMMX（Open Mathematical prograMming eXchange・読み方：オミキス）」をリリースしています。
この記事では、OMMXのユースケースの一つである、数理最適化においてよく用いられるモデリングツールの相互変換する処理をデモンストレーションします。
数理モデリングツール、およびその課題
数理最適化分野において、近年無償で使える数理最適化ソルバ、およびモデラーが増えてきています。代表的なモデリングツールとして例えば以下があります。
その一方、モデリングツールによって対応しているソルバーが限られているため、しばしば使いたいソルバーに応じてモデリングツールの書き換えを行わなければならないケースが生じます。例えば、Python-MIPでは対応しているソルバーがCBC, Gurobiしかないため、SCIPを使いたいとなった時にはわざわざ数式をPySCIPOptを用いて書き換えなければならないといった問題が発生します。
今回は、Python-MIPによって作られた数理モデルを、OMMXを用いてPySCIPOptの形式に変換する処理を通してこの問題が解決されることを見ていこうと思います。
デモンストレーション
手元の環境で、まず以下をインストールしておきます。
OMMXでは数理モデルの相互変換を行うため、以下にあるようなadapterを各モデリングツールごとに用います。
pip install mip pyscipopt ommx ommx-python-mip-adapter ommx-pyscipopt-adapter
まず、Python-MIPを用いて典型的なナップザック問題を解いてみたいと思います。
この問題は与えられた重さを超えない範囲で、なるべく価値を最大にするにはどのようなアイテムを選択すれば良いかを決定する問題です。
from mip import Model, xsum, maximize, BINARY
# アイテムの数
n_items = 5
# アイテムの重さ
weights = [2, 3, 4, 5, 9]
# アイテムの価値
values = [3, 4, 8, 8, 10]
# ナップザックに入る重さ上限
max_weight = 10
# Create a MIP model
model = Model(sense=maximize)
# Create decision variables for each item (0 or 1, binary)
x = [model.add_var(var_type=BINARY) for i in range(n_items)]
# Add weight constraint: total weight of selected items must be less than or equal to max_weight
model += xsum(weights[i] * x[i] for i in range(n_items)) <= max_weight
# Define the objective: maximize the total value of selected items
model.objective = maximize(xsum(values[i] * x[i] for i in range(n_items)))
# Optimize the model
model.optimize()
# Print the selected items
selected_items = [i for i in range(n_items) if x[i].x >= 0.99]
print(f"Selected items: {selected_items}")
print(f"Total value: {model.objective_value}")
結果は以下のようになります。
Selected items: [2, 3]
Total value: 16.0
この問題をSCIPを使うために、Python-MIPでなく、PySCIPOptを使って解きたくなったとしましょう。通常であれば一からモデルを書き直さないといけないので大変です。
そこで、OMMXを使うと以下のように書けます。
from ommx_pyscipopt_adapter import adapter as pyscipopt_adapter
import ommx_python_mip_adapter as pythonmip_adapter
# Python-MIPからOMMX instanceに変換
ommx_instance = pythonmip_adapter.model_to_instance(model)
# OMMX instanceからPySCIPOptのモデラー形式へ変換
model = pyscipopt_adapter.instance_to_model(ommx_instance)
これだけの処理で、PySCIPOptの形式に変換ができます。
あとは最適化を行い、解を取り出します。
# 最適化
model.optimize()
# 解の変換
solution = pyscipopt_adapter.model_to_solution(model, ommx_instance)
# 解の抽出
selected_items = sorted([k for k,v in solution.state.entries.items() if v >= 0.99])
print(f"Selected items: {selected_items}")
print(f"Total value: {solution.objective}")
結果は以下のようになり、Python-MIPと全く同じ答えが出てきます。
Selected items: [2, 3]
Total value: 16.0
まとめ
今回は具体例を通して、OMMXによってモデリングツール間の相互変換のデモンストレーションを行いました。
OMMXのアダプターに対応したモデリングツールが増えてくることで、任意のソルバーを任意のモデリングツールから呼び出せるようになっていくと思います。
また、Tutorialページには、OMMXの詳細な使い方に加え、アダプターの作り方も紹介しているのでぜひご参照ください。
Jijでは各ポジションを絶賛採用中です！
ご興味ございましたらカジュアル面談からでもぜひ！ご連絡お待ちしております。
数理最適化エンジニア（採用情報）
量子コンピューティングソフトウェアエンジニア（採用情報）
Rustエンジニア[アルゴリズムエンジニア]（採用情報）
研究チームPMO（採用情報）
オープンポジション等その他の採用情報はこちら
Discussion