🕸️

QUBO++入門:整数を扱う(つるかめ算)

2025/01/06に公開

QUBO++の整数変数

QUBO++では整数変数を扱うことができます.一つの整数変数は複数の二値変数を用いて実装されておりその下限値と上限値を指定する必要があります.例えば次のソースコードでは関数qbpp::var_int()を用いてabをそれぞれ[1,10][-10,10]の範囲の整数値をとる変数として生成しています.

#include "qbpp.hpp"

int main() {
  auto a = 1 <= qbpp::var_int("a") <= 10;
  auto b = -10 <= qbpp::var_int("b") <= 10;

  std::cout << "a = " << a << std::endl;
  std::cout << "b = " << b << std::endl;
}

このコードにより、整数変数を表すqbpp::VarIntオブジェクトabが生成されます.このプログラムをコンパイルして実行すると次のような出力が得られます.

a = 1 +a[0] +2*a[1] +4*a[2] +2*a[3]
b = -10 +b[0] +2*b[1] +4*b[2] +8*b[3] +5*b[4]

これらの式はabを実装するためのQUBO式を表しています.aは4つの二値変数a[0]a[1]a[2]a[3]を用いて実装されており全て0のときは1で全て1のときは10となります.これら4つの二値変数により[1,10]の範囲の整数を表すことができます.同様にbは5つの二値変数を用いており[-10,10]の範囲の整数を表すことができます.

整数変数は複数の二値変数の一次式として実現されています.定数項を下限値として二値変数を加算していきます.その際係数を1, 2, 4, 8, ...と倍々にします.定数項と係数の合計が上限値と一致した場合は終了し超えた場合は最後の係数を調整します.

例えば[1,10]の整数値をとる整数変数aの場合次のように二値変数とその係数が決定されます.

a = 1 下限値1
a = 1 + a[0] 上限値2
a = 1 + a[0] +2*a[1] 上限値4
a = 1 + a[0] +2*a[1] + 4*a[2] 上限値8
a = 1 + a[0] +2*a[1] + 4*a[2] + 8*a[3] 上限値16で超える
a = 1 + a[0] +2*a[1] + 4*a[2] + 2*a[3] 上限値10に調整

つるかめ算を解くQUBO++プログラム

つるかめ算を解くQUBO式を構築します.問題として,つるとかめが合わせて5匹おり,足の数の合計が16であるとします.つるをx羽,かめをy匹とすると,次の連立方程式が立てられます.

\begin{align*} x+y &= 5 \\ 2x+4y &= 16 \end{align*}

これを解くQUBO++プログラムは次のようになります.

#include "qbpp.hpp"
#include "qbpp_exhaustive_solver.hpp"

int main() {
  auto x = 0 <= qbpp::var_int("x") <= 5;
  auto y = 0 <= qbpp::var_int("y") <= 5;
  std::cout << "x = " << x << std::endl;
  std::cout << "y = " << y << std::endl;

  auto c1 = x + y == 5;
  auto c2 = 2 * x + 4 * y == 16;
  c1.simplify_as_binary();
  c2.simplify_as_binary();
  std::cout << "c1 = " << c1 << std::endl;
  std::cout << "c2 = " << c2 << std::endl;

  auto f = c1 + c2;
  f.simplify_as_binary();
  std::cout << "f = " << f << std::endl;

  auto solver = qbpp::exhaustive_solver::ExhaustiveSolver(f);
  auto sol = solver.search();
  std::cout << "sol = " << sol << std::endl;
  std::cout << "x = " << sol.get(x) << std::endl;
  std::cout << "y = " << sol.get(y) << std::endl;
}

このプログラムでは,整数変数xyを生成しています.これらはそれぞれ[0,5]の範囲の整数値をとることができます.範囲の下限値と上限値は二重不等号を用いて指定します.

次に,連立方程式を制約式として生成します.c1c2はそれぞれ,等式x + y = 52x + 4y = 16を表します.これらはQUBO式のクラスqbpp::Exprのオブジェクトで,等式を満たすときに値が0となり,満たさない場合に1以上の値を持つよう設計されています.その後,c1c2を簡単化して表示しています.

QUBO式fc1c2の和として生成されたqbpp::Exprのオブジェクトです.この式をさらに簡単化し,ExhaustiveSolverに渡して最適解を求めます.最適解はsolに格納され,solが保持するxyの値をメンバ関数get()を用いて取得し表示します.

このプログラムを実行すると次の出力が得られます.

x = x[0] +2*x[1] +2*x[2]
y = y[0] +2*y[1] +2*y[2]
c1 = 25 -9*x[0] -16*x[1] -16*x[2] -9*y[0] -16*y[1] -16*y[2] +4*x[0]*x[1] +4*x[0]*x[2] +2*x[0]*y[0] +4*x[0]*y[1] +4*x[0]*y[2] +8*x[1]*x[2] +4*x[1]*y[0] +8*x[1]*y[1] +8*x[1]*y[2] +4*x[2]*y[0] +8*x[2]*y[1] +8*x[2]*y[2] +4*y[0]*y[1] +4*y[0]*y[2] +8*y[1]*y[2]
c2 = 256 -60*x[0] -112*x[1] -112*x[2] -112*y[0] -192*y[1] -192*y[2] +16*x[0]*x[1] +16*x[0]*x[2] +16*x[0]*y[0] +32*x[0]*y[1] +32*x[0]*y[2] +32*x[1]*x[2] +32*x[1]*y[0] +64*x[1]*y[1] +64*x[1]*y[2] +32*x[2]*y[0] +64*x[2]*y[1] +64*x[2]*y[2] +64*y[0]*y[1] +64*y[0]*y[2] +128*y[1]*y[2]
f = 281 -69*x[0] -128*x[1] -128*x[2] -121*y[0] -208*y[1] -208*y[2] +20*x[0]*x[1] +20*x[0]*x[2] +18*x[0]*y[0] +36*x[0]*y[1] +36*x[0]*y[2] +40*x[1]*x[2] +36*x[1]*y[0] +72*x[1]*y[1] +72*x[1]*y[2] +36*x[2]*y[0] +72*x[2]*y[1] +72*x[2]*y[2] +68*y[0]*y[1] +68*y[0]*y[2] +136*y[1]*y[2]
sol = 0:{{x[0],0},{x[1],1},{x[2],0},{y[0],1},{y[1],1},{y[2],0}}
x = 2
y = 3

この結果から,x = 2y = 3という正しい解が得られていることが確認できます.

QUBO++で等値演算子==の実現法

QUBO++では等値演算子==がサポートされています.この演算子を使用する場合,左辺はQUBO式,右辺は整数でなければなりません.左辺のQUBO式をf,右辺の整数をnとすると,f = nを満たす変数の割り当てが存在するときに0となるQUBO式をこの演算子は返します.数式で表すと,次のようなQUBO式を返します.

(f-n)^2

このQUBO式は,f = nを満たす場合には0となり,f \neq nの場合には1以上の値をとります.
例えば,先のQUBO++のプログラムでx + y == 5と記述された場合には,次のようにQUBO式が導出されます.

x + y == 5 = (x + y - 5) * (x + y - 5) 
           = (x[0] +2*x[1] +2*x[2] +y[0] +2*y[1] +2*y[2] -5)^2
           = 25 -9*x[0] -16*x[1] -16*x[2] -9*y[0] -16*y[1] -16*y[2] +4*x[0]*x[1] +4*x[0]*x[2] +2*x[0]*y[0] +4*x[0]*y[1] +4*x[0]*y[2] +8*x[1]*x[2] +4*x[1]*y[0] +8*x[1]*y[1] +8*x[1]*y[2] +4*x[2]*y[0] +8*x[2]*y[1] +8*x[2]*y[2] +4*y[0]*y[1] +4*y[0]*y[2] +8*y[1]*y[2]

このQUBO式は,x + y == 5を満たすように二値変数x[0], x[1], x[2], y[0], y[1], y[2]に値が割り当てられたときに0となります.逆に,条件を満たさない場合には1以上の値をとります.

このように,等値演算子==はQUBO++における制約式の実現に非常に有用です.

まとめ

  • QUBO++の整数変数
    整数変数は,上限値や下限値を指定して次のように生成します.
  auto a = 1 <= qbpp::var_int("a") <= 10;
  auto b = -10 <= qbpp::var_int("b") <= 10;

これにより,整数変数を表すqbpp::VarIntオブジェクトが生成されます.

  • 整数変数の実装
    整数変数は,複数の二値変数を用いて次のように実装されています.
a = 1 +a[0] +2*a[1] +4*a[2] +2*a[3]
b = -10 +b[0] +2*b[1] +4*b[2] +8*b[3] +5*b[4]
  • 等値演算子 ==
    等値演算子を用いることで,「QUBO式 == 整数値」の形式で等式が成り立つとき,最適解が0となるQUBO式を得ることができます.
  auto c1 = x + y == 5;
  auto c2 = 2 * x + 4 * y == 16;
  • Exhaustive Solverによる最適解の探索
    search()メンバ関数を用いて最適解を1つ求めます.複数の最適解がある場合でも,そのうちの任意の1つが返されます.
  auto sol = solver.search();
  • 解の整数値の取得
    得られた解に対して,get()メンバ関数を整数変数qbpp::VarIntオブジェクトとともに使用すると,対応する整数値を取得できます.
  std::cout << "x = " << sol.get(x) << std::endl;
  std::cout << "y = " << sol.get(y) << std::endl;

QUBO++情報

広島大学コンピューティングラボ
設定によりコメント欄が無効化されています