インスタンスの生成

インスタンスの生成#

前節までで数理モデルの一通りの定式化方法を学んできました。 本節では、いよいよ数理モデルを OMMX インスタンスへとコンパイルし、OMMX Adapter を経由して問題を解くまでの流れを説明します。

記号的に記述された数理モデルに「インスタンスデータ」を入力すると、ソルバーへの入力データ（＝インスタンス）が生成される

図 6 インスタンスデータ作成までの流れ#

図6 にモデルからインスタンスを得るまでの流れを再掲しました。 これに沿って、インスタンスデータの用意とコンパイルの順に説明します。

以下では、次のシナジーボーナスつきのナップサック問題を例に説明します。

import jijmodeling as jm


@jm.Problem.define("Knapsack with Synergy", sense=jm.ProblemSense.MAXIMIZE)
def problem(problem: jm.DecoratedProblem):
    N = problem.Natural()
    W = problem.Float(description="Weight limit of the problem")
    v = problem.Float(shape=(N,), description="Values of the items")
    w = problem.Float(shape=(N,), description="Weights of the items")
    s = problem.PartialDict(
        dtype=float, dict_keys=(N, N), description="Synergy bonus between items"
    )
    x = problem.BinaryVar(shape=(N,), description="Item selection variables")

    problem += jm.sum(v[i] * x[i] for i in N)
    problem += jm.sum(s[i, j] * x[i] * x[j] for i, j in s.keys())

    problem += problem.Constraint("weight", jm.sum(w[i] * x[i] for i in N) <= W)


problem
\[\begin{split}\begin{array}{rl} \text{Problem}\colon &\text{Knapsack with Synergy}\\\displaystyle \max &\displaystyle \sum _{i=0}^{N-1}{{v}_{i}\cdot {x}_{i}}+\sum _{\left\langle i,j\right\rangle \in \mathop{\mathtt{keys}}\left(s\right)}{{s}_{i,j}\cdot {x}_{i}\cdot {x}_{j}}\\&\\\text{s.t.}&\\&\begin{aligned} \text{weight}&\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}\\&&&\text{Item selection variables}\\\end{alignedat}\\&\\&\text{Placeholders:}\\&\qquad \begin{alignedat}{2}N&\in \mathbb{N}&\quad &\text{A scalar placeholder in }\mathbb{N}\\s&\in \mathop{\mathrm{PartialDict}}\left[N\times N;\mathbb{R}\right]&\quad &\text{A partial dictionary of placeholders with keys }N\times N\text{, values in }\mathbb{R}\\&&&\text{Synergy bonus between items}\\&&&\\v&\in \mathop{\mathrm{Array}}\left[N;\mathbb{R}\right]&\quad &1\text{-dimensional array of placeholders with elements in }\mathbb{R}\\&&&\text{Values of the items}\\&&&\\W&\in \mathbb{R}&\quad &\text{A scalar placeholder in }\mathbb{R}\\&&&\text{Weight limit of the problem}\\&&&\\w&\in \mathop{\mathrm{Array}}\left[N;\mathbb{R}\right]&\quad &1\text{-dimensional array of placeholders with elements in }\mathbb{R}\\&&&\text{Weights of the items}\\\end{alignedat}\end{array} \end{split}\]

インスタンスデータの用意#

各プレースホルダーとカテゴリーラベルに対応するデータを用意する必要があります。 現在各データの仕様は以下のようになります：

プレースホルダーの種類

対応する Python のデータ型

単体のプレースホルダー

値の型に一致する Python の数値やタプル

プレースホルダーの配列

値の型に一致する Python の（多重）リストまたはNumPy 配列

プレースホルダーの辞書

値の型に一致する Python の辞書

カテゴリーラベル

重複のない数値または文字列からなる Python のリスト

また、配列のシェイプや辞書の全域性に関する制約を満たすようにデータを与える必要があります。 現時点においては、辞書のデータを配列として与えることはできないので注意してください。

インスタンスデータは、これらをそれぞれの変数名に対応させた Python の辞書として用意します。 それでは、problem に対するインスタンスデータを用意してみましょう。

import random
import numpy as np

random.seed(42)
N_data = 10
W_data = random.randint(10, 75)
v_data = [random.uniform(1, 20) for _ in range(N_data)]
w_data = np.array([random.uniform(1, 15) for _ in range(N_data)])  # Numpy 配列も可
s_data = {(1, 2): 5.0, (1, 4): 3.0, (2, 9): 5.0, (3, 5): 10}

instance_data = {"N": N_data, "W": W_data, "v": v_data, "w": w_data, "s": s_data}

インスタンスデータのランダム生成

正式リリースまでの間に、インスタンスデータをランダム生成する機能が追加される予定です。

インスタンスへのコンパイル#

モデルとインスタンスデータが用意できたら、いよいよ OMMX インスタンスへのコンパイルを行います。 一番簡単な方法は、Problem.eval() メソッドを使う方法です：

instance1 = problem.eval(instance_data)
instance1.constraints_df
equality type used_ids name subscripts description
id
0 <=0 Linear {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} weight [] <NA> 
instance1.decision_variables_df
kind lower upper name subscripts description substituted_value parameters.subscripts
id
0 Binary 0.0 1.0 x [0] Item selection variables <NA> [0]
1 Binary 0.0 1.0 x [1] Item selection variables <NA> [1]
2 Binary 0.0 1.0 x [2] Item selection variables <NA> [2]
3 Binary 0.0 1.0 x [3] Item selection variables <NA> [3]
4 Binary 0.0 1.0 x [4] Item selection variables <NA> [4]
5 Binary 0.0 1.0 x [5] Item selection variables <NA> [5]
6 Binary 0.0 1.0 x [6] Item selection variables <NA> [6]
7 Binary 0.0 1.0 x [7] Item selection variables <NA> [7]
8 Binary 0.0 1.0 x [8] Item selection variables <NA> [8]
9 Binary 0.0 1.0 x [9] Item selection variables <NA> [9] 
instance1.objective

Function(5*x1*x2 + 3*x1*x4 + 5*x2*x9 + 10*x3*x5 + 1.4752043492306717*x0 + 6.225557049013266*x1 + 5.241004024827633*x2 + 14.992953069116236*x3 + 13.857290261035315*x4 + 17.951411786392065*x5 + 2.651837819958907*x6 + 9.016514574020139*x7 + 1.5661471693233366*x8 + 5.154121521268464*x9)

これは実際には Compiler.from_problem() メソッドと Compiler.eval_problem() メソッドを呼び出しており、以下のように書くのと同値です：

compiler = jm.Compiler.from_problem(problem, instance_data)
instance2 = compiler.eval_problem(problem)

assert instance1.objective.almost_equal(instance2.objective)
assert len(instance1.constraints) == 1
assert len(instance2.constraints) == 1
assert instance2.constraints[0].equality == instance1.constraints[0].equality
assert instance2.constraints[0].function == instance1.constraints[0].function

何故問題を二回渡す必要があるのか？

上の例では、from_problem() と eval_problem() の両方に problem 問題を渡しています。 これは一見無駄に見えますが、それぞれ以下のように別々の役割を持っています：

from_problem() の第 1 引数の Problem オブジェクト

Compiler が評価時に用いる決定変数の型の情報などを取得するのに使われています。 こうした情報の束を JijModeling では Namespace と呼びます。 実際には Problem が保持している Namespace オブジェクトを namespace() プロパティにより取得し、それを使って Compiler の構築子 を呼ぶ形になっています。

eval_problem() の第 1 引数の Problem オブジェクト

インスタンスにコンパイルしたい Problem オブジェクトを指定します。 Compiler オブジェクトは特定の Problem に限定されたものではなく、決定変数やプレースホルダーが一致しているような複数の Problem オブジェクトに対して使い回すことができるため、このような形になっています。

単純に Problem をインスタンスにコンパイルするだけであれば Problem.eval() メソッドを使うのが手軽ですが、 Compiler オブジェクトは get_constraint_id_by_name() や get_decision_variable_by_name() メソッドなどを使ってモデルの制約条件や決定変数の OMMX 側での ID の情報を取得することもできます。

また、Compiler はインスタンスへのコンパイル以外にも、以下のように eval_function() メソッドを個別のスカラー関数式を OMMX の Function オブジェクトに評価したり、eval_constraint() により個別の制約条件を（Problem に登録せずに）OMMX の Constraint オブジェクトに評価したりすることもできます。 以下は problem 問題の決定変数を使った関数式を評価している例です：

x_ = problem.decision_vars["x"]
compiler.eval_function(jm.sum(x_.roll(1) * x_) - 1)

Function(x0*x1 + x0*x9 + x1*x2 + x2*x3 + x3*x4 + x4*x5 + x5*x6 + x6*x7 + x7*x8 + x8*x9 - 1)

eval_function や eval_constraint メソッドはデバッグに使える他、コンパイル後の ommx.v1.Instance を変形する用途などに利用できます。

また、一度作成した Compiler は、プレースホルダーと決定変数を共有する複数のモデルに対して使い回すことができ、決定変数や制約条件の ID の対応関係も保存されます。 この機能は、同じパラメーターを持ちつつ制約条件や目的関数を変化させた複数のモデルを同時にコンパイルし、結果を比較する用途などに便利です。

OMMX SDK を用いた問題の変形

OMMX SDK にはコンパイル後の Instance オブジェクトを変形するための様々な機能が用意されています。 たとえば、決定変数の値を固定したり、ommx.v1.Instance.to_qubo() メソッドなどを使ってペナルティ法を用いて制約つき問題を制約なしの QUBO 問題へと変換したり、といったことが可能です。 こういった機能の詳細については OMMX の公式ドキュメントを御覧ください。

eval や eval_problem のオプション#

Problem.eval() や Compiler.eval_problem() メソッドは、どちらも以下の共通のキーワード限定引数を渡すことで挙動を制御できるようになっています：

prune_unused_vars: bool

True に設定すると、デフォルトでは目的関数や制約条件に現れる決定変数のみが Instance に登録されるようになります。 デフォルト値は False であり、モデル中に現れない決定変数も登録されるようになっています。

constraint_detection: Optional[ConstraintDetectionConfig | bool] = None

JijModeling には制約条件の構造を検知して OMMX インスタンスに反映させることで、OMMX Adapter がより効率的にソルバーを呼び出せるようになっています。 この検出機能はデフォルトで有効になっていますが、現状最大数秒程度のコンパイル時のオーバーヘッドがかかります。 このオプションに ConstraintDetectionConfig オブジェクトを渡してやることで、検出する制約条件の種類を指定したり、振る舞いに関するパラメーターを調整したりすることができます。 また、False を渡すことで検出機能じたいを無効化できます。

インスタンスの求解#

OMMX インスタンスが得られたら、あとは OMMX Adapter を使ってソルバーで解くだけです。 以下では、SCIP アダプターを使って解く例を示します：

from ommx_pyscipopt_adapter import OMMXPySCIPOptAdapter

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

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

solution.decision_variables_df[["name", "subscripts", "value"]]

目的関数の最適値: 60.97707309867254
name subscripts value
id
0 x [0] 0.000000e+00
1 x [1] 1.000000e+00
2 x [2] 1.000000e+00
3 x [3] 1.000000e+00
4 x [4] 4.440892e-16
5 x [5] 1.000000e+00
6 x [6] 0.000000e+00
7 x [7] 0.000000e+00
8 x [8] 1.000000e+00
9 x [9] 0.000000e+00

OMMX Adapter の詳しい利用方法については、OMMX のユーザーガイドを参照してください。 また、SCIP だけでなくさまざまなソルバーに対する OMMX Adapterが用意されており、同様の手順で利用することができます。

OMMX SDK の名寄せ機能は決定変数や制約の辞書に未対応

OMMX SDK の Solution オブジェクトには、決定変数や制約の値を名前から名寄せする extract_decision_variables() や extract_constraints() メソッドが用意されています。 これらは現時点で文字列を添え字とする決定変数や制約には対応していないため、辞書やカテゴリーラベルを使ったモデルの Solution に対して呼び出すとエラーになってしまいます。 こうした場合は、JijModeling の Compiler.get_constraint_id_by_name() や Compiler.get_decision_variable_by_name() メソッドを呼び出してコンパイラから ID との対応を取得し、その ID を ommx.v1.Solution.get_constraint_value() や ommx.v1.Solution.get_decision_variable_by_id() メソッドに渡して値を取得するようにしてください。

目次