5. QUBO #

5.1. 導入 #

QUBO (Quadratic Unconstrained Binary Optimization) もしくは二次無制約二値最適化とは以下の特徴を持った問題クラスのことである．

変数が \(0\)-\(1\) 整数変数 (バイナリ変数) である．
制約条件がない．

¹\(x\in\mathbb{B}=\{0,1\}\) に対して，\(x^2=x\) であるから，一次の項は暗に二次の項に含まれている．

目的関数が (高々) 二次 ¹ ¹\(x\in\mathbb{B}=\{0,1\}\) に対して，\(x^2=x\) であるから，一次の項は暗に二次の項に含まれている．である．

これら前提は問題の表現能力という意味では非常に狭いものであるが， QUBO でない問題についても以下の工夫によって，QUBO へと帰着することができる．

連続変数 (や整数変数) は浮動点小数によって近似的に実現する．
制約条件を考慮する場合は目的関数にペナルティとして追加する．
三次以上は式変形によって二次に帰着させる．

QUBO への帰着が可能という意味で，「巡回セールスマン問題」「最大カット問題」「グラフ彩色問題」「数分割問題」「充足可能問題」「クラスタリング」など，多くの組合せ最適化問題を QUBO で扱うことができる．

QUBO を問題表現の標準形であるかのように扱う背景としては，QUBO のための専用計算機の存在がある．これら計算機の実証や研究は，新たな計算方式の開拓という点で重要な側面がある．

Tip

Ising 模型を基礎とした専用計算機では変数の値を \(\pm 1\) で扱うため，これら二値を取りうる変数 \(\tilde{x}\) を特に Ising 変数と呼ぶことがある． \(x\in\mathbb{B}=\{0,1\}\) との関係は次の線形な関係のため，これによる本質的な差異はない．

(1)#\[\tilde{x} = 2x - 1\]

またそれら専用計算機では目的関数を系のエネルギーに対応させるため，最適化は常に最小化として扱われる．このために QUBO でも，最大化問題については負符号を全体につけて最小化問題として説明がなされやすい．

5.2. QUBO への帰着 #

QUBO への帰着方法について，その方針を以下に述べる．なお専用計算機によってはそのアーキテクチャを反映した定式化が必要とされることもあり，下記の一般論をそのまま適用できるとは限らない．

注釈

QUBO への帰着が必要になるだけ，計算のパフォーマンスは落ちてしまう．また有限の計算資源の下では，これら帰着は問題規模に応じて近似的なものにとどまらざるを得ない．このため QUBO を扱う専用機の使用を検討する場合には，なるべくこれらの帰着が必要ない問題を選定することが肝要である．

5.2.1. 連続変数を考慮する場合 #

QUBO は二値しか扱えないため，整数変数や連続変数をあくまでも QUBO で扱いたい場合には，それら変数を必要な精度だけ二進展開することになる．これは桁の数だけ変数を追加で必要になり，問題表現のために問題規模が増えることになる．

5.2.2. 制約条件を考慮する場合 #

QUBO は次の二次形式の目的関数 \(f_Q(x)\) のみからなる．

(2)#\[\mathrm{Minimize\colon}~ f_Q(x) = \sum_{i,j}Q_{i,j}x_ix_j\]

このため制約条件 \(\{g_k(x)= 0\}_k\) を加味できないが，「制約条件がどれだけ満たされていないか」というように視点を変えて，次式のようにペナルティ項として目的関数の一部に含めれば，間接的に制約条件を考慮できる．

(3)#\[\mathrm{Minimize\colon}~ f_{Q,\mu}(x) = f_Q(x) + \sum_k \mu_k [g_k(x)]^2\]

ここで \(\{\mu_k\}_k\) はそれぞれ正値で，制約条件の破れの度合いを相対的に定めるハイパーパラメータである．値を大きくとるほど，制約条件を満たす最適解が得られやすくなるが，必要以上に大き過ぎると最適化計算が数値的に難しくなる可能性がある．逆に値を小さくとるほど，この関係は逆になって，実行可能解ですらない解が得られる可能性が高くなる．このように多目的最適化となっており，このハイパーパラメータをどの程度にすべきかは経験的に決めることになる．

注釈

以上は制約条件式として等式の制約式を考慮する場合だった．これに対して不等式の制約式を考慮する場合は何らかの方法によって等式制約に直して，上記の議論に帰着させることになる．

単純な方法としてはスラック変数を導入して等式制約に直すことである．つまり \(g(x)\geq 0\) なる制約式一つに対してスラック変数 \(s(\geq 0)\) を一つ使って，\(g(x) = s\) と等式制約に直すのである．このこと自体はよくあるテクニックだが，QUBO への帰着を徹底する必要性から，計算資源を浪費してしまうことがある．というのも，スラック変数は制約条件によっては一般に二値とは限らないから，QUBO に帰着させるために，二進展開のための追加の変数が必要になるからである．それ故にこの方針は多くの場合で得策ではない．

このような背景から不等式制約は QUBO では相性が悪いとされているが，この問題を回避するための手法が提案 [2] されている．当該文献については [3] なども参照されたい．

5.2.3. 高次項を考慮する場合 #

QUBO は三次以上の高次項を扱えない．このためこれら高次項を扱う場合には，新たな変数とペナルティとしての制約条件を追加して二次に帰着させる．

例えば三次項 \(x_1x_2x_3\) があった場合，新たな変数 \(x_4\) を用いて \(x_2x_3 = x_4\) なる等式制約を考える．このとき元の目的関数 \(f_Q\) を次のように修正する．

(4)#\[\mathrm{Minimize\colon}~ f_{Q,\mu}(x) = f_Q(x) + \mu g(x_2,x_3,x_4) ~~ (\mu > 0)\]

追加するペナルティ項は次を満たす高々二次の関数とする．

(5)#\[\begin{split}g(x_2,x_3,x_4) = \begin{cases} 0 & (x_2x_3 = x_4), \\ c(>0) & (x_2x_3 \neq x_4) \end{cases}\end{split}\]

ここで \(g(x_2,x_3,x_4)=x_2x_3-x_4\) という単純なものではない．この場合には例えば \(g(0,0,1) = -1\) となってしまうからである．つまりペナルティ関数にならない．

また \(g\) は一意ではなく，いろいろな可能性がある．それらのうち，一つを採用すればよい．一例として次を挙げる．

(6)#\[g(x_2,x_3,x_4) = 3x_4 + x_2x_3 - 2x_2x_4 -2x_3x_4\]

5.3. 例題 #

QUBO 形式での定式化の例を以下に挙げる．なお，これらは必ずしも QUBO 形式でなければならないというわけではなく，場合によっては線形に定式化することもできる．

5.3.1. 巡回セールスマン問題 #

\(N\) 都市の巡回セールスマン問題について，各都市間の移動距離 \(D_{c_1,c_2}\) の総和を最小化する目的関数は， QUBO 形式で次のように定式化できる．

(7)#\[\begin{split}& \mathrm{Minimize\colon}~ f_{D,\mu}(x) = f_D(x) + f_{\mu}(x), \\ & f_D(x) = \sum_{c_1,c_2}\sum_{n=1}^N D_{c_1,c_2} x_{c_1,n} x_{c_2,n+1}, \\ & f_{\mu}(x) = \mu_1 \sum_{c\in C} \left(\sum_{n=1}^N x_{c,n} - 1\right)^2 + \mu_2 \sum_{n=1}^N \left(\sum_{c\in C} x_{c,n} - 1\right)^2\end{split}\]

ここで変数 \(x_{c,n}\) は，都市 \(c\) を \(n\) 番目に巡回する場合に \(1\) をとり，そうでない場合に \(0\) をとるものとする．

ペナルティ項にある制約条件式について，第一項は「都市 \(c\) を一度だけ巡回すること」を意味し，第二項は「\(n\) 番目に巡回する都市は唯一つであること」を意味する．これらペナルティ項が負にならないよう，二乗していることに注意する．

5.3.2. 最大カット問題 #

グラフの辺 \((i,j)\) についての重みが \(G_{i,j}\) で与えられる最大カット問題は QUBO 形式で次のように定式化できる．但し \(\tilde{x}_i,\tilde{x}_j \in \{+1,-1\}\) である．

(8)#\[\mathrm{Minimize\colon}~ f_G(x) = -\frac{1}{2}\sum_{i<j} G_{i,j}(1-\tilde{x}_i\tilde{x}_j)\]

5.3.3. グラフ彩色問題 #

グラフ彩色問題とはグラフ \(G=(V,E)\) に対して，各頂点 \(v\in V\) や各辺 \(e\in E\) について，ある制約条件を満たした色の割り当てを決定する問題である．このとき使用する色の数を最小化するよう目的関数を設定することもある．

このようにグラフ彩色問題には様々な種類があるが，ここでは隣り合う頂点同士に異なる色を割り当てる問題 (頂点彩色問題) を例にしよう．

頂点彩色問題はそれ自身目的関数がなく，「隣り合う頂点は異なる色にする」という制約条件と，「頂点には必ず色を割り当てる」という暗黙の制約条件からなる問題である．

この問題を解くための目的関数は QUBO 形式で次のように定式化できる．但し \(C\) は彩色に使用する色からなる集合である．

(9)#\[f_{\mu}(x) = \mu_1 \sum_{(v_1,v_2)\in E}\sum_{c\in C}x_{v_1,c}x_{v_2,c} + \mu_2 \sum_{v\in V} \left(\sum_{c\in C}x_{v,c} - 1\right)^2\]

ここで変数 \(x_{v,c}\) は頂点 \(v\) に色 \(c\) を割り当てるならば \(1\)，そうでないならば \(0\) をとるものとする．

目的関数は制約条件の違反を表すペナルティ項のみからなり，第一項は「隣り合う頂点は異なる色にする」なる制約条件，第二項は「頂点には必ず色を割り当てる」なる制約条件を意味する．

特に第一項は隣り合う頂点同士が同色のときにのみペナルティとして計上されていることを表している．

5.3.4. 数分割問題 #

大小比較可能な数を要素に持つ集合 \(N\) が与えられ，これを互いに素な二つの集合 \(N_1\) と \(N_2\) に分割したとする．

(10)#\[N = N_1\sqcup N_2\]

このとき，各々の集合内について総和の差 \(\Delta N\) が最小となるような分割方法を決定する問題を「数分割問題」(または単に分割問題) という．

(11)#\[\Delta N = \left|\sum_{n\in N_1} n - \sum_{n\in N_2} n\right|\]

この問題を解くための目的関数は QUBO 形式で次のように定式化できる．但し \(\tilde{x}_i \in \{+1,-1\}\) である．

(12)#\[\mathrm{Minimize\colon}~ f_N(x) = \left( \sum_{i=1}^{|N|} n_i\tilde{x}_i \right)^2\]

ここで各 \(n_i\) は \(N\) の要素を附番したときの \(i\) 番目の要素である．そして変数 \(\tilde{x}_i\) は \(i\) 番目の要素 \(n_i\) が，\(N_1\) に属するならば \(+1\)，\(N_2\) に属するならば \(-1\) を表すものとする．

QUBO

目次