問題を変換して解法へ渡す

モデルはアプリケーションの要件を表し、ソルバーやサンプラーは候補を探索します。OMMXはその間に、共通の問題表現である Instance を置き、モデラーや解法をまたいで変換処理を使えるようにします。同じソルバーを使い続ける場合や、まだ求解せず問題だけを変換したい場合にも、この共通処理を利用できます。

必要な表現と、許してよい意味の変更を両方選びます。 Backendが読み込める問題になっても、出発点の問題と等価とは限りません。候補の変数値を復元できること、実行可能性を保存すること、最適性を保存することは、それぞれ別の保証です。

ソルバーに渡す定式化を選ぶ

ある生産ラインは通常運転では毎時100個まで、低速運転では毎時60個まで生産できます。毎時の生産量を \(q\)、低速運転のときに1、それ以外で0となる変数を \(r\) とします。Indicator制約 を使うと、「\(r=1\) のときは \(q\leq60\)」という条件をそのまま記述できます。PySCIPOpt Adapterはこの線形のIndicator制約をSCIPに直接渡せます。

同じSCIPで通常の線形制約を使う定式化を試すなら、OMMXはこの条件を線形不等式 \(q\leq100-40r\) に変換できます。\(r=0\) を代入すると既知の上限100、\(r=1\) なら低速運転時の上限60になります。係数40は二つの上限の差です。もし通常運転で100個を超えて生産できるなら、この式は本来許される計画を除いてしまいます。元の問題にIndicator制約を残しておけば、ソルバーへ渡す定式化は後で選べます。

Indicator制約は「どのモードで上限を課すか」を明示し、線形不等式は同じ条件を変数と係数で表します。ここで下がるのは記述の抽象度です。上限100が有効なら、どちらの記述でも許される運転モードと生産量の組は同じです。API名のlower_special_constraints()にある lower は、選んだ種類の特殊制約を、こうして通常制約で表し直すことを指します。

逆に、ソルバーが特殊制約を直接扱えるときは、線形制約に含まれる構造を明示する選択肢もあります。例えば、所定のパターンを満たす制約群は、SOS1制約として表せます。ソルバーはそこから「高々一つの変数だけが非ゼロ」という条件を直接読み取れます。

入力条件と、許可する変換を分ける

Adapter は、Instanceとbackendの入力・出力を接続します。その入力条件は、変数の種類、式の表現、制約の種類、最大化・最小化の向きなど、直接受け取れる表現を定めます。よく使われる問題の名前だけでは、入力条件を満たすかは判断できません。数学的には同じ式でも、格納する形が異なる場合があります。

OMMXでは、選んだ変換を適用して目標の表現へ近づける処理を Preparation と呼びます。変換先は満たしたい条件を、Policyは使ってよい変換を定めます。例えば、線形のIndicator制約を通常の不等式で表し、SOS1制約はそのままソルバーに渡す方針を選べます。Policyを作るだけでは問題は変わらず、目標へ到達した場合に許可したすべての変換が必要だったとも限りません。

表現の検査は入力クラスのReference、変換から候補評価までの一連の例はInstance.prepareにあります。Preparationの成功が示すのは、指定した入力条件への適合です。元の問題との数学的な対応は使った変換によって決まり、その後の入力変換やbackendの実行が失敗する場合もあります。

QUBOは、求解で課す制約を持たず、Binary変数の高々二次の多項式を最小化する表現です。変換先の一例であり、OMMXとは別の基礎モデルでも、すべてのsampling backendを指す名前でもありません。QUBOへ準備した後も対象はOMMX Instanceです。一方、係数と定数項だけを取り出すと、保持した制約や変数値を復元する規則は、その数値に付随しません。二つの操作はQUBO向けPolicyと係数形式のReferenceで説明します。

自分の目的に必要な保証を選ぶ

変換によって役割は異なります。複数の操作をつなぐ前に、アプリケーションに必要な対応を確認します。

操作	アプリケーションが確認すること
条件を別の式で表す	どの定義域・boundのもとで、同じ要件を表すか
整数をBinary変数で符号化する	必要な値を表せるか、元の値をどう復元するか
制約からboundを絞る	数値的な保証も含めて、その更新を問題の条件から導けるか
変数を固定する	元の問題から必ず定まる値か、条件付きの部分問題を選ぶのか
制約を緩和する	広げた実行可能領域で得た候補が、外した条件も満たす必要があるか
制約をpenaltyに置き換える	何に罰則を付け、定式化と重みが求める結果に十分か

例えば、Binary変数 \(x\) の最小化では最適値は \(0\) です。利用者が \(x=1\) に固定すると、その部分問題の最適値は \(1\) になります。固定値を復元すれば元の問題の実行可能候補を得られますが、元の最適解ではありません。一方、元の制約から必ず定まる値に固定するなら、このような追加の制限をせずに処理を減らせる場合があります。固定できる理由が重要です。操作と実行例は部分評価のReferenceが扱います。

Penaltyでは、重みだけでなく式の選び方も重要です。\(x\in\{0,1\}\)、\(x-1\leq0\) のもとで \(x\) を最小化する場合、どちらの値も実行可能です。不等式の本体を二乗して重み \(2\) を加えると、目的関数は \(x+2(x-1)^2\) になります。

\(x\)	元の目的値	二乗した本体	Penaltyを加えた目的値
0	0	1	2
1	1	0	1

二つの実行可能候補の順序が逆転しました。これは、どちらにも罰則を付けない違反量の二乗 \(\max(0,x-1)^2\) とは別の操作です。そのため、重みを増やすだけで元の最適解を得られるとは保証できません。OMMXの固定penalty操作も制約の本体を二乗します。そのReferenceで契約と、適用条件を満たす不等式にslack変数を導入して等式へ変換する操作を確認できます。

必要な保証は目的によっても変わります。最適値を保存しても、すべての実行可能候補やsampling分布を保存するとは限りません。対象とする集合について、候補の対応、両方向の実行可能性、目的値、最適性を分けて確認します。数値的な許容誤差も個別操作の契約の一部であり、手元の数候補で結果が一致しただけでは、任意の入力についての証明にはなりません。

解法・設定と、変換できない場合の進み方を選ぶ

Adapterの推奨Policyは出発点です。次の判断はアプリケーションに残ります。

• 解法が直接受け取れる表現と、そこへ到達するために必要な変換。

• 固定・緩和・penalty化など、許してよい意味の変更。

• Penalty weight、許容誤差、サンプル数、時間制限などの設定。

• 一つの候補か複数の候補か、実行可能性・終了理由・bound・gap・最適性について何が分かる必要があるか。

Preparationで目標へ到達できなければ、満たせない入力条件と、選んだ操作を調べます。保持した構造をそのまま扱えるbackendを選ぶ、変換に必要な正当なboundを用意する、モデルや変換方針を見直す、といった選択肢があります。緩和を許すことやpenaltyを選ぶことは数学的な判断であり、単に入力を受け付けてもらいたいという理由からは決まりません。失敗の読み方とInstanceに変更が残る範囲はPreparationのReferenceで説明します。

推奨のPreparationを使う経路と、明示的に選ぶ経路はAdapter Reference、backendごとの契約はAdapterの一覧から参照できます。ソルバー名と問題クラスは同じものではありません。例えばOpenJij SAは二次より高次のBinary多項式も扱えるため、実際の入力条件を出発点にします。

実行後は、対応する問題と、そこに保持した評価用の情報を使って候補を解釈します。求解の呼び出しが成功したことや、backendの目的値がよいことだけでは、この確認の代わりになりません。候補を評価して結果を判断するでは、復元値・報告目的値・実行可能性・最適性を分けて結果を比較します。

共通処理の上に技術を蓄積する

現在のOMMXは、個別の変換操作、それらを選ぶPolicy、候補評価を提供しています。bound更新もあり、例えば制約 \(x\leq3\) から、宣言時の上限 \(10\) を絞れます。この操作は一回の同時更新であり、収束するまで繰り返したり、実行不可能な問題をすべて検出したりする完全なpresolverではありません。

開発では、個別の変換技術に加え、いつ選択・反復するかという知識を蓄積していくことを目指しています。共通表現に対して操作を実装することで、新しいモデラーや解法もその処理を利用できます。現在は対応する操作を選び、それぞれの保証を確認して使います。一般的な自動選択・反復は今後の開発方針です。