# 整数変数と連立方程式の求解
:::{container} prog-cpp
このページでは，バイナリエンコーディングによる整数変数を説明します．
整数値をそのまま保持する[ネイティブ整数変数](../advanced/native-integer.md)も利用できます．
## 整数変数
Hi-QUBOは**整数変数**をサポートしており,内部的には複数のバイナリ変数を用いて実装されています.
整数値の表現には従来のバイナリエンコーディングが使用されます.
$n$個のバイナリ変数$x_0, x_1, \ldots, x_{n-1}$があるとします.
これらの変数は,以下の線形式を用いて$0$から$2^n-1$までのすべての整数を表現できます:
$$
\begin{aligned}
2^0x_0+2^1x_1+\cdots 2^{n-1}x_{n-1}
\end{aligned}
$$
定数オフセット$l$を導入し,$x_{n-1}$の係数を任意の値$d$に置き換えると,次のようになります:
$$
\begin{aligned}
l+2^0x_0+2^1x_1+\cdots +2^{n-2}x_{n-2}+dx_{n-1}
\end{aligned}
$$
この式は$l$から$l+2^{n-1}+d-1$までのすべての整数を表現できます.
このエンコーディングに基づき,整数範囲が$[l,u]$の変数は,以下を満たす適切な$n$と$d$（$1\leq d\leq 2^{n-1}$）を選ぶことで構成できます:
$$
\begin{aligned}
u &= l+2^{n-1}+d-1
\end{aligned}
$$
以下のHi-QUBOプログラムは整数変数の定義方法を示しています:
```{literalinclude} /../programFiles/cppPrograms/basic/integer-variables-and-linear-systems-program1.cpp
:language: cpp
:caption: integer-variables-and-linear-systems-program1.cpp
```
整数変数は**範囲演算子** **`<= <=`**を用いて定義され,変数が取りうる整数の範囲を指定します.
**`qbpp::var_int("name")`**を範囲演算子と組み合わせた式全体が,指定された`name`を持つ**`qbpp::Expr`**オブジェクトを作成し,バイナリ変数でエンコードされた線形式を表現します.
プログラムの出力は次のとおりです:
```{include} /../programFiles/markDown/basic/integer-variables-and-linear-systems.md
:start-after:
:end-before:
```
> **WARNING**
> 整数変数に必要なバイナリ変数の数は,その範囲に対して対数的に増加します.
> $u−l$が大きい場合,QUBOのサイズが増大するため,広い整数範囲はできる限り避けるべきです.
## 連立方程式を解くためのQUBO定式化
Hi-QUBOは,変数を整数変数として表現することで連立方程式を解くことができます.
例として,解が$x=4$,$y=6$である以下の方程式に対するQUBO定式化を構築します:
$$
\begin{aligned}
x + y = 10\\
2x+4y = 28
\end{aligned}
$$
これらの方程式を解くために,範囲$[0,10]$の整数変数$x$と$y$を定義し,それぞれ4つのバイナリ変数でエンコードします:
$$
\begin{aligned}
x = x_0 +2x_1 +4x_2 +3x_3\\
y = y_0 +2y_1 +4y_2 +3y_3
\end{aligned}
$$
以下の各ペナルティ式は,対応する方程式が満たされるとき,かつそのときに限り最小値0をとります:
$$
\begin{aligned}
f(x,y) &= (x+y-10)^2\\
&=(x_0 +2x_1 +4x_2 +3x_3+y_0 +2y_1 +4y_2 +3y_3-10)^2\\
g(x,y) &= (2x+4y -28)^2\\
&= (2\cdot(x_0 +2x_1 +4x_2 +3x_3)+4\cdot( y_0 +2y_1 +4y_2 +3y_3)-28)^2
\end{aligned}
$$
したがって,結合式
$$
\begin{aligned}
h(x,y) &= f(x,y) +g(x,y)
\end{aligned}
$$
は,両方の方程式が同時に満たされるとき,正確にその最小値0を達成します.
## Hi-QUBOプログラム
以下のHi-QUBOプログラムはQUBO式$h(x,y)$を構築し,それを解き,結果の$x$と$y$の値をデコードします:
```{literalinclude} /../programFiles/cppPrograms/basic/integer-variables-and-linear-systems-program2.cpp
:language: cpp
:caption: integer-variables-and-linear-systems-program2.cpp
```
これにより,`x`,`y`,および制約式`f`,`g`,`f.body()`,`g.body()`の値が解と整合していることが確認できます.
> **WARNING**
> Hi-QUBOは,左辺が式で右辺が整数の場合にのみ`==`演算子をサポートしています.
> 整数`==`式や式`==`式の形式の比較はサポートされていません.
> 詳細は[**比較演算子**](../advanced/comparison-operators.md)で説明しています.
:::
:::{container} prog-python
このページでは，バイナリエンコーディングによる整数変数を説明します．
整数値をそのまま保持する[ネイティブ整数変数](../advanced/native-integer.md)も利用できます．
## 整数変数
PyQBPPは**整数変数**をサポートしており,内部的には複数のバイナリ変数を用いて実装されています.
整数値の表現には従来のバイナリエンコーディングが使用されます.
$n$個のバイナリ変数$x_0, x_1, \ldots, x_{n-1}$があるとします.
これらの変数は,以下の線形式を用いて$0$から$2^n-1$までのすべての整数を表現できます:
$$
\begin{aligned}
2^0x_0+2^1x_1+\cdots 2^{n-1}x_{n-1}
\end{aligned}
$$
定数オフセット$l$を導入し,$x_{n-1}$の係数を任意の値$d$に置き換えると,次のようになります:
$$
\begin{aligned}
l+2^0x_0+2^1x_1+\cdots +2^{n-2}x_{n-2}+dx_{n-1}
\end{aligned}
$$
この式は$l$から$l+2^{n-1}+d-1$までのすべての整数を表現できます.
このエンコーディングに基づき,整数範囲が$[l,u]$の変数は,以下を満たす適切な$n$と$d$（$1\leq d\leq 2^{n-1}$）を選ぶことで構成できます:
$$
\begin{aligned}
u &= l+2^{n-1}+d-1
\end{aligned}
$$
以下のプログラムは整数変数の定義方法を示しています.
```{literalinclude} /../programFiles/pythonPrograms/basic/integer-variables-and-linear-systems-program1.py
:language: python
:caption: integer-variables-and-linear-systems-program1.py
```
整数変数は **`between=`** キーワード引数を使って定義し,変数がとりうる整数範囲を指定します.
**`qbpp.var("name", between=(min, max))`** は,指定された `name` を持つ整数変数 **`Expr`** オブジェクトを作成し,バイナリ変数でエンコードされた線形式を表現します.
プログラムの出力は以下の通りです.
```{include} /../programFiles/markDown/basic/integer-variables-and-linear-systems.md
:start-after:
:end-before:
```
> **注意**
> 整数変数に必要なバイナリ変数の数は,その範囲に対して対数的に増加します.
> `max - min` が大きい場合,QUBOのサイズが増大するため,広い整数範囲はできる限り避けるべきです.
## 連立方程式を解くためのQUBO定式化
PyQBPPは,変数を整数変数として表現することで連立方程式を解くことができます.
例として,解が $x=4$,$y=6$ である以下の方程式に対するQUBO定式化を構築します.
$$
\begin{aligned}
x + y = 10\\
2x+4y = 28
\end{aligned}
$$
これらの方程式を解くために,範囲 $[0,10]$ の整数変数 $x$ と $y$ を定義し,それぞれ4つのバイナリ変数でエンコードします:
$$
\begin{aligned}
x = x_0 +2x_1 +4x_2 +3x_3\\
y = y_0 +2y_1 +4y_2 +3y_3
\end{aligned}
$$
以下の各ペナルティ式は,対応する方程式が満たされるとき,かつそのときに限り最小値0をとります:
$$
\begin{aligned}
f(x,y) &= (x+y-10)^2\\
&=(x_0 +2x_1 +4x_2 +3x_3+y_0 +2y_1 +4y_2 +3y_3-10)^2\\
g(x,y) &= (2x+4y -28)^2\\
&= (2\cdot(x_0 +2x_1 +4x_2 +3x_3)+4\cdot( y_0 +2y_1 +4y_2 +3y_3)-28)^2
\end{aligned}
$$
したがって,結合式
$$
\begin{aligned}
h(x,y) &= f(x,y) +g(x,y)
\end{aligned}
$$
は,両方の方程式が同時に満たされるとき,正確にその最小値0を達成します.
## PyQBPP プログラム
以下のプログラムはQUBO式 $h(x,y)$ を構築し,それを解いて結果の $x$ と $y$ の値をデコードします.
```{literalinclude} /../programFiles/pythonPrograms/basic/integer-variables-and-linear-systems-program2.py
:language: python
:caption: integer-variables-and-linear-systems-program2.py
```
これにより,`x`,`y`,および制約式 `f`,`g`,`f.body`,`g.body` の値が解と整合していることが確認できます.
> **注意**
> PyQBPPの `qbpp.constrain(expr, equal=n)` の `n` には,整数のほか式（`Var`/`Term`/`Expr`）も指定できます.
> penalty は `sqr(expr - n)`,body は `expr` になります（例: `qbpp.constrain(x + y, equal=2*z)`）.
> 演算子形式の `式 == 式` は直接サポートされていないため,式同士の等価制約には
> `equal=` か `qbpp.constrain(expr1 - expr2, equal=0)` を使ってください.
> 詳細は[**比較制約**](../advanced/comparison-operators.md)で説明しています.
:::