概要
$N$種類の商品にはそれぞれ価値$v$とコスト$c$が設定されている。ナップザックに、$N$種類の商品を1つずつ選んで詰める。詰めた商品の価値の総和が最大になるようにしたい。ただし、ナップザックに詰められる商品のコストの総和は$C$以下でなければならない。すなわち、決められたコストを上回らないように、選んだ商品の価値合計を最大化する問題である。
$N$種類の商品にはインデックス$\alpha = 1, 2, \cdots, N$をつける。ナップザックに入れる商品に対応するQUBO変数には$1$を、入れない商品に対応するQUBO変数には$0$を割り当てれば、上記問題は以下のように書ける。
{\rm max} \,\, \sum _{\alpha=1} ^{N} v_{\alpha} q_{\alpha} \quad {\rm s.t.} \,\, \sum _{\alpha=1} ^{N} c_{\alpha} q_{\alpha} \leq C
イジングモデルの構築
イジングモデルで、問題を定式化する。イジングモデルのハミルトニアンは、選択した商品の価値合計を最大化する項と、コストが$C$以下になるようにする制約条件の項の2つに分けられる。
H = H_{value} + H_{cost}
$H_{value}$および$H_{cost}$の具体的な数式を構築する。まずは価値合計を最大化する項だが、こちらは先に記述した価値合計の数式をそのまま使って以下のように書ける。
H_{value} = - \sum _{\alpha=1} ^{N} v_{\alpha} q_{\alpha} , \quad q_{\alpha} \in \{ 0, 1 \}
価値合計が最大のとき、$H_{value}$は最小値を取る。
一方、制約条件の項を記述するためには、工夫が必要になる。まず、選択した商品のコスト合計は$\sum_{\alpha} c_{\alpha} q_{\alpha}$と書けるが、これが$C$と等しくなるような制約条件であれば、以下のようなハミルトニアンを構築すればよい。
H_{cost} = \lambda \left( C - \sum _{\alpha=1} ^{N} c_{\alpha} q_{\alpha} \right) ^{2}
しかし、実際に解きたい問題では、必ずしも$C$に等しい必要はなく、例えばコスト合計値が$C-1$であっても、価値合計が最大であればそれが最適解となる。
したがって、「コスト合計値が$C$以下」という制約条件を定式化しなければならない。これを実現するために、補助変数$y_{k} \in \{ 0, 1 \}, \,\, k = 1, 2, \cdots C$を導入して、
\begin{align}
H_{cost} &= \lambda \left[ \left( 1 - \sum _{k} y_{k} \right) ^{2} + \left( \sum _{k} k y_{k} - \sum _{\alpha} c_{\alpha} q_{\alpha} \right) ^{2} \right] \\
&= \lambda \left( H_{cost} ^{(1)} + H_{cost} ^{(2)} \right)
\end{align}
と書ける。パラメータ$\lambda$は正の定数である。
式展開
これらの式を展開し、
H = \sum _{i} h_{i} q_{i} + \sum _{i < j} J_{ij} q_{i} q_{j}
の形に帰着させる。まずは$H_{cost} ^{(1)}$を展開する。
\begin{align}
H_{cost} ^{(1)} &= \left( 1 - \sum _{k} y_{k} \right) ^{2} \\
&= 1 - 2 \sum _{k} y_{k} + \left( \sum _{k} y_{k} \right) ^{2} \\
&= 1 - 2 \sum _{k} y_{k} + \sum _{k} y_{k}^{2} + 2\sum _{k < l} y_{k} y_{l} \\
&= 1 - \sum _{k} y_{k} + 2\sum _{k < l} y_{k} y_{l}
\end{align}
2行目から3行目の式変形で、以下を利用した。
\left( \sum _{i} a_{i} x_{i} \right) ^{2} = \sum _{i} a_{i}^{2} x_{i}^{2} + 2 \sum _{i < j} a_{i}a_{j} x_{i}x_{j}
また、3行目から4行目の式変形で$y_{k}^{2} = y_{k}, \,\, y_{k} \in \{ 0, 1 \}$を使った。
次に、$H_{cost}^{(2)}$を展開する。
\begin{align}
H_{cost} ^{(2)} &= \left( \sum _{k} k y_{k} - \sum _{\alpha} c_{\alpha} q_{\alpha} \right) ^{2} \\
&= \left( \sum _{k} k y_{k} \right) ^{2} + \left( \sum _{\alpha} c_{\alpha} q_{\alpha} \right) ^{2} - 2 \sum _{k} \sum _{\alpha} kc_{\alpha} y_{k} q_{\alpha} \\
&= \sum _{k} k^{2} y_{k} + 2\sum _{k < l} kly_{k}y_{l} + \sum _{\alpha} c_{\alpha} ^{2} q_{\alpha} + 2\sum _{\alpha < \beta} c_{\alpha} c_{\beta} q_{\alpha} q_{\beta} - 2 \sum_{k} \sum _{\alpha} kc_{\alpha} y_{k} q_{\alpha}
\end{align}
ここで、$q_{\alpha} ^{2} = q_{\alpha}$を使った。
\frac{H_{cost}}{\lambda } = 1 + \sum _{k} (k^{2} - 1) y_{k} + 2\sum _{k < l} (kl + 1) y_{k}y_{l} + \sum _{\alpha} c_{\alpha} ^{2} q_{\alpha} + 2\sum _{\alpha < \beta} c_{\alpha} c_{\beta} q_{\alpha} q_{\beta} - 2 \sum_{k} \sum _{\alpha} kc_{\alpha} y_{k} q_{\alpha}
ここで、$y_{k}$もQUBO変数の一種として見なす。すなわち、
y_{k} \longrightarrow q_{\alpha}, \quad \alpha = k + N
とすれば、ハミルトニアンは以下のようになる。
\begin{align}
\frac{H_{cost}}{\lambda} &= 1 + \sum _{k=1} ^{C} (k^{2} - 1) q_{k + N} + \sum _{\alpha=1} ^{N} c_{\alpha} ^{2} q_{\alpha}\\
& + 2\sum _{k=1} ^{C-1} \sum _{l=k+1}^{C} (kl + 1) q_{k+N}q_{l+N} + 2\sum _{\alpha = 1} ^{N-1} \sum _{\beta = \alpha + 1} ^{N} c_{\alpha} c_{\beta} q_{\alpha} q_{\beta} - 2 \sum_{k=1} ^{C} \sum _{\alpha=1} ^{N} kc_{\alpha} q_{k+N} q_{\alpha}
\end{align}
パラメータ調整
制約条件の項にかかるパラメータ$\lambda$を決める必要がある。これを適当に決めた場合には、得られる最適解は期待したものにはならない。例えば、$1 \gg \lambda$となるようなパラメータを選んだ場合には、価値合計を最大化する項が強くなり、制約条件の項が相対的に弱くなる。これはすなわち、最適解として得たQUBO変数が、制約条件を満たさない可能性が高いことを意味する。一方で、$1 \ll \lambda$を満たすパラメータを選んだ場合、制約条件の項が強くなり制約条件が優先的に満たされるようになるが、一方で価値合計が最大とはならない可能性が高くなる。
最適解を与えるQUBO変数列$\{ q_{\alpha} \}$を用意し、適当に選んだQUBO変数$q_{k} \in \{ q_{\alpha} \}$を1つだけ変更することを考える。このとき、価値合計は$\left| \Delta H_{value} \right| = c_{k} $だけ小さくなる。制約条件の項が全体のハミルトニアンに影響するためには、以下を満たすようにパラメータを選べばよい。
0 \leq max(c_{\alpha}) \leq \lambda