# 範囲制約と整数線形計画法の求解
:::{container} prog-cpp
## 範囲制約の多項式定式化
$f$ をバイナリ変数の多項式とします.
範囲制約は $l**NOTE**
> Hi-QUBOは内部的に軽量な改善を施しており,範囲制約をわずかに少ないバイナリ変数数で符号化できます.
> 詳細は[比較演算子](../advanced/comparison-operators.md)に記載されています.
## 整数線形計画法の求解
**整数線形計画法**のインスタンスは,**目的関数**と複数の**線形制約**から構成されます.
例えば,以下の整数線形計画問題は2つの変数,1つの目的関数,2つの制約を持ちます:
$$
\begin{aligned}
\text{Maximize: } & & & 5x + 4y \\
\text{Subject to: } & && 2x + 3y \le 24 \\
& & & 7x + 5y \le 54
\end{aligned}
$$
この問題の最適解は $x=4$, $y=5$ であり,目的関数値は $40$ です.
以下のHi-QUBOプログラムは,Easy Solverを使用してこの最適解を求めます:
```{literalinclude} /../programFiles/cppPrograms/basic/range-constraints-and-ilp-program1.cpp
:language: cpp
:caption: range-constraints-and-ilp-program1.cpp
```
このHi-QUBOプログラムでは,
- **`f`** は目的関数を表し,
- **`c1`** と **`c2`** は範囲制約を表し,
- **`g`** はこれらを1つの最適化式にまとめたものです.
目標が最大化であるため,目的関数は `-f` として符号を反転しています.
制約 `c1` と `c2` には重み100のペナルティを付け,高い優先度で制約が満たされるようにしています.
`g` に対してEasy Solverインスタンスを作成し,制限時間1.0秒で探索を実行します.
最適解 `sol` を取得した後,`x`,`y`,`f`,`c1`,`c2`,`c1.body(sol)`,`c2.body(sol)` の値を出力します.
プログラムの出力は以下の通りです:
```{include} /../programFiles/markDown/basic/range-constraints-and-ilp.md
:start-after:
:end-before:
```
ここで,
- **`c1`** は制約 `0 <= 2 x + 3 y <= 24` のペナルティ式（制約が満たされると 0）であり,
- **`c1.body()`** は線形式 `2 x + 3 y` を返し,`c1.body(sol)` はその値を `sol` で評価します.
ソルバーが正しく最適解を見つけたことが確認できます.
## ネイティブ制約 `cons()` による記述
上のプログラムでは,制約 `c1` と `c2` を重み付きのペナルティ式として目的関数に加えました.
Hi-QUBO では,さらに一歩進めて,制約を `qbpp::cons()` で囲んで**制約であることを明示**できます:
```{literalinclude} /../programFiles/cppPrograms/basic/range-constraints-and-ilp-program2.cpp
:language: cpp
:caption: range-constraints-and-ilp-program2.cpp
```
変更点は `100 * (c1 + c2)` を `100 * (qbpp::cons(c1) + qbpp::cons(c2))` に書き換えただけです.
`qbpp::cons()` で囲まれた部分は**制約として特別に処理**され,
バンドルされたソルバーは宣言された制約を満たすように効率よく探索を行います.
`g.cons(sol)` は解 `sol` で違反している制約の本数を返します（0 なら全制約を充足）.
プログラムの出力は以下の通りです:
```{include} /../programFiles/markDown/basic/range-constraints-and-ilp.md
:start-after:
:end-before:
```
`cons()` で宣言した制約は,バンドルされた 3 つのソルバー（Easy Solver・
Exhaustive Solver・ABS3 Solver）すべてで同じ意味を持ち,Exhaustive Solver は
このペナルティ込みエネルギーの**厳密な最小解**を返します.
MIP ソルバー（Gurobi 等）では**ハード制約**（必ず満たすべき制約）として扱われます.
詳細は[ネイティブ制約](../basic/constraints.md)をご覧ください.
:::
:::{container} prog-python
## 範囲制約の多項式定式化
$f$ をバイナリ変数の多項式とします.
範囲制約は $l**NOTE**
> PyQBPPは内部的に軽量な改善を施しており,範囲制約をわずかに少ないバイナリ変数数で符号化できます.
> 詳細は[比較演算子](../advanced/comparison-operators.md)に記載されています.
## 整数線形計画法の求解
**整数線形計画法**のインスタンスは,**目的関数**と複数の**線形制約**から構成されます.
例えば,以下の整数線形計画は2つの変数,1つの目的関数,2つの制約を持ちます：
$$
\begin{aligned}
\text{Maximize: } & & & 5x + 4y \\
\text{Subject to: } & && 2x + 3y \le 24 \\
& & & 7x + 5y \le 54
\end{aligned}
$$
この問題の最適解は $x=4$, $y=5$ で,目的関数の値は $40$ です.
以下のPyQBPPプログラムは,Easy Solverを使ってこの最適解を求めます：
```{literalinclude} /../programFiles/pythonPrograms/basic/range-constraints-and-ilp-program1.py
:language: python
:caption: range-constraints-and-ilp-program1.py
```
このプログラムでは,
- **`f`** は目的関数を表し,
- **`c1`** と **`c2`** は **`constrain()`** を使って作成された範囲制約を表し,
- **`g`** はそれらを1つの最適化式にまとめたものです.
目標が最大化であるため,目的関数は `-f` として符号を反転しています.
制約 `c1` と `c2` は重み100のペナルティを付けて,高い優先度で満たされるようにしています.
`g` に対してEasy Solverのインスタンスを作成し,制限時間1.0秒を `search()` のパラメータとして渡して探索を実行します.
最適解 `sol` を得た後,プログラムは `x`,`y`,`f`,`c1`,`c2`,および制約本体の式の値を出力します.
プログラムの出力は以下の通りです：
```{include} /../programFiles/markDown/basic/range-constraints-and-ilp.md
:start-after:
:end-before:
```
ここで,
- **`c1`** は制約 `0 <= 2x + 3y <= 24` のペナルティであり,
- **`c1.body`** は線形式 `2x + 3y` を表します.
ソルバーが正しく最適解を見つけていることが確認できます.
## ネイティブ制約 `cons()` による記述
上のプログラムでは,制約 `c1` と `c2` を重み付きのペナルティ式として目的関数に加えました.
PyQBPP では,さらに一歩進めて,制約を **`qbpp.cons()`** で作成して**制約であることを明示**できます:
```{literalinclude} /../programFiles/pythonPrograms/basic/range-constraints-and-ilp-program2.py
:language: python
:caption: range-constraints-and-ilp-program2.py
```
変更点は `constrain()` の代わりに `qbpp.cons()` を使うことだけです（引数の書き方は同じで,
範囲制約は `between=(l, u)`,等式制約は `equal=n` で指定します）.
`qbpp.cons()` で作成した部分は**制約として特別に処理**され,
バンドルされたソルバーは宣言された制約を満たすように効率よく探索を行います.
`g.cons(sol)` は解 `sol` で違反している制約の本数を返します（0 なら全制約を充足）.
プログラムの出力は以下の通りです:
```{include} /../programFiles/markDown/basic/range-constraints-and-ilp.md
:start-after:
:end-before:
```
`cons()` で宣言した制約は,バンドルされた 3 つのソルバー（Easy Solver・
Exhaustive Solver・ABS3 Solver）すべてで同じ意味を持ち,Exhaustive Solver は
このペナルティ込みエネルギーの**厳密な最小解**を返します.
MIP ソルバー（Gurobi 等）では `ilp=True` を指定すると**ハード制約**
（必ず満たすべき制約）として扱われます.
詳細は[ネイティブ制約](../basic/constraints.md)をご覧ください.
:::