# ネイティブ制約 :::{container} prog-cpp Hi-QUBO では，式の中の制約部分を `qbpp::cons()` で囲むと，その部分は **制約とみなされて特別に処理**されます．Hi-QUBO にバンドルされているソルバーは，宣言された制約を満たすように効率よく探索を行います． ## 整数線形計画法を `cons()` で解く [範囲制約と整数線形計画法の求解](range-constraints.md)では，次の整数線形計画問題を，範囲制約 `c1`・`c2` を重み付きのペナルティ式として目的関数に加える方法で解きました: $$ \begin{aligned} \text{Maximize: } & & & 5x + 4y \\ \text{Subject to: } & && 2x + 3y \le 24 \\ & & & 7x + 5y \le 54 \end{aligned} $$ 同じ問題は，制約を `qbpp::cons()` で囲むと次のように書けます: ```{literalinclude} /../programFiles/cppPrograms/basic/constraints-program1.cpp :language: cpp :caption: constraints-program1.cpp ``` 変更点は，ペナルティ和 `100 * (c1 + c2)` を `100 * (qbpp::cons(c1) + qbpp::cons(c2))` に書き換えただけです．これだけで `c1`・`c2` は単なるペナルティ式ではなく**制約として宣言**され，ソルバーは制約を満たす解を効率よく探索します． `g.cons(sol)` は解 `sol` で違反している制約の本数を返します（0 なら全制約を充足）．プログラムの出力は以下の通りです: ```{include} /../programFiles/markDown/basic/constraints.md :start-after: :end-before: ``` ## ナップサック問題の例もう1つの例として，次のプログラムは簡単なナップサック問題（容量制約と等式制約）を `cons()` で解きます: ```{literalinclude} /../programFiles/cppPrograms/basic/constraints-program2.cpp :language: cpp :caption: constraints-program2.cpp ``` 従来のペナルティ式からの移行は，制約部分を `qbpp::cons()` で囲むだけです — `obj + 1000 * (rows + cols)` を `obj + 1000 * qbpp::cons(rows + cols)` に書き換えます．多くの問題で，同じ制約をペナルティ式のまま解くより大幅に良い解が得られます． ## 制約の書き方制約は右辺が整数の比較，または連鎖した両側範囲を `qbpp::cons()` で囲んで書きます．重みは制約へのスカラー係数として書き，`+` で目的関数や他の制約と自由に足し合わせられます． ```{include} /../programFiles/markDown/basic/constraints.md :start-after: :end-before: ``` 配列の比較を囲むと要素ごとに 1 本の制約になるので，行列の one-hot 行は 1 文で書けます． ```{include} /../programFiles/markDown/basic/constraints.md :start-after: :end-before: ``` 制約の重み付き和をまとめて `qbpp::cons()` で囲むこともできます．次の例は重み 100 と 150 の 2 本の制約を作ります． ```{include} /../programFiles/markDown/basic/constraints.md :start-after: :end-before: ``` 制約を蓄積した式に `*=` を使うと，蓄積済みの全制約の重みを一括でスケールできます． ```{include} /../programFiles/markDown/basic/constraints.md :start-after: :end-before: ``` 式を出力すると**目的関数の多項式**が，`f.cons()` を出力すると宣言された **制約リスト**が表示されます（重みが 1 のときは係数プレフィックスを省略，片側制約は片側表示）． ```{include} /../programFiles/markDown/basic/constraints.md :start-after: :end-before: ``` 出力は次のようになります． ```{include} /../programFiles/markDown/basic/constraints.md :start-after: :end-before: ``` ### 離散許容値集合式の値が**とびとびの許容値のいずれか**に一致することを要求する制約は， `qbpp::equal{...}` で書けます．`qbpp::cons(s == qbpp::equal{0, 2})` は `s` が 0 か 2 のときだけ充足されます（`qbpp::cons(s, qbpp::equal{0, 2})` と書いても同じです）．許容値は任意個・任意の整数を指定できます． ```{include} /../programFiles/markDown/basic/constraints.md :start-after: :end-before: ``` これはグラフの path や cycle を構成する辺を選ぶ問題（各頂点の次数が 0 か 2 のとき充足）などに便利です．許容値がとびとびのため，両側範囲 `l <= f <= u` では表現できません．制約リストには `== {0, 2}` と表示されます．この制約は `EasySolver`・`ExhaustiveSolver`・`ABS3Solver` で使えます（MIP ソルバーは非対応）．double 係数フロントエンド（`DOUBLE_TYPE*`）では使えません． ### 非線形の制約本体非線形（2 次以上）の式を `qbpp::cons()` に入れた場合も，**等式**（`x*y + z == 1` など）・**範囲**（`1 <= x*y + z*w <= 2` など）ともにそのまま制約として扱われ，バンドルされたソルバー（`EasySolver` / `ExhaustiveSolver` / `ABS3Solver`）が制約を満たすよう探索します．外部の MIP／ILP ソルバーは非線形の制約本体を受け付けないため，その場合は `expand_cons()`（後述）で従来のペナルティ式に展開してから渡してください． ## 制約が返す値 `qbpp::cons()` で宣言した制約は，変数割当のもとで**違反量の 2 乗**を値として持ちます．制約本体の式を $f$ とすると，等式制約の値は $$ \operatorname{cons}(f = k) = (f - k)^2 $$ 範囲制約の値は $$ \operatorname{cons}(l \le f \le u) = \begin{cases} (l - f)^2 & (f < l) \\ 0 & (l \le f \le u) \\ (f - u)^2 & (u < f) \end{cases} $$ です（片側制約は該当する側だけが働きます）．重み $P$ を掛けた制約 $P \cdot \operatorname{cons}(\cdots)$ はこの値の $P$ 倍になり，モデル全体の値は $$ f(\mathrm{sol}) = \mathrm{objective} + \sum_{c} P_c \cdot \mathrm{viol}_c^2 $$ で，バンドルソルバーが報告する Energy と一致します．全ての制約を満たす解では Energy = objective です． ## 式の演算規則制約付きの式 `f` はモデルの完全な記述です． - `f(sol)` はソルバーが報告する Energy と一致します． - `f.cons(sol)` は違反している制約の**本数**を返します（0 なら全充足）． - 目的関数の調整（`+`, `-`, 定数加算）と 0 以外のスカラー倍（重みの一括スケール），`simplify_as_binary()`，`qbpp::replace()` は制約を保ったまま使えます． - `f.simplify_as_binary()` は目的関数と制約の両方に適用されます．ソルバーに渡す前に 1 回呼んでください — 特に `qbpp::replace()` で変数を置換した後に必要です． - 重みは通常は正の値を使いますが，負の重みも指定できます（制約の減算・負号も同様に重みの符号反転として扱われます）．負の重みは違反を「優遇」する特殊な用途向けで，バンドルソルバー（`EasySolver`・`ExhaustiveSolver`・`ABS3Solver`）でのみ使えます — MIP ソルバー（ハード制約扱い）に渡すとエラーになります． - 制約の宣言を壊す演算 — `sqr()`，式同士の乗算，0 倍（制約が黙って消えるため），`reduce()` など — は明示的にエラーになります． ## ソルバーごとの意味論すべてのソルバーが同じ式 `f` を 1 引数で受け付けます． | ソルバー | 意味論 | | ---------------------------------------------------------------------- | --------------------------------------------------------------------------------------------------------------------------------------------------------------- | | `EasySolver`, `ABS3Solver` | **ソフト**: 制約違反には重みに応じたペナルティが加算され，制約を満たす良い解を効率よく探索する | | `ExhaustiveSolver` | **ソフト**: `EasySolver`・`ABS3Solver` と同じペナルティ込みエネルギーで全割当を順位付けし，その**厳密な最小解**を返す（小規模インスタンスでの検証・デバッグ用） | | `GurobiSolver`, `ScipSolver`, `HighsSolver`, `CbcSolver`, `GlpkSolver` | **ハード**: 制約は MIP の線形制約として渡される（重みは無視.負の重みの制約が含まれる場合はエラー） | 同一のモデル定義を厳密ソルバーで検証してからヒューリスティックソルバーでスケールアップできます． ```{literalinclude} /../programFiles/cppPrograms/basic/constraints-program3.cpp :language: cpp :caption: constraints-program3.cpp ``` ネイティブ制約がある場合，`target_energy` は「エネルギーが target に達し， **かつ全制約が充足**」のときだけ探索を停止します． `EasySolver` のデフォルトコールバックはエネルギーと並べて充足の進捗を表示します．`Energy` はペナルティ込みの合計，`Obj` は目的関数部分， `Viol = k/m` は m 本の制約のうち k 本が違反中であることを示します．全制約が充足されると `Energy` と `Obj` は一致します． ## 解の検証 `violations()` は解に対して全制約を評価し，制約値・境界・違反距離・重みを報告します． ```{include} /../programFiles/markDown/basic/constraints.md :start-after: :end-before: ``` ## 従来のペナルティ式への展開 `qbpp::expand_cons(f)` は，宣言された制約を**従来のペナルティ式** （比較演算子で書いた場合と同じ形）に展開した通常の式を返します．ネイティブ制約に対応しない外部の QUBO/HUBO ツールに渡す場合などに使います．`f` 自身を上書きする `f.expand_cons()` もあります．展開結果は簡約されていないので，ソルバーに渡す前に `simplify_as_binary()` を呼んでください． ```{include} /../programFiles/markDown/basic/constraints.md :start-after: :end-before: ``` ## 自由記述ペナルティ **充足のときちょうど値が 0** になる式であれば，従来の QUBO ペナルティスタイルの式をそのまま `qbpp::cons()` に混ぜられます． ```{include} /../programFiles/markDown/basic/constraints.md :start-after: :end-before: ``` 比較で書いた制約は 1 本ずつ追跡されます．自由記述部分は，その値が 0 のときだけ充足と見なされます．デフォルトコールバックはこの部分を `Pen = ...`（0 なら充足）として表示し，`violations()` は境界 `[0, 0]` の最終エントリとして報告します．式が非負で最小値 0 になることの保証は利用者の責任です． ::: :::{container} prog-python PyQBPP では，式の中の制約部分を `qbpp.cons()` で囲むと，その部分は **制約とみなされて特別に処理**されます．Hi-QUBO にバンドルされているソルバーは，宣言された制約を満たすように効率よく探索を行います． ## 整数線形計画法を `cons()` で解く [範囲制約と整数線形計画法の求解](range-constraints.md)では，次の整数線形計画問題を，範囲制約を重み付きのペナルティ式として目的関数に加える方法で解きました: $$ \begin{aligned} \text{Maximize: } & & & 5x + 4y \\ \text{Subject to: } & && 2x + 3y \le 24 \\ & & & 7x + 5y \le 54 \end{aligned} $$ 同じ問題は，制約を `qbpp.cons()` で作成すると次のように書けます: ```{literalinclude} /../programFiles/pythonPrograms/basic/constraints-program1.py :language: python :caption: constraints-program1.py ``` 変更点は，`constrain()` で作っていたペナルティ式を `qbpp.cons()` に置き換えただけです（引数の書き方は同じです）．これだけで 2 つの範囲制約は単なるペナルティ式ではなく**制約として宣言**され，ソルバーは制約を満たす解を効率よく探索します． `g.cons(sol)` は解 `sol` で違反している制約の本数を返します（0 なら全制約を充足）．プログラムの出力は以下の通りです: ```{include} /../programFiles/markDown/basic/constraints.md :start-after: :end-before: ``` ## ナップサック問題の例もう1つの例として，次のプログラムは簡単なナップサック問題（容量制約と等式制約）を `cons()` で解きます: ```{literalinclude} /../programFiles/pythonPrograms/basic/constraints-program2.py :language: python :caption: constraints-program2.py ``` 従来のペナルティ式からの移行は，制約部分を `qbpp.cons()` で囲むだけです — `obj + 1000 * (rows + cols)` を `obj + 1000 * qbpp.cons(rows + cols)` に書き換えます．多くの問題で，同じ制約をペナルティ式のまま解くより大幅に良い解が得られます． ## 制約の書き方制約は `qbpp.cons(式 == 整数)`，または範囲を kwargs で直接指定する `qbpp.cons(式, between=(下限, 上限))`（片側は `None`）で書きます．重みは制約へのスカラー係数として書き，`+` で目的関数や他の制約と自由に足し合わせられます． ```{literalinclude} /../programFiles/pythonPrograms/basic/constraints-program3.py :language: python :caption: constraints-program3.py ``` 配列の比較を囲むと要素ごとに 1 本の制約になるので，行列の one-hot 行は 1 文で書けます． ```{literalinclude} /../programFiles/pythonPrograms/basic/constraints-program4.py :language: python :caption: constraints-program4.py ``` 制約を蓄積した式に `*=` を使うと，蓄積済みの全制約の重みを一括でスケールできます． ```{literalinclude} /../programFiles/pythonPrograms/basic/constraints-program5.py :language: python :caption: constraints-program5.py ``` 式を `print` すると**目的関数の多項式**が表示され，`f.cons()` は宣言された **制約リスト**の文字列を返します（重みが 1 のときは係数プレフィックスを省略，片側制約は片側表示）． ```{literalinclude} /../programFiles/pythonPrograms/basic/constraints-program6.py :language: python :caption: constraints-program6.py ``` 出力は次のようになります． ```{include} /../programFiles/markDown/basic/constraints.md :start-after: :end-before: ``` ### 離散許容値集合式の値が**とびとびの許容値のいずれか**に一致することを要求する制約は， `equal=[...]` で書けます．`qbpp.cons(s, equal=[0, 2])` は `s` が 0 か 2 のときだけ充足されます．許容値は任意個・任意の整数を指定できます． ```{include} /../programFiles/markDown/basic/constraints.md :start-after: :end-before: ``` これはグラフの path や cycle を構成する辺を選ぶ問題（各頂点の次数が 0 か 2 のとき充足）などに便利です．許容値がとびとびのため，両側範囲 `between=(l, u)` では表現できません．制約リストには `== {0, 2}` と表示されます．この制約は `EasySolver`・`ExhaustiveSolver`・`ABS3Solver` で使えます（MIP ソルバーは非対応）．任意精度（`pyqbpp.cppint`）および double 係数（`pyqbpp.d`）バリアントでは使えません． ### 非線形の制約本体非線形（2 次以上）の式を `qbpp.cons()` に入れた場合も，**等式**（`x*y + z == 1` など）・**範囲**（`qbpp.cons(x*y + z*w, between=(1, 2))` など）ともにそのまま制約として扱われ，バンドルされたソルバー（`EasySolver` / `ExhaustiveSolver` / `ABS3Solver`）が制約を満たすよう探索します．外部の MIP／ILP ソルバーは非線形の制約本体を受け付けないため，その場合は `expand_cons()`（後述）で従来のペナルティ式に展開してから渡してください． ## 制約が返す値 `qbpp.cons()` で宣言した制約は，変数割当のもとで**違反量の 2 乗**を値として持ちます．制約本体の式を $f$ とすると，等式制約の値は $$ \operatorname{cons}(f = k) = (f - k)^2 $$ 範囲制約の値は $$ \operatorname{cons}(l \le f \le u) = \begin{cases} (l - f)^2 & (f < l) \\ 0 & (l \le f \le u) \\ (f - u)^2 & (u < f) \end{cases} $$ です（片側制約は該当する側だけが働きます）．重み $P$ を掛けた制約 $P \cdot \operatorname{cons}(\cdots)$ はこの値の $P$ 倍になり，モデル全体の値は $$ f(\mathrm{sol}) = \mathrm{objective} + \sum_{c} P_c \cdot \mathrm{viol}_c^2 $$ で，バンドルソルバーが報告する Energy と一致します．全ての制約を満たす解では Energy = objective です． ## 式の演算規則制約付きの式 `f` はモデルの完全な記述です． - `sol(f)` はソルバーが報告する Energy と一致します． - `f.cons(sol)` は違反している制約の**本数**を返します（0 なら全充足）． - 目的関数の調整（`+`, `-`, 定数加算）と 0 以外のスカラー倍（重みの一括スケール），`simplify_as_binary()`，`qbpp.replace()` は制約を保ったまま使えます． - `f.simplify_as_binary()` は目的関数と制約の両方に適用されます．ソルバーに渡す前に 1 回呼んでください — 特に `qbpp.replace()` で変数を置換した後に必要です． - 重みは通常は正の値を使いますが，負の重みも指定できます（制約の減算・負号も同様に重みの符号反転として扱われます）．負の重みは違反を「優遇」する特殊な用途向けで，バンドルソルバー（`EasySolver`・`ExhaustiveSolver`・`ABS3Solver`）でのみ使えます — MIP ソルバー（ハード制約扱い）に渡すと `RuntimeError` になります． - 制約の宣言を壊す演算 — `qbpp.sqr()`，式同士の乗算，0 倍（制約が黙って消えるため），`qbpp.reduce()` など — は `RuntimeError` になります． ## ソルバーごとの意味論バンドルソルバーは同じ式 `f` を 1 引数で受け付けます． | ソルバー | 意味論 | | --------------------------------------------------------- | --------------------------------------------------------------------------------------------------------------------------------------------------------------- | | `EasySolver`, `ABS3Solver` | **ソフト**: 制約違反には重みに応じたペナルティが加算され，制約を満たす良い解を効率よく探索する | | `ExhaustiveSolver` | **ソフト**: `EasySolver`・`ABS3Solver` と同じペナルティ込みエネルギーで全割当を順位付けし，その**厳密な最小解**を返す（小規模インスタンスでの検証・デバッグ用） | | 外部 MIP ソルバー（`ScipSolver` など，`ilp=True` 指定時） | **ハード**: 制約は MIP の線形制約として渡される（重みは無視.負の重みの制約が含まれる場合は `RuntimeError`） | 制約付きモデルを外部 MIP ソルバーに渡すには ILP モードを使います — `ilp=True` を指定してください（例: `qbpp.ScipSolver(f, ilp=True)`．モデルは線形である必要があります）．`ilp=True` なしで制約付きモデルを渡すとエラーになります．同一のモデル定義を厳密ソルバーで検証してからヒューリスティックソルバーでスケールアップできます． ```{literalinclude} /../programFiles/pythonPrograms/basic/constraints-program7.py :language: python :caption: constraints-program7.py ``` ネイティブ制約がある場合，`target_energy` は「エネルギーが target に達し， **かつ全制約が充足**」のときだけ探索を停止します． `EasySolver` のデフォルトコールバックはエネルギーと並べて充足の進捗を表示します．`Energy` はペナルティ込みの合計，`Obj` は目的関数部分， `Viol = k/m` は m 本の制約のうち k 本が違反中であることを示します．全制約が充足されると `Energy` と `Obj` は一致します． ## 解の検証 `violations(sol)` は解に対して全制約を評価し，制約値・境界・違反距離・重みの dict を制約ごとに返します． ```{literalinclude} /../programFiles/pythonPrograms/basic/constraints-program8.py :language: python :caption: constraints-program8.py ``` ## 従来のペナルティ式への展開 `qbpp.expand_cons(f)` は，宣言された制約を**従来のペナルティ式** （比較演算子や `qbpp.constrain` で書いた場合と同じ形）に展開した通常の式を返します．ネイティブ制約に対応しない外部の QUBO/HUBO ツールに渡す場合などに使います．`f` 自身を上書きする `f.expand_cons()` もあります．展開結果は簡約されていないので，ソルバーに渡す前に `simplify_as_binary()` を呼んでください． ```{literalinclude} /../programFiles/pythonPrograms/basic/constraints-program9.py :language: python :caption: constraints-program9.py ``` ## 自由記述ペナルティ **充足のときちょうど値が 0** になる式であれば，従来の QUBO ペナルティスタイルの式をそのまま `qbpp.cons()` に混ぜられます． ```{literalinclude} /../programFiles/pythonPrograms/basic/constraints-program10.py :language: python :caption: constraints-program10.py ``` 比較で書いた制約は 1 本ずつ追跡されます．自由記述部分は，その値が 0 のときだけ充足と見なされます．デフォルトコールバックはこの部分を `Pen = ...`（0 なら充足）として表示し，`violations()` は境界 `[0, 0]` の最終エントリとして報告します．式が非負で最小値 0 になることの保証は利用者の責任です． :::