🕸️

QUBO++入門:QUBO++とは

2024/12/23に公開

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モデルの生成
    スピン変数(-1/+1)を使用したIsingモデルの生成が可能です.

  • HUBOモデルの変換
    高次の項を含むHUBO(High-Order Unconstrained Binary Optimization)モデルを等価なQUBOモデルに変換する関数を備えています.これにより,HUBO問題をQUBO問題に変換し解くことも可能です.

QUBO問題とは

QUBO問題とは,0または1の値を取る2値変数を用いた2次式の中で,その式の値(エネルギー値とも呼ばれます)を最小化する変数の割り当てを求める問題です.このエネルギー値という概念は物理現象に由来しています.具体的には,次のような4変数を含む関数f(a,b,c,d)はQUBOの2次式となります.

\begin{aligned} f(a,b,c,d) &= (a+b+c+d-3)(a+b+c+d-4) \\ &= 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 \end{aligned}

式を展開し整理するときに,2値変数の二乗は一乗と等しい,例えば,a^2=aが成り立つことを用いています.この関数f(a,b,c,d)は,その定義から次の条件を満たすときに最小エネルギー値0をとります:

  • 4つの変数のうち3つが1の場合
  • または,4つ全てが1の場合
    したがって,これらの条件を満たす変数の割り当てが,この関数f 対応するQUBO問題の最適解となります.

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()を呼び出します.また,fstd::coutで出力し,内容を確認することができます.

このfを引数としてExhaustive Solverのオブジェクトを作成します.続いて,すべての最適解を出力するために,メンバ関数search_optimal_solutions()を呼び出し,その結果をsolに格納します.最後に,このsolstd::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は,n変数を持つQUBO式に対して,全2^n通りの解を網羅的に探索し,それぞれのエネルギー値を計算します.そのため,nが大きくなると計算時間が急激に増加し,現実的な時間内で処理を終えるためには,変数の個数nは30~40程度が上限となります.

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++情報

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