QUBOからMIPソルバーへの定式化の変換方法【個人的まとめ】

# はじめに
QUBOで表現した数理モデルをMIPソルバーで計算する必要がある場面があったので両者のモデルの変換方法をこの機会にまとめました。
この記事では全ての定式化を網羅せずに私が出会った定式化を順次まとめることにします。
[整数計画法による定式化入門(藤江哲也氏)](http://web.tuat.ac.jp/~miya/fujie_ORSJ.pdf)から数式を引用しています。
間違っていたり、より適した定式化があればコメントお願いします。

# 2次関数 (2次変数項)
$xy$のような2次項を1次にリダクションする方法について説明します。
QUBOでもMIPでも補助変数$z$を導入して$z=xy$と変換します。
変換に伴い$x, y, z$の間に$z=xy$の関係を満たすための制約条件を追加します。

| x | y | z |
|:-----------:|:------------:|:------------:|
| 0 | 0 | 0 |
| 1 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 1 | 1 |

QUBOの場合は上記の関係を満たさない場合はエネルギーが増加する項を追加します。
(※QUBOの場合、2次以下であればこの変換を行わなくても計算をすることが可能です。)

MIPの場合は上記の関係以外が成立しないような不等式を追加します。

## QUBO
この変換方法は[HOBOからQUBOへの変換](https://qiita.com/nori_autumn/items/2713bb3dc48663cb680b)の「置換による変換」でも説明しています。

### 変換前
```math
\begin{align}
xy\;\;\; (x, y \in \{0, 1\})
\end{align}
```

### 変換後
```math
\begin{align}
z &+ D(x, y, z) \\
D(x, y, z) &= xy - 2z(x+y) + 3z \\
(x, y, z &\in \{0, 1\})
\end{align}
```

## MIP
### 変換前
```math
\begin{align}
xy\;\;\; (x, y \in \{0, 1\})
\end{align}
```

### 変換後
```math
\begin{align}
z \\
x + y - z &\le 1 \\
-x + z &\le 0 \\
-y + z &\le 0 \\
(x, y, z &\in \{0, 1\})
\end{align}
```

$(x, y)=(1, 1)$となった場合は1つ目の不等式より$z=1$になる必要があります。
$(x, y)=(1, 0)$の場合は3つ目の不等式より$z=0$になる必要があります。
$(x, y)=(0, 1)$の場合は2つ目の不等式より$z=0$になる必要があります。
$(x, y)=(0, 0)$の場合は2,3つ目の不等式より$z=0$になる必要があります。

# 2次の等式制約
$xy=0$という2次の制約条件を考えます。
$(x, y)=(1, 1)$以外を取ることができます。

## QUBO
QUBOの場合は$xy$を加えるだけです。

```math
\begin{align}
xy\;\;\; (x, y \in \{0, 1\})
\end{align}
```

## MIP
$xy=1$となるのは$x=y=1$の場合だけです。
この場合は$x+y=2$となるので以下の不等式を追加します。

### 変換前
```math
\begin{align}
xy = 0
\end{align}
```

### 変換後
```math
\begin{align}
x + y \le 1
\end{align}
```

# または (その1)
$\boldsymbol{a}\cdot \boldsymbol{x}=b$または$\boldsymbol{a}\cdot \boldsymbol{x}=c$について考えます。
$\boldsymbol{x}$はある組みの変数をベクトルで表したもので$\boldsymbol{a}$は対応する係数になります。

## QUBO
$\boldsymbol{a}\cdot \boldsymbol{x}=b$と$\boldsymbol{a}\cdot \boldsymbol{x}=c$となる場合以外はエネルギーが増加すれば良いので次の式になります。

```math
\begin{align}
(\boldsymbol{a}\cdot \boldsymbol{x} - b) \cdot (\boldsymbol{a}\cdot \boldsymbol{x} - c)
\end{align}
```

## MIP
QUBOは2次項を扱えたので上記の式で良いのですが、MIPではこれを1次で表現する必要があります。
補助変数$y, z$と正の大きな数$M$(通称Big M)導入してこれを実現します。

### 変換前
```math
\begin{align}
\boldsymbol{a}\cdot \boldsymbol{x} = b \;\;\; OR \;\;\; \boldsymbol{a}\cdot \boldsymbol{x} = c
\end{align}
```

### 変換後
```math
\begin{align}
-Mz \le \boldsymbol{a}\cdot \boldsymbol{x} &- b \le M(1-y) \\
-M(1-z) \le \boldsymbol{a}\cdot \boldsymbol{x} &- c \le My \\
y + z &= 1 \\
y, z \in & \{0, 1\}
\end{align}
```

3番目の制約条件により$(y, z)=(1, 0), (0, 1)$の場合だけを考えれば良いです。
$(y, z)=(1, 0)$の場合、

```math
\begin{align}
0 \le \boldsymbol{a}\cdot \boldsymbol{x} &- b \le 0  \Leftrightarrow \boldsymbol{a}\cdot \boldsymbol{x} = b \\
-M \le \boldsymbol{a}\cdot \boldsymbol{x} &- c \le M
\end{align}
```

となります。
$M$を十分大きく取れば2つ目の不等式は常に成立します。

$(y, z)=(0, 1)$の場合、

```math
\begin{align}
Mz \le \boldsymbol{a}\cdot \boldsymbol{x} &- b \le M \\
0 \le \boldsymbol{a}\cdot \boldsymbol{x} &- c \le 0 \Leftrightarrow \boldsymbol{a}\cdot \boldsymbol{x} = c
\end{align}
```

となります。
$M$を十分大きく取れば1つ目の不等式は常に成立します。

以上よりいずれの場合も成立します。
Big Mを導入すると一般的に緩和解の質が悪くなるため計算速度・精度が悪くなるというデメリットもあるようです。
下の記事にそのあたりの説明を書いているのでよければ参照してください。
[整数計画問題の良い線形緩和について](https://qiita.com/nori_autumn/items/988cbc0ae3db8caa9398)

また1つの制約条件に対して2つの変数が追加されるため制約条件の個数が多いと変数の数が増加するというデメリットもあります。

# 最後に
To be continued...