# 整数変数と連立方程式の解法

## 整数変数について
:::{container} prog-cpp
QUBO++ は整数変数をサポートしており、これらは内部的には複数のバイナリ変数を用いて実装されています。 
:::
:::{container} prog-python
PyQBPP は整数変数をサポートしており、これらは内部的には複数のバイナリ変数を用いて実装されています。
::: 
整数値の表現には、従来のバイナリエンコーディングが使用されます。

$n$ 個のバイナリ変数 $x_0,\cdots,x_{n-1}$ があるとします。  
これらの変数を用いることで、次の線形表現により $0$ から $2^n-1$ までのすべての整数を表すことができます：

$$
2^0x_0+\cdots+2^{n-2}x_{n-2}+2^{n-1}x_{n-1}
$$

さらに、定数オフセット $l$ を導入し、$x_{n-1}$ の係数を任意の値 $d$ に置き換えると、次のように書けます：

$$
l+2^0x_0+\cdots+2^{n-2}x_{n-2}+dx_{n-1}
$$
 
この式は、$l$ から $l+2^{n-1}+d-1$ までのすべての整数を表すことができます。
このエンコーディングに基づき、整数範囲 $[l, u]$ を持つ変数は、$n$ および $d$
（ $1 \leq d \leq 2^{n-1}$ ）を適切に選ぶことで、次を満たすように構築できます：

$$
u=l+2^{n-1}+d-1
$$

<hr>


:::{container} prog-cpp
次の 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")` 関数は、指定した名前を持つ `qbpp::VarInt` オブジェクトを生成します。  
このオブジェクトは、バイナリ変数によってエンコードされた線形式を表します。

このプログラムは、次の式を出力します：

```{include} ../../programFiles/markDown/basic/integer-variables-and-linear-systems-program.md
:start-after: <!-- begin: 整数変数について -->
:end-before: <!-- end: 整数変数について -->
```
:::


:::{container} prog-python
次の PyQBPP プログラムは、整数変数の定義方法を示しています。

```{literalinclude} ../../programFiles/pythonPrograms/basic/integer-variables-and-linear-systems-program1.py
:language: python
:caption: integer-variables-and-linear-systems-program1.py
```

整数変数は`between()` 関数を使って定義し、変数がとりうる整数範囲を指定します。  
この演算子により、その変数が取り得る整数範囲を指定します。

`var_int("name")` 関数は、指定した名前を持つ `VarIntCore` オブジェクトを生成し、`between(var_int("name"), min, max)` はバイナリ変数でエンコードされた線形式を表す `VarInt` オブジェクトを作成します。
このプログラムは、次の式を出力します：

```{include} ../../programFiles/markDown/basic/integer-variables-and-linear-systems-program.md
:start-after: <!-- begin: 整数変数について -->
:end-before: <!-- end: 整数変数について -->
```
:::



<hr>

**WARNING**  

整数変数に必要なバイナリ変数の数は、その取り得る範囲に対して対数的に増加します。  
$u-l$ が大きくなると QUBO のサイズも増大するため、可能な限り広い整数範囲は避けるべきです。


## QUBOを用いて連立方程式を解く
:::{container} prog-cpp
QUBO++ は、変数を整数変数として表現することで、連立方程式を解くことができます。  
:::
:::{container} prog-python
PyQBPP は、変数を整数変数として表現することで、連立方程式を解くことができます。  
:::
例として、解が $x=4$ および $y=6$ である次の方程式を考えます：

$$
x+y&=10,\\
2x+4y&=28.
$$

これらの方程式を解くために、整数範囲 $[0, 10]$ を持つ整数変数 $x$ および $y$ を定義します。  
それぞれは 4 個のバイナリ変数によってエンコードされます：

$$
x&=x_0+2x_1+4x_2+3x_3,\\
y&=y_0+2y_1+4y_2+3y_3.
$$

次の各ペナルティ式は、対応する方程式が満たされる場合に限り、最小値 0 を取ります：

$$
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(x_0+2x_1+4x_2+3x_3)+4(y_0+2y_1+4y_2+3y_3)-28)^2.
$$

したがって、これらを組み合わせた式

$$
h(x, y)=f(x, y)+g(x, y)
$$ 

は、両方の方程式が同時に満たされる場合に正確に最小値 0 を達成します。


:::{container} prog-cpp
### QUBO++ program

次の 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
```

まず、範囲  $[0, 10]$ を持つ `qbpp::VarInt` オブジェクト `x` および `y` を定義します。
`qbpp::Expr` オブジェクト `f` は制約 `x + y == 10` を表します。  
内部的には、これは QUBO 式 `qbpp::sqr(x + y - 10)` と等価です。

同様に、`g` は制約 `2 * x + 4 * y == 28` を表します。  
結合式 `h = f + g` は、両方の方程式を同時にエンコードします。

`h` を用いて Easy Solver のインスタンスを生成し、最適解はすべての制約を満たすため、目標エネルギーを 0 に設定します。  
`search()` を呼び出すと、すべてのバイナリ変数の最適な割り当てを格納した `qbpp::Sol` オブジェクト `sol` が返されます。

最後に、`sol`、`sol(x)`、`sol(y)`、`sol(f)`、`sol(g)`、`sol(*f)`、`sol(*g)` の値を出力します。

ここで：

- `f`：制約 `x + y = 10` を強制するペナルティ式。  
  したがって、方程式が満たされる場合に限り `sol(f) = 0` となります。
- `*f`：線形式 `x + y`。  
  したがって、`sol(*f)` は実際に評価された `x + y` の値を返します。

`g` および `*g` についても同様です。

このプログラムは、次の結果を出力します：

```{include} ../../programFiles/markDown/basic/integer-variables-and-linear-systems-program.md
:start-after: <!-- begin: QUBO++ program -->
:end-before: <!-- end: QUBO++ program -->
```

これにより、`x`、`y`、および制約式 `f`、`g`、`*f`、`*g` の値が、解と整合していることを確認できます。
:::



:::{container} prog-python
### PyQBPP program

次の 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
```

まず、範囲  $[0, 10]$ を持つ `VarInt` オブジェクト `x` および `y` を定義します。
`Expr` オブジェクト `f` は制約 `x + y == 10` を表します。  
内部的には、これは QUBO 式 `sqr(x + y - 10)` と等価です。

同様に、`g` は制約 `2 * x + 4 * y == 28` を表します。  
結合式 `h = f + g` は、両方の方程式を同時にエンコードします。

`h` を用いて Easy Solver のインスタンスを生成し、最適解はすべての制約を満たすため、目標エネルギーを 0 に設定します。  
`search()` を呼び出すと、すべてのバイナリ変数の最適な割り当てを格納した `Sol` オブジェクト `sol` が返されます。

最後に、`sol`、`sol(x)`、`sol(y)`、`sol(f)`、`sol(g)`、`sol(*f)`、`sol(*g)` の値を出力します。

ここで：

- `f`：制約 `x + y = 10` を強制するペナルティ式。  
  したがって、方程式が満たされる場合に限り `sol(f) = 0` となります。
- `f.body`：線形式 `x + y`。  
  したがって、`sol(f.body)` は実際に評価された `x + y` の値を返します。

`g` および `g.body` についても同様です。

このプログラムは、次の結果を出力します：

```{include} ../../programFiles/markDown/basic/integer-variables-and-linear-systems-program.md
:start-after: <!-- begin: QUBO++ program -->
:end-before: <!-- end: QUBO++ program -->
```

これにより、`x`、`y`、および制約式 `f`、`g`、`*f`、`*g` の値が、解と整合していることを確認できます。
:::

<hr>

**WARNING**
:::{container} prog-cpp
QUBO++ では、`==` 演算子は「左辺が式、右辺が整数」の場合にのみサポートされています。  
:::
:::{container} prog-python
PyQBPP では、`==` 演算子は「左辺が式、右辺が整数」の場合にのみサポートされています。  
:::
`integer == expression` や `expression == expression` の形式の比較はサポートされていません。  

詳細は [比較演算子](https://hi-qubo.com/docs/advanced/comparison-operators.html) を参照してください。