(transform-and-solve)= # 問題を変換して解法へ渡す モデルはアプリケーションの要件を表し、ソルバーやサンプラーは候補を探索します。OMMXはその間に、共通の問題表現である **Instance** を置き、モデラーや解法をまたいで変換処理を使えるようにします。同じソルバーを使い続ける場合や、まだ求解せず問題だけを変換したい場合にも、この共通処理を利用できます。 **必要な表現と、許してよい意味の変更を両方選びます。** Backendが読み込める問題になっても、出発点の問題と等価とは限りません。候補の変数値を復元できること、実行可能性を保存すること、最適性を保存することは、それぞれ別の保証です。 ## ソルバーに渡す定式化を選ぶ ある生産ラインは通常運転では毎時100個まで、低速運転では毎時60個まで生産できます。毎時の生産量を $q$、低速運転のときに1、それ以外で0となる変数を $r$ とします。**Indicator制約** を使うと、「$r=1$ のときは $q\leq60$」という条件をそのまま記述できます。PySCIPOpt Adapterはこの線形のIndicator制約をSCIPに直接渡せます。 同じSCIPで通常の線形制約を使う定式化を試すなら、OMMXはこの条件を{meth}`線形不等式 ` $q\leq100-40r$ に変換できます。$r=0$ を代入すると既知の上限100、$r=1$ なら低速運転時の上限60になります。係数40は二つの上限の差です。もし通常運転で100個を超えて生産できるなら、この式は本来許される計画を除いてしまいます。元の問題にIndicator制約を残しておけば、ソルバーへ渡す定式化は後で選べます。 Indicator制約は「どのモードで上限を課すか」を明示し、線形不等式は同じ条件を変数と係数で表します。ここで下がるのは**記述の抽象度**です。上限100が有効なら、どちらの記述でも許される運転モードと生産量の組は同じです。API名の{meth}`~ommx.Instance.lower_special_constraints`にある `lower` は、選んだ種類の特殊制約を、こうして通常制約で表し直すことを指します。 逆に、ソルバーが特殊制約を直接扱えるときは、線形制約に含まれる構造を明示する選択肢もあります。例えば、所定のパターンを満たす制約群は、{meth}`SOS1制約として表せます `。ソルバーはそこから「高々一つの変数だけが非ゼロ」という条件を直接読み取れます。 (adapter-responsibilities)= ## Adapterが守る責務 Adapterは、OMMXの問題とbackendの入力・出力の間で、数学的な意味を対応づける責任を持ちます。OMMXとして求める契約は次のとおりです。 - 受け取れる問題の範囲を明示し、その範囲では条件や目的の意味を保ってbackendへ渡す。扱えない制約を黙って省略してはならない。 - 候補の値をOMMXの変数に対応づけ、実際にbackendへ渡した問題と同じ数学的内容に照らして評価する。 - 候補の有無、終了理由、最適性・実行不能性などの報告を、実際に解いた問題について解釈する。候補が見つからないことから実行不能性を、候補の評価だけから最適性を主張してはならない。 - 元の問題について結論を返すときは、使った変換の対応と保存保証に基づく。保証を確認できない結論まで引き継いではならない。 Backendは探索とその報告を担い、共通のOMMX処理は問題の変換・候補評価と変換の保証を担います。Adapterはそれらを接続し、報告の対象と意味を揃えます。証明書の独立検証は、報告を解釈する責務とは別の処理です。 この契約に対する対応範囲は、機能・Adapterごとに異なります。具体的な入力条件、結果や診断の扱い、利用手順は{doc}`各AdapterのAPI Reference `、Adapterを実装するためのAPI契約は{class}`~ommx.adapter.SolverAdapter`と{class}`~ommx.adapter.SamplerAdapter`を参照してください。 ## 入力条件と、許可する変換を分ける **Adapter** は、Instanceとbackendの入力・出力を接続し、backendの報告を実際に解いた問題に結びつけて解釈します。その入力条件は、変数の種類、式の表現、制約の種類、最大化・最小化の向きなど、直接受け取れる表現を定めます。よく使われる問題の名前だけでは、入力条件を満たすかは判断できません。数学的には同じ式でも、格納する形が異なる場合があります。 OMMXでは、選んだ変換を適用して目標の表現へ近づける処理を **Preparation** と呼びます。変換先は満たしたい条件を、Policyは使ってよい変換を定めます。例えば、線形のIndicator制約を通常の不等式で表し、SOS1制約はそのままソルバーに渡す方針を選べます。Policyを作るだけでは問題は変わらず、目標へ到達した場合に許可したすべての変換が必要だったとも限りません。 表現の検査は{class}`入力クラスのReference `、変換から候補評価までの一連の例は{meth}`Instance.prepare `にあります。Preparationの成功が示すのは、指定した入力条件への適合です。元の問題との数学的な対応は使った変換によって決まり、その後の入力変換やbackendの実行が失敗する場合もあります。 QUBOは、求解で課す制約を持たず、Binary変数の高々二次の多項式を最小化する表現です。変換先の一例であり、OMMXとは別の基礎モデルでも、すべてのsampling backendを指す名前でもありません。QUBOへ準備した後も対象はOMMX Instanceです。一方、係数と定数項だけを取り出すと、保持した制約や変数値を復元する規則は、その数値に付随しません。二つの操作は{meth}`QUBO向けPolicy `と{meth}`係数形式のReference `で説明します。 ## 自分の目的に必要な保証を選ぶ 変換によって役割は異なります。複数の操作をつなぐ前に、アプリケーションに必要な対応を確認します。 | 操作 | アプリケーションが確認すること | |---|---| | 条件を別の式で表す | どの定義域・boundのもとで、同じ要件を表すか | | 整数をBinary変数で符号化する | 必要な値を表せるか、元の値をどう復元するか | | 制約からboundを絞る | 数値的な保証も含めて、その更新を問題の条件から導けるか | | 変数を固定する | 元の問題から必ず定まる値か、条件付きの部分問題を選ぶのか | | 制約を緩和する | 広げた実行可能領域で得た候補が、外した条件も満たす必要があるか | | 制約をpenaltyに置き換える | 何に罰則を付け、定式化と重みが求める結果に十分か | 例えば、Binary変数 $x$ の最小化では最適値は $0$ です。利用者が $x=1$ に固定すると、その部分問題の最適値は $1$ になります。固定値を復元すれば元の問題の実行可能候補を得られますが、元の最適解ではありません。一方、元の制約から必ず定まる値に固定するなら、このような追加の制限をせずに処理を減らせる場合があります。固定できる理由が重要です。操作と実行例は{meth}`部分評価の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の{meth}`固定penalty操作 `も制約の本体を二乗します。そのReferenceで契約と、適用条件を満たす不等式にslack変数を導入して等式へ変換する操作を確認できます。 必要な保証は目的によっても変わります。最適値を保存しても、すべての実行可能候補やsampling分布を保存するとは限りません。対象とする集合について、候補の対応、両方向の実行可能性、目的値、最適性を分けて確認します。数値的な許容誤差も個別操作の契約の一部であり、手元の数候補で結果が一致しただけでは、任意の入力についての証明にはなりません。 ## 解法・設定と、変換できない場合の進み方を選ぶ Adapterの推奨Policyは出発点です。次の判断はアプリケーションに残ります。 - 解法が直接受け取れる表現と、そこへ到達するために必要な変換。 - 固定・緩和・penalty化など、許してよい意味の変更。 - Penalty weight、許容誤差、サンプル数、時間制限などの設定。 - 一つの候補か複数の候補か、実行可能性・終了理由・bound・gap・最適性について何が分かる必要があるか。 Preparationで目標へ到達できなければ、満たせない入力条件と、選んだ操作を調べます。保持した構造をそのまま扱えるbackendを選ぶ、変換に必要な正当なboundを用意する、モデルや変換方針を見直す、といった選択肢があります。緩和を許すことやpenaltyを選ぶことは数学的な判断であり、単に入力を受け付けてもらいたいという理由からは決まりません。失敗の読み方とInstanceに変更が残る範囲は{meth}`PreparationのReference `で説明します。 推奨のPreparationを使う経路と、明示的に選ぶ経路は{mod}`Adapter Reference `、backendごとの契約は{doc}`Adapterの一覧 `から参照できます。ソルバー名と問題クラスは同じものではありません。例えばOpenJij SAは二次より高次のBinary多項式も扱えるため、実際の入力条件を出発点にします。 実行後は、対応する問題と、そこに保持した評価用の情報を使って候補を解釈します。求解の呼び出しが成功したことや、backendの目的値がよいことだけでは、この確認の代わりになりません。候補が返らない場合にも、終了報告を実際に解いた問題について読み、元の問題へ結論を引き継ぐには変換の対応と保存保証を使います。[候補を評価して結果を判断する](./evaluate_and_interpret.md)では、復元値・報告目的値・実行可能性・最適性を分けて比較し、候補がない場合の結論や、結果を元の要求へ戻す経路も説明します。 (shared-analysis-and-transformations)= ## 解析・変換・保証を組み合わせる ソルバーへそのまま渡せる問題でも、前処理（Presolve）によって縮約できる場合があります。その選択・反復は、入力条件へ適合させるPreparationとは別の目的を持ちます。 OMMXは、解析と変換を共通の問題表現に対して追加し、組み合わせて使う体系です。各処理の責務を次のように分けます。 - 解析は、問題を書き換えずに性質や構造を調べ、その結果が依存する条件を明らかにする。 - 変換は、解析結果と適用条件に基づいて問題を書き換え、元の問題との対応と保存する保証を明らかにする。 - 解析と変換を組み合わせる処理は、変更後も解析結果を再利用できるかを判断し、必要な保証に沿って変換をつなぐ。 例えば、ある制約から得たboundを別の変換が使う場合、その制約を外した後も同じboundを根拠にできるとは限りません。解析結果の依存条件を確認し、保持・更新・再検査のどれが必要かを判断する責任は、これらを組み合わせる処理にあります。 新しい解析や変換を追加するときも、この分担に沿って適用条件と保証を定めます。利用者は用途に必要な保証を選び、その保証を満たす組合せを共通の処理として再利用できるようにする設計です。宣言の種類や解法が増えても、個々の変換から元の変数値の復元や結果解釈へつなぐ契約は共通です。 利用できる操作や組合せ、保証の範囲は機能ごとに異なります。具体的な適用条件と保証は、{meth}`Preparation `や{meth}`bound更新 `など、各操作のAPI Referenceで確認してください。