Easy Solver および Exhaustive Solver を使用した式解決

QUBO++ は、QUBO/HUBO 式に対してイージーソルバー と網羅的ソルバー を提供します。
これらは、Intel Threading Building Blocks (oneTBB) を使用して、マルチコア CPU 上で並行して実行されます。

簡易ソルバー
- シミュレーテッドアニーリングに基づくヒューリスティックアルゴリズムを実行します。
- 最適解を保証しません。
網羅的ソルバー
- 全ての可能な解を探索します。
- 返される解の最適性を保証します。
- 計算上実行可能なのは、二値変数の数が約30～40個以下の場合に限られる。

両ソルバーは次の2段階で利用されます：

ソルバーオブジェクトを作成します（qbpp::easy_solver::EasySolverまたはqbpp::exhaustive_solver::ExhaustiveSolver）。
ソルバーオブジェクトのメンバsearch()関数を呼び出す。これにより、得られた解を格納するオブジェクトqbpp::Solが返される。

Easy Solver

Easy Solverを使用するには、ヘッダーファイルをqbpp_easy_solver.hppインクルードする。これは名前空間で定義されているqbpp::easy_solver。

例として次の式 $f(a,b,c,d)$ を使用します:

\[\begin{aligned} f(a,b,c,d,e) &= (a+2b+3c+4d-5)^2 \end{aligned}\]

明らかに、この式は最小値 $f=0$ を $a+2b+3c+4d=5$ のときに達成します。したがって、2つの最適解、$(a,b,c,d)=(0,1,1,0)$ と $(1,0,0,1)$ があります。

以下のプログラムでは、式 f は記号計算を用いて作成される。関数は引数のqbpp::sqr()二乗を返すことに注意せよ。次に、クラス qbpp::easy_solver::EasySolver のインスタンスを構築する。その前に、 f をコンストラクタに渡すことでクラスインスタンスを構築する。その前に、 f を呼び出して二進変数用に簡略化するsimplify_as_binary()必要がある。コンストラクタは EasySolver オブジェクトを返しますsolver。最適値が $f=0$ であることがわかっているため、メンバtarget_energy()関数を呼び出して目標エネルギーを $0$ に設定します。メンバsearch()関数を呼び出すと solver を呼び出すと、qbpp::Solクラスのsol解インスタンスが返され、 std::cout.

#include "qbpp.hpp"
#include "qbpp_easy_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 = qbpp::sqr(a + 2 * b + 3 * c + 4 * d - 5);
  std::cout << "f = " << f.simplify_as_binary() << std::endl;
  auto solver = qbpp::easy_solver::EasySolver(f);
  solver.target_energy(0);
  auto sol = solver.search();
  std::cout << sol << std::endl;
}

このプログラムの出力は以下の通りです:

f = 25 -9*a -16*b -21*c -24*d +4*a*b +6*a*c +8*a*d +12*b*c +16*b*d +24*c*d
0:{{a,1},{b,0},{c,0},{d,1}}

最適解の一つが正しく出力されている。

網羅的ソルバー

網羅的ソルバーを使用するには、ヘッダーファイルをqbpp_exhaustive_solver.hppインクルードします。
これは名前空間で定義されていますqbpp::exhaustive_solver。

クラスのsolverインスタンスqbpp::exhaustive_solver::ExhaustiveSolverを構築するには、 f そのコンストラクタに渡すことで構築します。メンバsearch()関数を呼び出すと solver を呼び出すと、qbpp::Solクラスのsol解インスタンスが返され、 std::coutによって出力されます。網羅的ソルバーは全ての可能な割り当てを探索するため、 sol が最適解を格納することが保証されます。

#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 = qbpp::sqr(a + 2 * b + 3 * c + 4 * d - 5);
  f.simplify_as_binary();
  auto solver = qbpp::exhaustive_solver::ExhaustiveSolver(f);
  auto sol = solver.search();
  std::cout << sol << std::endl;
}

このプログラムの出力は以下の通りです:

0:{{a,0},{b,1},{c,1},{d,0}}

すべての最適解はメンバーsearch_optimal_solutions()関数によって以下のように取得できます:

  auto sol = solver.search_optimal_solutions();

出力は以下の通りです:

(0) 0:{{a,0},{b,1},{c,1},{d,0}}
(1) 0:{{a,1},{b,0},{c,0},{d,1}}

さらに、非最適解を含む全ての解はメンバー関数 search_all_solutions()によって以下のように取得できます:

 auto sol = solver.search_all_solutions();

出力は以下の通りです：

(0) 0:{{a,0},{b,1},{c,1},{d,0}}
(1) 0:{{a,1},{b,0},{c,0},{d,1}}
(2) 1:{{a,0},{b,0},{c,0},{d,1}}
(3) 1:{{a,0},{b,1},{c,0},{d,1}}
(4) 1:{{a,1},{b,0},{c,1},{d,0}}
(5) 1:{{a,1},{b,1},{c,1},{d,0}}
(6) 4:{{a,0},{b,0},{c,1},{d,0}}
(7) 4:{{a,0},{b,0},{c,1},{d,1}}
(8) 4:{{a,1},{b,1},{c,0},{d,0}}
(9) 4:{{a,1},{b,1},{c,0},{d,1}}
(10) 9:{{a,0},{b,1},{c,0},{d,0}}
(11) 9:{{a,1},{b,0},{c,1},{d,1}}
(12) 16:{{a,0},{b,1},{c,1},{d,1}}
(13) 16:{{a,1},{b,0},{c,0},{d,0}}
(14) 25:{{a,0},{b,0},{c,0},{d,0}}
(15) 25:{{a,1},{b,1},{c,1},{d,1}}

網羅的ソルバーは、小さな式の解析やデバッグに非常に有用です。

最終更新日: 2025.12.26