--- jupytext: text_representation: extension: .md format_name: myst format_version: 0.13 jupytext_version: 1.19.1 kernelspec: display_name: ommx-update-books (3.9.23) language: python name: python3 --- # 特殊制約型 OMMX は通常の制約（{class}`~ommx.v1.Constraint`、等式・不等式を持つ {class}`~ommx.v1.Function`）に加えて、数理最適化で頻出するいくつかの特殊な制約を第一級の制約型として扱います。本ページでは以下の3種類の特殊制約型の定義と使い方、および PySCIPOpt Adapter を使って実際に解く手順を説明します。 - {class}`~ommx.v1.IndicatorConstraint`: バイナリ変数による条件付き制約 - {class}`~ommx.v1.OneHotConstraint`: バイナリ変数集合のうち丁度1つが1 - {class}`~ommx.v1.Sos1Constraint`: 変数集合のうち高々1つが非ゼロ 以下の例では [OMMX Adapterで最適化問題を解く](../tutorial/solve_with_ommx_adapter.md) と同様に PySCIPOpt Adapter を使うので、事前にインストールしてください。 ``` pip install ommx-pyscipopt-adapter ``` PySCIPOpt Adapter は Indicator と SOS1 をサポート宣言しており、SCIP の `addConsIndicator` / `addConsSOS1` にそのまま渡します（等式 Indicator は上下2本の不等式 Indicator に分解されます）。OneHot はサポート宣言がないため、Adapter 内部で通常の等式制約に自動変換されてから SCIP に渡されます。Adapter 側のサポート宣言や変換の詳細は [Adapter Capability モデルと制約変換](./capability_model.md) を参照してください。 ## IndicatorConstraint **Indicator Constraint** はバイナリ変数 $z$ に対し、$z = 1$ のときのみ制約 $f(x) \leq 0$ あるいは $f(x) = 0$ を課す条件付き制約です。$z = 0$ のときはこの制約は無条件に満たされると見なされます。 {class}`~ommx.v1.IndicatorConstraint` は、既存の {class}`~ommx.v1.Constraint` に対して {meth}`Constraint.with_indicator() ` を呼ぶことで生成できます。 ```{code-cell} ipython3 from ommx.v1 import Instance, DecisionVariable, Equality z = DecisionVariable.binary(0, name="z") x = DecisionVariable.continuous(1, lower=0, upper=10, name="x") # z = 1 => x <= 5 ic = (x <= 5).with_indicator(z) assert ic.indicator_variable_id == 0 assert ic.equality == Equality.LessThanOrEqualToZero ``` {meth}`Instance.from_components ` の `indicator_constraints=` 引数に `dict[int, IndicatorConstraint]` を渡すことでインスタンスに追加できます。 ```{code-cell} ipython3 instance = Instance.from_components( decision_variables=[z, x], objective=x, constraints={0: z == 1}, # z を 1 に固定 indicator_constraints={0: ic}, # z = 1 => x <= 5 sense=Instance.MAXIMIZE, ) assert set(instance.indicator_constraints.keys()) == {0} ``` PySCIPOpt Adapter は Indicator 制約をサポート宣言しているので、そのまま求解できます。 ```{code-cell} ipython3 from ommx_pyscipopt_adapter import OMMXPySCIPOptAdapter solution = OMMXPySCIPOptAdapter.solve(instance) # z = 1 で x <= 5 が効くので x の最大値 5 が目的関数値 assert abs(solution.objective - 5.0) < 1e-6 ``` ## OneHotConstraint **One-hot 制約** はバイナリ変数の集合 $\{x_1, \ldots, x_n\}$ に対して $\sum_i x_i = 1$、つまり丁度1つだけが $1$ であることを要求します。 ```{code-cell} ipython3 from ommx.v1 import OneHotConstraint xs = [DecisionVariable.binary(i, name="x", subscripts=[i]) for i in range(3)] oh = OneHotConstraint(variables=[0, 1, 2]) assert oh.variables == [0, 1, 2] ``` `variables` に渡す ID のバイナリ変数はインスタンス構築時の `decision_variables` に含まれている必要があります。数学的には通常の等式制約 $x_0 + x_1 + x_2 - 1 = 0$ と等価ですが、first-class の制約として保持することで、対応するソルバー（MIP系ソルバーの多くは one-hot 制約を直接受け付けます）に効率的に渡すことができます。 ```{code-cell} ipython3 values = [5.0, 10.0, 3.0] instance_oh = Instance.from_components( decision_variables=xs, objective=sum(v * x for v, x in zip(values, xs)), constraints={}, one_hot_constraints={0: oh}, sense=Instance.MAXIMIZE, ) assert set(instance_oh.one_hot_constraints.keys()) == {0} ``` PySCIPOpt Adapter は OneHot をサポート宣言していないため、`solve` の内部で通常の等式制約 $x_0 + x_1 + x_2 - 1 = 0$ に自動変換されてから SCIP に渡されます。 ```{code-cell} ipython3 solution = OMMXPySCIPOptAdapter.solve(instance_oh) # 3 つのうち丁度 1 つを選ぶので、最大値 10 をもつ x_1 が選ばれる assert abs(solution.objective - 10.0) < 1e-6 ``` `instance_oh` は `solve` によって in-place に書き換わるため、呼び出し後は OneHot 制約が除去され、通常制約へ変換された痕跡が `removed_one_hot_constraints` に残ります。 ```{code-cell} ipython3 assert instance_oh.one_hot_constraints == {} assert len(instance_oh.constraints) == 1 assert set(instance_oh.removed_one_hot_constraints.keys()) == {0} ``` ## Sos1Constraint **SOS1 (Special Ordered Set type 1)** 制約は変数集合 $\{x_1, \ldots, x_n\}$ の**高々1個**しか非ゼロになれないことを要求します。One-hot との違いは以下の通りです。 - One-hot は $\sum x_i = 1$ を要求するため、丁度1個が非ゼロ。 - SOS1 は高々1個が非ゼロで、全て $0$ であることも許容。 - SOS1 の変数はバイナリとは限らない（連続変数でも良い）。 ```{code-cell} ipython3 from ommx.v1 import Sos1Constraint ys = [DecisionVariable.continuous(i, lower=0, upper=10, name="y", subscripts=[i]) for i in range(3, 6)] s1 = Sos1Constraint(variables=[3, 4, 5]) assert s1.variables == [3, 4, 5] ``` ```{code-cell} ipython3 instance_s1 = Instance.from_components( decision_variables=ys, objective=sum(ys), constraints={}, sos1_constraints={0: s1}, sense=Instance.MAXIMIZE, ) assert set(instance_s1.sos1_constraints.keys()) == {0} ``` PySCIPOpt Adapter は SOS1 制約をサポート宣言しているので、そのまま求解できます。 ```{code-cell} ipython3 solution = OMMXPySCIPOptAdapter.solve(instance_s1) # 高々 1 つだけが非ゼロなので、1 つを上限 10 にして他を 0 にする assert abs(solution.objective - 10.0) < 1e-6 ``` ## 制約種別ごとに独立したID空間 OMMX では、通常制約・Indicator・OneHot・SOS1 の4つはそれぞれ**独立したID空間**を持ちます。{meth}`Instance.from_components ` に渡す4つの dict はそれぞれ独立したキー空間として扱われるため、異なる制約型同士で同じ整数 ID を使っても衝突しません。 したがって、例えば「通常制約 ID=1」と「Indicator 制約 ID=1」は衝突せず、別々の制約として共存できます。 ```{code-cell} ipython3 z2 = DecisionVariable.binary(10, name="z2") x2 = DecisionVariable.continuous(11, lower=0, upper=10, name="x2") instance_mix = Instance.from_components( decision_variables=[z2, x2] + xs + ys, objective=x2, constraints={1: z2 == 1}, # 通常制約 ID=1 indicator_constraints={1: (x2 <= 5).with_indicator(z2)}, # Indicator ID=1 one_hot_constraints={1: OneHotConstraint(variables=[0, 1, 2])}, # OneHot ID=1 sos1_constraints={1: Sos1Constraint(variables=[3, 4, 5])}, # SOS1 ID=1 sense=Instance.MAXIMIZE, ) # 4 種の dict それぞれが ID=1 の制約を独立に保持している assert set(instance_mix.constraints.keys()) == {1} assert set(instance_mix.indicator_constraints.keys()) == {1} assert set(instance_mix.one_hot_constraints.keys()) == {1} assert set(instance_mix.sos1_constraints.keys()) == {1} ``` ただし、特殊制約型を通常制約に変換する（[Capability モデルと変換](./capability_model.md) 参照）と、新たに生成される通常制約は **`Constraint` 側の ID 空間**から割り当てられます。変換後に衝突する可能性があるのは通常制約の ID のみです。 ## 評価結果の参照 インスタンスを解いて得られた {class}`~ommx.v1.Solution` や {class}`~ommx.v1.SampleSet` は、共通の {meth}`~ommx.v1.Solution.constraints_df` を `kind=` で切り替えて使います。 | 制約型 | `kind=` の値 | |---|---| | 通常制約 | `"regular"`（デフォルト） | | Indicator | `"indicator"` | | OneHot | `"one_hot"` | | SOS1 | `"sos1"` | ```python solution.constraints_df() # regular（デフォルト） solution.constraints_df(kind="indicator") # Indicator sample_set.constraints_df(kind="one_hot") # OneHot ``` DataFrame の index 名は kind ごとに qualified（`regular_constraint_id` / `indicator_constraint_id` / `one_hot_constraint_id` / `sos1_constraint_id`）になっており、別 ID 空間どうしを誤って `df.join()` した場合に `df.head()` 等で気づきやすくなっています。 Indicator 制約の DataFrame には、`indicator_active` というカラムが含まれます。これにより「インジケータが OFF だった（制約は自明に満たされた）」ケースと「インジケータが ON で制約が本当に満たされた」ケースを区別できます。なお、Indicator 制約には双対変数の値は定義されない（条件付き制約に対する双対値は一般に well-defined ではない）ため、`dual_variable` は含まれません。 ### `include=` で removed_reason カラムを追加する `removed_reason` は {meth}`~ommx.v1.Solution.constraints_df` のデフォルトカラムには含まれません。`include=` に `"removed_reason"` を渡すと、reason 名と `removed_reason.{key}` パラメータカラムがまとめて追加されます（評価前に削除された制約の行のみ値が入り、それ以外の行は NA）。 ```python df = solution.constraints_df( include=("metadata", "parameters", "removed_reason"), ) ``` Indicator / OneHot / SOS1 でも同じく、対応する `kind=` と一緒に `"removed_reason"` を `include=` に渡せば取得できます。long-format で（id, parameter_key）の組合せごとに 1 行を得たい場合は、`kind=` で切り替えられる {meth}`~ommx.v1.Solution.constraint_removed_reasons_df` サイドカーを引き続き利用できます。 ## Relax / Restore {class}`~ommx.v1.IndicatorConstraint` は、通常制約と同じ relax / restore ワークフローを持ちます。 - {meth}`Instance.relax_indicator_constraint() `: Indicator 制約を「緩和」（無効化）し、理由文字列を記録します。緩和された制約は `removed_indicator_constraints` に移動します。 - {meth}`Instance.restore_indicator_constraint() `: 緩和した Indicator 制約を元に戻します。インジケータ変数が既に値を代入されている・固定されている場合は失敗します。 OneHot / SOS1 については、`removed_one_hot_constraints` / `removed_sos1_constraints` への移動は [Capability モデルと制約変換](./capability_model.md) で扱う変換 API によって行われます。