OpenJij Adapterで小さな問題をサンプリングする

OpenJij Adapterで小さな問題をサンプリングする#

OpenJijの焼きなまし法で候補を集め、OMMXの目的値と実行可能性で結果を読みます。制約のペナルティ重みを自分で決める場合は、Policyに設定してInstanceを準備し、sample_without_preparation()へ渡します。

Pythonと変数・目的関数・制約の基礎が分かれば、このページだけで実行できます。ほかのTutorialの実行状態は使いません。インストール手順の1・2でSDKの3.0.0b7を用意し、OpenJij Adapterを追加してください。その環境をNotebookのカーネルに選びます。ほかのAdapterや外部データは必要ありません。

1. ちょうど一つを選ぶ問題を作る#

二つの選択肢から一つだけ選び、得点を最大化します。Instanceは目的関数・変数・制約をまとめた問題です。new_binary()で0か1の値を取る変数を作り、OneHotConstraintで「ちょうど一つが1」という条件を加えます。

from ommx import FixedPenaltyPreparation, Instance, OneHotConstraint
from ommx_openjij_adapter import OMMXOpenJijSAAdapter

instance = Instance.maximize()
x = [instance.new_binary("x", subscripts=[i]) for i in range(2)]
instance.objective = 3 * x[0] + 2 * x[1]
instance.add_one_hot_constraint(OneHotConstraint(variables=x))

target = OMMXOpenJijSAAdapter.INPUT_CLASS
target.contains(instance)

False

INPUT_CLASSは、このAdapterが直接受け取る問題の条件です。OpenJij SA Adapterの場合、使われる変数がBinary、目的関数が多項式の最小化、現在課す制約がないことを要求します。多項式の次数は2次に限らず、3次以上も扱えます。

このInstanceは最大化でOneHot制約もあるので、contains()はFalseです。そこで、OpenJijで探索できる表現に変えます。

2. 重みを決めてPreparationする#

Preparationは、許可する変換を表すPolicyに従い、目標のクラスに入るようにInstanceを変換する操作です。ここではAdapterの推奨Policyを取り、制約違反を目的関数で不利にするペナルティの重みを追加します。OpenJij Adapterの推奨Policyは、この重みを利用者に任せています。

policy = OMMXOpenJijSAAdapter.recommended_preparation_policy()
policy.fixed_penalty = (
    FixedPenaltyPreparation.uniform_penalty_method_with_fixed_weight(weight=4.0)
)
instance.prepare(target, policy)

target.contains(instance)

True

この例ではOneHotを等式にし、最大化を最小化へ変え、等式の違反に重み4のペナルティを加えます。例えば両方を選ぶと得点は5ですが、重み4のペナルティがかかるため、得点3の選択肢を一つ選ぶ方が有利になります。重み4はこの小さな問題用の設定であり、ほかの問題で十分とは限りません。

prepare()は同じInstanceを直接変更します。Trueは入力の表現条件に入ったことを示しますが、返る候補が元の制約を満たすことや、元の問題の最適解を得られることの保証ではありません。

3. 準備したInstanceから候補を集める#

sample_without_preparation()は追加のPreparationを行わず、今準備したInstanceを使います。num_readsは試行回数、seedは乱数の設定です。

sample_set = OMMXOpenJijSAAdapter.sample_without_preparation(
    instance, num_reads=10, seed=42
)
sample_set.summary
objective feasible
sample_id
5 3.0 True
4 3.0 True
7 3.0 True
6 3.0 True
1 3.0 True
0 3.0 True
3 3.0 True
2 3.0 True
9 3.0 True
8 3.0 True

返るSampleSetは、得られた候補をOMMXの問題で評価した結果です。表の各行はsample_idで識別される候補で、同じ変数値の候補が複数行に現れることもあります。実行可能な候補を先に、その中では報告目的値の良い順に表示します。候補の内訳は実行環境によって変わることがあります。

  • objective：この例では、ペナルティを加える前の得点3*x[0] + 2*x[1]です。元の最大化の向きで比較します。

  • feasible：この例では、変換後に検査用として残したOneHotも含めて判定します。OpenJijへ制約なしで渡したことと、候補が元の条件を満たすことは別です。

OpenJijが探索に使うenergyと、この報告目的値は別です。最大化から最小化への変換、ペナルティ、係数に含めない定数項があるため、同じ値とは限りません。このsummaryはrawなenergyを表示する表ではありません。

4. 得られた候補の中から選ぶ#

best_feasibleは、得られた実行可能な候補の中で報告目的値が最良のものをSolutionとして返します。変数のnameとsubscriptsはモデルで付けた名前と添字、valueはその候補での値です。

solution = sample_set.best_feasible
print(f"{solution.objective=}, {solution.feasible=}")
solution.decision_variables_df()[["name", "subscripts", "value"]]

solution.objective=3.0, solution.feasible=True
name subscripts value
id
0 x [0] 1.0
1 x [1] 0.0

実行可能な候補が一つもなければbest_feasibleはエラーになります。その場合は表のfeasibleを確認し、重みや試行回数などの設定を見直します。重みを変える場合はモデルを作るセルから実行し直してください。 変換済みのInstanceはすでに入力条件を満たすため、Policyを変えてprepare()を呼ぶだけでは重みは置き換わりません。焼きなまし法で得た候補からの選択であり、大域最適性の証明ではありません。

関連する説明と応用#

通常のsample()は、その呼び出しで新しく取得した推奨Policyを使います。ここで編集したpolicyを渡すAPIではないため、独自の重みを使うこの経路ではprepare()とsample_without_preparation()を組にします。

目次