Instance Preparation と PreparationPolicy

Instance Preparation と PreparationPolicy#

Instance Preparationは、Instanceに既存の変換操作を適用し、targetのInstanceClassに属する表現へ近づける仕組みです。変換先を表すclass、許可する操作を選ぶPolicy、実際に変換するInstance.prepare()を分けて考えます。

要素

役割

targetのInstanceClass

満たしたい表現の条件

PreparationPolicy

使ってよい変換操作と設定の選択

Instance.prepare

そのInstanceへ変換を適用し、target membershipを検査する

classの意味はInstanceClassとAdapterの入力条件、一連の操作例はInstanceを変換するHow-toを参照してください。後半では、この共通の仕組みをAdapterに適用します。

Policyを作ることと、変換することは別#

PreparationPolicyは、変換操作の選択を保持する値です。Policyを作成・編集しただけではInstanceは変わりません。

例えば「ちょうど一つを選ぶ」というOneHotの条件を、通常の等式へ置き換えるPolicyは次のように作ります。特殊制約を通常の制約へ書き換える操作をloweringと呼びます。ここでは変換するinstanceと、変換先のtargetが用意されているとします。

from ommx import (
    PreparationPolicy, SpecialConstraintKind, SpecialConstraintPreparation,
)

policy = PreparationPolicy(
    special_constraints=SpecialConstraintPreparation.lower_special_constraints(
        kinds={SpecialConstraintKind.OneHot}
    )
)

instance.prepare(target, policy)
assert target.contains(instance)

prepare()は呼び出したInstanceをin-placeに変更します。変換前のInstance自体を後でも使う必要がある場合だけ、事前にcopyを作ります。候補の評価結果を比較するだけなら、変換前に評価結果を保存しておけば十分です。Instanceとtargetの構築も含む実行例は変換How-toにあります。

Targetに入った時点で止まる#

PreparationはPolicyのすべての操作を必ず最後まで実行する仕組みではありません。実行前と、選択した変換段階（phase）の完了後にInstance全体のmembershipを調べ、targetに入った時点で停止します。最初からmemberならInstanceは変更されません。

成功時に成立する条件は、指定したtargetへのmembershipです。

assert target.contains(instance)

この条件だけでは、元の問題との数学的な等価性や最適性は保証されません。変換元の条件、使う操作、その操作が保存するものを個別に確認します。

変換後の候補は、そのInstanceが保持する変数・制約・目的の情報を使って解釈します。Instanceの変数の役割と変換後の問題とRemoved constraintsを参照してください。

PreparationPolicy が選ぶ phase#

PreparationPolicy の各 field は optional で、未指定の phase は実行されません。デフォルトではすべての phase が無効です。各 field は、Instanceの変換操作のうちどれを呼ぶかを選択します。各操作の入力条件やerrorは、対応するメソッドのAPI Referenceを参照してください。

prepare() は、選択された phase を高々1回ずつ次の固定順序で適用します。

順序

Policy field

役割

1

special_constraints

選択した active な特殊制約を通常制約へ lowering

2

objective

active objectiveを指定したsenseへ変換

3

integer_slack

active な通常不等式への Integer slack 導入

4

integer_encoding

使用中の Integer 変数を Binary 変数で encoding

5

fixed_penalty

active な通常制約を固定 weight の penalty として目的関数へ移動

6

binary_power_reduction

activeなBinary変数の冪を縮約

各fieldに設定する型とfactoryの全引数は、SpecialConstraintPreparation、ObjectivePreparation、IntegerSlackPreparation、FixedPenaltyPreparation、IntegerEncodingPreparation、BinaryPowerPreparationのAPI Referenceを参照してください。特殊制約loweringの数式と成立条件も、各変換メソッドのAPI Referenceが所有します。特殊制約そのものの意味は特殊制約型を参照してください。

固定penaltyの大きさのように、問題のscaleや求める解の性質に依存する選択があります。どの変換を許し、どの値を使うかはapplicationが判断します。

Adapterへの適用：推奨Policyと自動Preparation#

Adapterは、直接受け取れるInstanceの集合をINPUT_CLASSとして宣言します。このInstanceClassをtargetとして使うのがAdapter向けのPreparationです。

通常の求解・samplingには、まずsolve()またはsample()を使えます。標準のeasy APIは、入力のcopyを作り、Adapterの推奨Policyでprepareしてから厳格なmethodを呼びます。

# 呼び出し元のinstanceは変更されない。内部のcopyだけがPreparationされる。
result = Adapter.solve(instance)

recommended_preparation_policy()は、Adapterのexact inputへ到達する際に一般的に有用なPolicyを返します。この呼び出しは次の性質を持ちます。

  • 呼び出すたびに、呼び出し側が編集できる新しいPolicyを返す

  • 特定のInstanceを参照または変更せず、Preparationもしない

  • target membershipへの到達を保証しない

INPUT_CLASSと推奨Policyは独立した値です。固定penaltyの大きさなど、Adapterが安全な値を推奨できないapplication固有の選択がある場合は、自分でPolicyを編集し、明示的な経路を使います。

input_class = Adapter.INPUT_CLASS
policy = Adapter.recommended_preparation_policy()

# 必要なら、application固有の判断でpolicyを編集する。
instance.prepare(input_class, policy)

assert input_class.contains(instance)
result = Adapter.solve_without_preparation(instance)

*_without_preparation()とAdapter constructorはPreparationしません。上の経路では、編集したPolicyを自分で適用してから渡します。一連の実行例はPreparationで変換する制約族を選ぶを参照してください。

AdapterではINPUT_CLASS membershipがapplicabilityです。converterやBackendは、その後のsolver input構築や実行で別のerrorを返すことがあります。それらは追加のapplicability条件ではありません。

Solverの出力をSolutionやSampleSetに戻すときも、Adapterへ渡した同じ変換済みInstanceで評価します。そのInstanceが保持する変数間のdependencyとremoved constraintにより、encoding前の変数値や変換前の制約も評価できます。値の復元はInstanceの基本モデル、制約の評価規則はRemoved constraintsと実行可能性を参照してください。

詳細：到達できない場合と部分的な変更#

すべての configured phase を適用しても target に到達しない場合、PreparationTargetNotReachedError が送出されます。report 属性には、最終状態に対する InstanceClassMembershipReport が入ります。呼び出し側は report を見て Policy を追加・変更するか、異なる target を選べます。

Preparation全体が失敗しても、自動的に変更前の状態へ戻るわけではありません。後のphaseが失敗しても、それより前に完了した変更はInstanceに残ります。通常のsolve()とsample()ではこの変更も内部copyだけに残ります。明示的なprepare()で失敗後も変換前のInstance自体を使う必要がある場合だけ、事前にcopyを作ってください。個々の変換が失敗時にどこまで変更を残すかは、それぞれのAPI Referenceを参照してください。

初めてAdapterを使う場合はTutorialから始め、失敗時の処理が必要になった時点で本節と各変換のAPI Referenceを確認してください。

目次