QUBO++入門:QUBO++とは
QUBO++
QUBO++は,C++を使用してさまざまな組合せ最適化問題を等価なQUBO(Quadratic Unconstrained Binary Optimization)問題に変換し,その解を求めるためのツールです.その主な特徴は以下の通りです.
-
簡潔なC++17ベースの設計
基本的な3つのC++クラス,変数(qbpp::Var
),式(qbpp::Expr
),解(qbpp::Sol
)を使用します.これらを理解すれば,QUBO問題を扱うC++コードを簡単に作成できます. -
高い移植性
BoostやTBBなどの標準的なライブラリのみを利用しており,Linuxベースの多くの計算機で動作します.さらに,WindowsのWSLやmacOS(Intel版およびARM版のCPU)でも動作確認済みです. -
桁数制限のない整数
多倍長整数をサポートしており,式の定数項や係数として桁数制限のない値を使用できます. -
整数変数のサポート
整数変数を扱えるため,整数計画問題をQUBO形式で簡単に記述できます. -
多彩な演算子と関数
ベクトル演算を含む複雑な式を操作するための豊富な演算子と関数が用意されています. -
テストとデバッグのための組み込みソルバー
簡易的なソルバー(EasySolver)および全探索ソルバー(ExhaustiveSolver)の2種類を提供しています. -
並列処理による高速化
Intel® Threading Building Blocks (TBB) を活用したマルチスレッド処理で,可能な限り高速化を図っています. -
外部ソルバー対応
GPUベースのQUBOソルバー(ABS2)や商用MIPソルバー(Gurobi Optimizer)をQUBO++からQUBOソルバーとして呼び出すAPIを提供しています. -
Isingモデルの生成
スピン変数( )を使用したIsingモデルの生成が可能です.-1/+1 -
HUBOモデルの変換
高次の項を含むHUBO(High-Order Unconstrained Binary Optimization)モデルを等価なQUBOモデルに変換する関数を備えています.これにより,HUBO問題をQUBO問題に変換し解くことも可能です.
QUBO問題とは
QUBO問題とは,0または1の値を取る2値変数を用いた2次式の中で,その式の値(エネルギー値とも呼ばれます)を最小化する変数の割り当てを求める問題です.このエネルギー値という概念は物理現象に由来しています.具体的には,次のような4変数を含む関数
式を展開し整理するときに,2値変数の二乗は一乗と等しい,例えば,
- 4つの変数のうち3つが1の場合
- または,4つ全てが1の場合
したがって,これらの条件を満たす変数の割り当てが,この関数 対応するQUBO問題の最適解となります.f
QUBO++のプログラム
このQUBO問題を解くQUBO++プログラムは,次のように記述することができます.
#include "qbpp.hpp"
#include "qbpp_exhaustive_solver.hpp"
int main() {
auto a = qbpp::var("a");
auto b = qbpp::var("b");
auto c = qbpp::var("c");
auto d = qbpp::var("d");
auto f = (a + b + c + d - 3) * (a + b + c + d - 4);
f.simplify_as_binary();
std::cout << "f = " << f << std::endl;
auto solver = qbpp::exhaustive_solver::ExhaustiveSolver(f);
auto sol = solver.search_optimal_solutions();
std::cout << sol << std::endl;
}
QUBO++を使用する場合,ヘッダファイルqbpp.hpp
をインクルードします.今回は,QUBOソルバーであるExhaustive Solverを用いるため,qbpp_exhaustive_solver.hpp
もインクルードします.Exhaustive Solverは,全解探索を行うQUBOソルバーです.
まず,4つの変数 a,b,c,d
を関数qbpp::var
で定義します.この関数の引数は文字列で,変数を表示するときの名前に対応します.各変数の定義によって,QUBO++内部では変数に対応するクラスオブジェクトqbpp::Var
が作成されます.
次に,2次式 f を数式の形で定義しています.この f は,QUBO++内部ではクラスオブジェクトqbpp::Expr
です.式の定義から,a+b+c+d
の値が3または4のとき,f
の値は0となり,それ以外のときは1以上になります.このf
を2値変数として整理するため,メンバ関数simplify_as_binary()
を呼び出します.また,f
をstd::cout
で出力し,内容を確認することができます.
このf
を引数としてExhaustive Solverのオブジェクトを作成します.続いて,すべての最適解を出力するために,メンバ関数search_optimal_solutions()
を呼び出し,その結果をsol
に格納します.最後に,このsol
をstd::cout
に出力します.
このプログラムをコンパイルし実行すると,次のような出力が得られます.
f = 12 -6*a -6*b -6*c -6*d +2*a*b +2*a*c +2*a*d +2*b*c +2*b*d +2*c*d
0:0:{{a,0},{b,1},{c,1},{d,1}}
1:0:{{a,1},{b,0},{c,1},{d,1}}
2:0:{{a,1},{b,1},{c,0},{d,1}}
3:0:{{a,1},{b,1},{c,1},{d,0}}
4:0:{{a,1},{b,1},{c,1},{d,1}}
この出力結果から,a+b+c+d
が3または4の場合の5通りの解が正しく得られていることが確認できます.
すべての解を表示したい場合,search_optimal_solutions()
をsearch_all_solutions()
に変更します.これにより,16通りのすべての解が値の小さい順に表示されます.出力は以下の通りです.
f = 12 -6*a -6*b -6*c -6*d +2*a*b +2*a*c +2*a*d +2*b*c +2*b*d +2*c*d
0:0:{{a,0},{b,1},{c,1},{d,1}}
1:0:{{a,1},{b,0},{c,1},{d,1}}
2:0:{{a,1},{b,1},{c,0},{d,1}}
3:0:{{a,1},{b,1},{c,1},{d,0}}
4:0:{{a,1},{b,1},{c,1},{d,1}}
5:2:{{a,0},{b,0},{c,1},{d,1}}
6:2:{{a,0},{b,1},{c,0},{d,1}}
7:2:{{a,0},{b,1},{c,1},{d,0}}
8:2:{{a,1},{b,0},{c,0},{d,1}}
9:2:{{a,1},{b,0},{c,1},{d,0}}
10:2:{{a,1},{b,1},{c,0},{d,0}}
11:6:{{a,0},{b,0},{c,0},{d,1}}
12:6:{{a,0},{b,0},{c,1},{d,0}}
13:6:{{a,0},{b,1},{c,0},{d,0}}
14:6:{{a,1},{b,0},{c,0},{d,0}}
15:12:{{a,0},{b,0},{c,0},{d,0}}
一方,最適解を1つだけ得たい場合は,search_optimal_solutions()
をsearch()
に変更します.このメンバ関数は,最適解の中から任意に1つを選択して出力します.以下はその出力例です.
f = 12 -6*a -6*b -6*c -6*d +2*a*b +2*a*c +2*a*d +2*b*c +2*b*d +2*c*d
0:{{a,1},{b,1},{c,1},{d,0}}
Exhaustive Solver
QUBO++にバンドルされているExhaustive Solverは,
Exhaustive Solverは,作成したQUBO式が意図したエネルギー値を持つかどうかを確認するデバッグ用途として使用されることを想定しています.内部では,Intel® Threading Building Blocks (TBB) を活用したマルチスレッド処理により,高速化を実現しています.
まとめ
-
変数の作成:
qbpp::var
関数を使用して次のように変数を作成します.これにより,変数を表すqbpp::Var
オブジェクトaが生成されます.
auto a = qbpp::var("a");
-
多項式の記述:変数を用いて多項式を次のように記述します.これにより,式を表す
qbpp::Expr
オブジェクトfが生成されます.
auto f = (a + b + c + d - 3) * (a + b + c + d - 4);
-
多項式の整理:多項式を二値変数とみなして整理するには,
qbpp::Expr
クラスのsimplify_as_binary()
メンバ関数を使用します.この関数を呼び出すと,整理されたQUBO式が得られます.
f.simplify_as_binary();
-
式の表示式:式を表示するには,
std::cout
を使用します.
std::cout << "f = " << f << std::endl;
-
QUBO式の最適解の求解:整理されたQUBO式を引数として
ExhaustiveSolver
オブジェクトを作成します.
auto solver = qbpp::exhaustive_solver::ExhaustiveSolver(f);
-
全ての最適解の探索:全ての最適解を求めるには,
search_optimal_solutions()
メンバ関数を呼び出します.
auto sol = solver.search_optimal_solutions();
-
得られた解の表示:得られた解を表示するには,
std::cout
を使用します.
std::cout << sol << std::endl;
QUBO++情報
- QUBO++ツールとABS2 QUBO Solverの詳細情報:QUBO++に関する公式サイトです.ツールの特徴や使用方法,ABS2 QUBO Solverとの連携について詳しく説明されています.
- 【研究成果】組合せ最適化問題を解くためのプログラミング用ツールQUBO++を無償公開します:広島大学からの公式リリース情報です.QUBO++の開発背景や研究成果について記載されています.
- 利用条件:QUBO++は非商用利用や評価研究目的に限り無償で利用可能です.商用利用や定常的な業務での使用を希望する場合は,ライセンス契約が必要となります.