特殊制約型#

OMMX は通常の制約（Constraint、等式・不等式を持つ Function）に加えて、数理最適化で頻出するいくつかの特殊な制約を第一級の制約型として扱います。本ページでは以下の3種類の特殊制約型の定義と使い方、および PySCIPOpt Adapter を使って実際に解く手順を説明します。

IndicatorConstraint: バイナリ変数による条件付き制約
OneHotConstraint: バイナリ変数集合のうち丁度1つが1
Sos1Constraint: 変数集合のうち高々1つが非ゼロ

以下の例では OMMX Adapterで最適化問題を解くと同様に PySCIPOpt Adapter を使うので、事前にインストールしてください。

pip install ommx-pyscipopt-adapter

PySCIPOpt Adapter は Indicator と SOS1 をサポート宣言しており、SCIP の addConsIndicator / addConsSOS1 にそのまま渡します（等式 Indicator は上下2本の不等式 Indicator に分解されます）。OneHot はサポート宣言がないため、Adapter 内部で通常の等式制約に自動変換されてから SCIP に渡されます。Adapter 側のサポート宣言や変換の詳細は Adapter Capability モデルと制約変換を参照してください。

IndicatorConstraint#

Indicator Constraint はバイナリ変数 \(z\) に対し、\(z = 1\) のときのみ制約 \(f(x) \leq 0\) あるいは \(f(x) = 0\) を課す条件付き制約です。\(z = 0\) のときはこの制約は無条件に満たされると見なされます。

IndicatorConstraint は、既存の Constraint に対して Constraint.with_indicator() を呼ぶことで生成できます。

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

Instance.from_components の indicator_constraints= 引数に dict[int, IndicatorConstraint] を渡すことでインスタンスに追加できます。

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 制約をサポート宣言しているので、そのまま求解できます。

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\) であることを要求します。

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 制約を直接受け付けます）に効率的に渡すことができます。

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 に渡されます。

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 に残ります。

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 の変数はバイナリとは限らない（連続変数でも良い）。

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]

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 制約をサポート宣言しているので、そのまま求解できます。

solution = OMMXPySCIPOptAdapter.solve(instance_s1)
# 高々 1 つだけが非ゼロなので、1 つを上限 10 にして他を 0 にする
assert abs(solution.objective - 10.0) < 1e-6

制約種別ごとに独立したID空間#

OMMX では、通常制約・Indicator・OneHot・SOS1 の4つはそれぞれ独立したID空間を持ちます。Instance.from_components に渡す4つの dict はそれぞれ独立したキー空間として扱われるため、異なる制約型同士で同じ整数 ID を使っても衝突しません。

したがって、例えば「通常制約 ID=1」と「Indicator 制約 ID=1」は衝突せず、別々の制約として共存できます。

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 モデルと変換参照）と、新たに生成される通常制約は Constraint 側の ID 空間から割り当てられます。変換後に衝突する可能性があるのは通常制約の ID のみです。

評価結果の参照#

インスタンスを解いて得られた Solution や SampleSet は、共通の constraints_df() を kind= で切り替えて使います。

制約型	`kind=` の値
通常制約	`"regular"`（デフォルト）
Indicator	`"indicator"`
OneHot	`"one_hot"`
SOS1	`"sos1"`

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 は constraints_df() のデフォルトカラムには含まれません。include= に "removed_reason" を渡すと、reason 名と removed_reason.{key} パラメータカラムがまとめて追加されます（評価前に削除された制約の行のみ値が入り、それ以外の行は NA）。

df = solution.constraints_df(
    include=("metadata", "parameters", "removed_reason"),
)

Indicator / OneHot / SOS1 でも同じく、対応する kind= と一緒に "removed_reason" を include= に渡せば取得できます。long-format で（id, parameter_key）の組合せごとに 1 行を得たい場合は、kind= で切り替えられる constraint_removed_reasons_df() サイドカーを引き続き利用できます。

Relax / Restore#

IndicatorConstraint は、通常制約と同じ relax / restore ワークフローを持ちます。

Instance.relax_indicator_constraint(): Indicator 制約を「緩和」（無効化）し、理由文字列を記録します。緩和された制約は removed_indicator_constraints に移動します。
Instance.restore_indicator_constraint(): 緩和した Indicator 制約を元に戻します。インジケータ変数が既に値を代入されている・固定されている場合は失敗します。

OneHot / SOS1 については、removed_one_hot_constraints / removed_sos1_constraints への移動は Capability モデルと制約変換で扱う変換 API によって行われます。

特殊制約型

目次