QUBO++入門:整数を扱う(つるかめ算)
QUBO++の整数変数
QUBO++では整数変数を扱うことができます.一つの整数変数は複数の二値変数を用いて実装されておりその下限値と上限値を指定する必要があります.例えば次のソースコードでは関数qbpp::var_int()
を用いてa
とb
をそれぞれ
#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
オブジェクトa
とb
が生成されます.このプログラムをコンパイルして実行すると次のような出力が得られます.
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]
これらの式はa
とb
を実装するためのQUBO式を表しています.a
は4つの二値変数a[0]
,a[1]
,a[2]
,a[3]
を用いて実装されており全て0のときは1で全て1のときは10となります.これら4つの二値変数によりb
は5つの二値変数を用いており
整数変数は複数の二値変数の一次式として実現されています.定数項を下限値として二値変数を加算していきます.その際係数を1, 2, 4, 8, ...と倍々にします.定数項と係数の合計が上限値と一致した場合は終了し超えた場合は最後の係数を調整します.
例えば
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であるとします.つるを
これを解く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;
}
このプログラムでは,整数変数x
とy
を生成しています.これらはそれぞれ
次に,連立方程式を制約式として生成します.c1
とc2
はそれぞれ,等式qbpp::Expr
のオブジェクトで,等式を満たすときに値が0となり,満たさない場合に1以上の値を持つよう設計されています.その後,c1
とc2
を簡単化して表示しています.
QUBO式f
はc1
とc2
の和として生成されたqbpp::Expr
のオブジェクトです.この式をさらに簡単化し,ExhaustiveSolverに渡して最適解を求めます.最適解はsol
に格納され,sol
が保持するx
とy
の値をメンバ関数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
この結果から,
QUBO++で等値演算子==の実現法
QUBO++では等値演算子==
がサポートされています.この演算子を使用する場合,左辺はQUBO式,右辺は整数でなければなりません.左辺のQUBO式を
このQUBO式は,
例えば,先の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++情報
- QUBO++ツールとABS2 QUBO Solverの詳細情報:QUBO++に関する公式サイトです.ツールの特徴や使用方法,ABS2 QUBO Solverとの連携について詳しく説明されています.
- 【研究成果】組合せ最適化問題を解くためのプログラミング用ツールQUBO++を無償公開します:広島大学からの公式リリース情報です.QUBO++の開発背景や研究成果について記載されています.
- 利用条件:QUBO++は非商用利用や評価研究目的に限り無償で利用可能です.商用利用や定常的な業務での使用を希望する場合は,ライセンス契約が必要となります.