このページでは整数計画問題と呼ばれるNP完全・NP困難な問題をイジングモデルで表現する方法について述べます。
問題の定式化 #
今回イジングモデルで扱う整数計画問題は変数がバイナリ変数であるものです。
\(N\) 個のバイナリ変数からなるベクトル \(\boldsymbol{x}\) があります。 このとき、制約条件を表す \(\boldsymbol{S} \boldsymbol{x} = \boldsymbol{b}\) の式を満たし、かつ目的関数 \(\boldsymbol{c} \cdot \boldsymbol{x}\) の値を最大化するような \(\boldsymbol{x}\) を求める問題はNP困難です。
問題の具体例 #
食材
\(A\)
が50g,食材
\(B\)
が100gあります。
弁当
\(a\)
,弁当
\(b\)
,弁当
\(c\)
があり、それぞれの弁当の必要食材と利益は以下のようになっています。
弁当
\(a\)
,弁当
\(b\)
,弁当
\(c\)
はそれぞれ高々１つしかつくらないとき、得られる利益を最大化するような弁当の作り方を求めたいです。
ただし、食材は補充できないかつ無駄にできないので、食材
\(A\)
をちょうど50g,食材
\(B\)
をちょうど100g使う必要があります。
この問題を先ほどの式に当てはめてみましょう。
\(x_i\)
を弁当
\(i\)
をつくるとき1をとり,つくらないとき0をとるバイナリ変数とすると、
制約条件
のもとで、 目的関数
\[ \begin{pmatrix} 100\ 60\ 50 \end{pmatrix} \cdot \begin{pmatrix} x_1\ x_2\ x_3 \end{pmatrix} \]を最大化する問題になります。 この問題の答えは
\[ \begin{pmatrix} x_1\ x_2\ x_3 \end{pmatrix} = \begin{pmatrix} 0\ 1\ 1 \end{pmatrix} \]で、このとき最大の利益110円を達成します。
イジングモデルへの変形 #
\(\boldsymbol{x}\) の各変数はバイナリ変数であるので、 \(i\) 番目の要素を \(x_i\) としそのままスピンにあてはめます。
行列 \(\boldsymbol{S}\) の \(i\) 行 \(j\) 列の要素を \(S_{ij}\) , \(\boldsymbol{b}\) の \(i\) 個目の要素を \(b_i\) , \(\boldsymbol{c}\) の \(i\) 個目の要素を \(c_i\) とします。
A,Bを正の定数とします。 このとき、エネルギー関数は以下のようになります。
\[ H = H_A + H_B \] \[ H_A = A \sum_{j=1}^{m} \left( b_j - \sum_{i=1}^{N} S_{ji} x_{i} \right)^2 \] \[ H_B = - B \sum_{i=1}^{N} c_i x_i \]
エネルギー関数の最小化により問題が解けるのは何故か #
それぞれのエネルギー関数の各項はどのような制約を課しているでしょうか？
まず、 \(H_A\) は \(\boldsymbol{S} \boldsymbol{x} = \boldsymbol{b}\) という制約を表します。 \(H_A=0\) となる解が存在すれば、 \(\boldsymbol{S} \boldsymbol{x} = \boldsymbol{b}\) という制約を満たすことになります。
次に、 \(H_B\) は目的関数 \(\boldsymbol{c} \cdot \boldsymbol{x}\) を表し、 \(H_B\) が小さいほど目的関数の値は大きくなります。
ここで、目的関数の最小化よりも制約条件を遵守するために、 \(A\) と \(B\) は \(\frac{A}{B} \gtrsim N\) という関係を満たす必要があります。
参考文献 #
A. Lucas, “Ising formulations of many NP problems” (open access)