kivantium活動日記

プログラムを使っていろいろやります

制約付き最適化問題をD-Waveと同じ方法で解く

まだ古典コンピュータで消耗してるの?

イジングモデルとQUBO

D-Waveが提供しているのは量子アニーリングを使った量子コンピュータです。
量子アニーリング方式では次の形の最適化問題を高速に解くことができます。
 {\displaystyle \text{min.}\ \sum_{i \lt j} J_{ij} s_{i} s_{j} - \sum_{i=1}^{N} h_i s_i }
ここで J_{ij}, h_{i} \in \mathbb{R} s_i \in \{1, -1\}です。

1と-1よりは0と1の方が扱いやすいので、 x_i = (s_i+1)/2と変数変換して得られる以下のQUBO (Quadratic unconstrained binary optimization) という形に変形してから使うことが多いようです。
 {\text{min. } \displaystyle \sum_{i=1}^{N} c_i x_i + \sum_{i=1}^{N} \sum_{j=1}^{i} q_{ij} x_i x_j }

制約付き最適化問題とQUBO

QUBOでは変数間の制約がありませんでしたが、実際には  x_1+x_2=1 のような制約が必要になることがあります。
その場合、最適化したい関数 f(x)と十分大きい \lambda > 0を使って
 {\displaystyle \text{min.} f(x) + \lambda (x_1+x_2-1)^2 }
を解けば、(実行可能解が存在するなら)最小値を取るときには自動的に制約が満たされることになるので、QUBOの形で制約付き最適化問題が解けることになります。
なお、QUBOには x_i^2 の項がありませんが、 x_i は0または1なので  x_i^2=x_i が成り立ち、2乗の項が出てきてもQUBOの形に変形することができます。

qbsolv

qbsolv はD-Waveが開発しているQUBOのソルバです。
設定すればD-Waveの実機上でも動かせるようですが、デフォルトではローカル環境でのシミュレーションを使って解く設定になっているようです。
ここではコマンドライン環境を使います。

コンパイル

git clone https://github.com/dwavesystems/qbsolv.git
cd qbsolv
mkdir build; cd build
cmake ..
make

qbsolvは.quboファイルを読み込んでその解を出力します。
.quboファイルの仕様は以下の通りです。(READMEより引用)

qbsolv "qubo" input file format

   A .qubo file contains data which describes an unconstrained
quadratic binary optimization problem.  It is an ASCII file comprised
of four types of lines:

1) Comments - defined by a "c" in column 1.  They may appear
    anywhere in the file, and are otherwise ignored.

2) One program line, which starts with p in the first column.
    The program line must be the first non-comment line in the file.
    The program line has six required fields (separated by space(s)),
    as in this example:

  p   qubo  topology   maxNodes   nNodes   nCouplers

    where:
  p         the problem line sentinel
  qubo      identifies the file type
  topology  a string which identifies the topology of the problem
            and the specific problem type.  For an unconstrained problem,
            target will be "0" or "unconstrained."   Possible, for future
            implementations, valid strings might include "chimera128"
            or "chimera512" (among others).
  maxNodes   number of nodes in the topology.
  nNodes     number of nodes in the problem (nNodes <= maxNodes).
            Each node has a unique number and must take a value in the
            the range {0 - (maxNodes-1)}.  A duplicate node number is an
            error.  The node numbers need not be in order, and they need
            not be contiguous.
  nCouplers  number of couplers in the problem.  Each coupler is a
            unique connection between two different nodes.  The maximum
            number of couplers is (nNodes)^2.  A duplicate coupler is
            an error.

3) nNodes clauses.  Each clause is made up of three numbers.  The
            numbers are separated by one or more blanks.  The first two
            numbers must be integers and are the number for this node
            (repeated).  The node number must be in {0 , (maxNodes-1)}.
            The third value is the weight associated with the node, may be
            an integer or float, and can take on any positive or negative
            value, or zero.

4) nCouplers clauses.  Each clause is made up of three numbers.  The
            numbers are separated by one or more blanks.  The first two
            numbers must be different integers and are the node numbers
            for this coupler.  The two values (i and j) must have (i < j).
            Each number must be one of the nNodes valid node numbers (and
            thus in {0, (maxNodes-1)}).  The third value is the strength
            associated with the coupler, may be an integer or float, and can
            take on any positive or negative value, but not zero.  Every node
            must connect with at least one other node (thus must have at least
            one coupler connected to it).

Here is a simple QUBO file example for an unconstrained QUBO with 4
nodes and 6 couplers.  This example is provided to illustrate the
elements of a QUBO benchmark file, not to represent a real problem.

        | <--- column 1
        c
        c  This is a sample .qubo file
        c  with 4 nodes and 6 couplers
        c
        p  qubo  0  4  4  6
        c ------------------
        0  0   3.4
        1  1   4.5
        2  2   2.1
        3  3   -2.4
        c ------------------
        0  1   2.2
        0  2   3.4
        1  2   4.5
        0  3   -2
        1  3   4.5678
        2  3   -3.22

最短路問題をQUBOで解く

制約付き最適化問題の例として、最短路問題をQUBOに変換して解きます。
良い子のみんなはダイクストラなどを使いましょう。

f:id:kivantium:20180617163419p:plain
今回考えるグラフ

最短路問題を最適化問題として解く時は、辺  e_i を通るときは  x_i=1、通らない時は  x_i=0 として、重みの和  \sum w_i x_i が最小になるようにする問題と見ます。( w_i は辺  e_i の重み)
これだけだと何も辺を選ばないのが最適になってしまうので、辺の選び方が経路になるように各頂点に制約を加えます。

  •  v_0 からは1辺が出ていくので  x_0 + x_2 = 1
  •  v_1 に入って来る辺の数と出て行く辺の数は等しいので  x_0 - x_1 = 0
  •  v_2 には1辺が入ってくるので  x_1 + x_2 = 1

 (w_0, w_1, w_2) = (1, 1, 3) とすると、この最短路問題を解くためのQUBOは、
 {\displaystyle \text{min. } x_0 + x_1 + 3x_2 + \lambda \{(x_0+x_2-1)^2 + (x_0-x_1)^2+(x_1+x_2-1)^2\} }
となります。
 \lambda=100として、 x_i^2=x_iに気をつけながら変形すると
 {\displaystyle \text{min. } x_0 + x_1 +  (-197)x_3 + (-200) x_0x_1+200x_0x_2+200x_1x_2 }
となります。(間違ってたらごめんなさい)

これを.quboファイルにすると

p  qubo  0  3  3  3
c ------------------
0  0   1
1  1   1
2  2   -197
c ------------------
0  1   -200
0  2   200
1  2   200

となります。

./qbsolv -i test.qubo

のように実行すると

3 bits,  find Min, SubMatrix= 47, -a o, timeout=2592000.0 sec
110
-198.00000 Energy of solution
0 Number of Partitioned calls, 1 output sample 
 0.02363 seconds of classic cpu time

となり、 (x_0, x_1, x_2) = (1, 1, 0) という正しい答えが得られました。

 w_0=3にすると答えが

3 bits,  find Min, SubMatrix= 47, -a o, timeout=2592000.0 sec
001
-197.00000 Energy of solution
0 Number of Partitioned calls, 1 output sample 
 0.02023 seconds of classic cpu time

に変わるので正しそうな挙動をしています。

特定商取引法に定められた事項は請求により遅滞なく提供する