Solving Expressions

QUBO++ provides three solvers for QUBO/HUBO expressions:

  • Easy Solver
    • Runs a heuristic algorithm based on simulated annealing.
    • Runs in parallel on multicore CPUs using Intel Threading Building Blocks (oneTBB).
    • Does not guarantee optimality.
  • Exhaustive Solver
    • Explores all possible solutions.
    • Guarantees optimality of the returned solution.
    • Is computationally feasible only when the number of binary variables is about 30–40 or fewer.
    • If a CUDA GPU is available, GPU acceleration is automatically enabled alongside CPU threads.
  • ABS3 Solver
    • A high-performance solver that uses CUDA GPUs and multicore CPUs.
    • Does not guarantee optimality, but is much more powerful than the Easy Solver.
    • If no GPU is available, falls back to CPU-only mode.

The Easy Solver and Exhaustive Solver are used in the following steps:

  1. Create a solver object, qbpp::easy_solver::EasySolver or qbpp::exhaustive_solver::ExhaustiveSolver.
  2. Call the search() member function on the solver object, optionally passing parameters as an initializer list. It returns a qbpp::Sol object that stores the obtained solution.

Easy Solver

To use the Easy Solver, include the header file qbpp/easy_solver.hpp. It is defined in the namespace qbpp::easy_solver.

We use the following expression $f(a,b,c,d)$ as an example:

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

Clearly, this expression attains its minimum value $f=0$ when $a+2b+3c+4d=5$. Therefore, it has two optimal solutions, $(a,b,c,d)=(0,1,1,0)$ and $(1,0,0,1)$.

In the following program, expression f is created using the symbolic computation. Note that the function qbpp::sqr() returns the square of the argument. We then construct an instance of the class qbpp::easy_solver::EasySolver by passing f to its constructor. Before doing so, f must be simplified for binary variables by calling simplify_as_binary(). The constructor returns an EasySolver object named solver. Since we know that the optimal value is $f=0$, we pass the target energy to search() as an initializer list. Calling the search() member function on solver returns a solution instance sol of class qbpp::Sol, which is printed using std::cout.

#include <qbpp/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);
  auto sol = solver.search({{"target_energy", 0}});
  std::cout << sol << std::endl;
}

The output of this program is as follows:

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}}

One of the optimal solutions is correctly output.

Exhaustive Solver

To use the Exhaustive Solver, include the header file qbpp/exhaustive_solver.hpp. It is defined in the namespace qbpp::exhaustive_solver.

We construct an instance solver of the class qbpp::exhaustive_solver::ExhaustiveSolver by passing f to its constructor. Calling the search() member function on solver returns a solution instance sol of class qbpp::Sol, which is printed using std::cout. Since the Exhaustive Solver explores all possible assignments, it is guaranteed that sol stores an optimal solution.

#include <qbpp/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;
}

The output of this program is as follows:

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

All optimal solutions can be obtained by setting the best_energy_sols parameter as follows:

  auto solver = qbpp::exhaustive_solver::ExhaustiveSolver(f);
  auto sol = solver.search({{"best_energy_sols", 1}});

The output is as follows:

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

Furthermore, all solutions including non-optimal ones can be obtained by setting the all_sols parameter as follows:

  auto solver = qbpp::exhaustive_solver::ExhaustiveSolver(f);
  auto sol = solver.search({{"all_sols", 1}});

The output is as follows:

(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}}

The Exhaustive Solver is very useful for analyzing small expressions and for debugging.

ABS3 Solver

To use the ABS3 Solver, include the header file qbpp/abs3_solver.hpp. It is defined in the namespace qbpp::abs3.

The ABS3 Solver is a high-performance solver that uses CUDA GPUs and multicore CPUs. If no GPU is available, it automatically falls back to CPU-only mode.

Usage involves two steps:

  1. Create an qbpp::abs3::ABS3Solver object for the expression.
  2. Call the search() member function, passing parameters as an initializer list. It returns the obtained solution.
#include <qbpp/qbpp.hpp>
#include <qbpp/abs3_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::abs3::ABS3Solver(f);
  auto sol = solver.search({{"time_limit", 5.0}, {"target_energy", 0}, {"enable_default_callback", 1}});
  std::cout << sol << std::endl;
}

The output of this program is as follows:

TTS = 0.000s Energy = 0
0:{{a,0},{b,1},{c,1},{d,0}}

For details on parameters, callbacks, multiple solution collection, and solution hints, see ABS3 Solver.

式の求解

QUBO++はQUBO/HUBO式を解くための3つのソルバーを提供しています：

  • Easy Solver
    • シミュレーテッドアニーリングに基づくヒューリスティックアルゴリズムを実行します。
    • Intel Threading Building Blocks (oneTBB)を使用してマルチコアCPU上で並列に動作します。
    • 最適性は保証されません。
  • Exhaustive Solver
    • すべての可能な解を探索します。
    • 返される解の最適性が保証されます。
    • バイナリ変数の数が約30～40以下の場合にのみ計算が現実的です。
    • CUDA GPUが利用可能な場合、CPUスレッドと並行してGPUアクセラレーションが自動的に有効になります。
  • ABS3 Solver
    • CUDA GPUとマルチコアCPUを活用する高性能ソルバーです。
    • 最適性は保証されませんが、Easy Solverよりはるかに強力です。
    • GPUが利用できない場合はCPUのみモードにフォールバックします。

Easy SolverとExhaustive Solverは以下のステップで使用します：

  1. ソルバーオブジェクト（qbpp::easy_solver::EasySolverまたはqbpp::exhaustive_solver::ExhaustiveSolver）を作成します。
  2. ソルバーオブジェクトの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}\]

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

以下のプログラムでは、シンボリック計算を使って式 f を作成します。 関数qbpp::sqr()は引数の2乗を返すことに注意してください。 次に、f をコンストラクタに渡してクラス qbpp::easy_solver::EasySolver のインスタンスを構築します。 その前に、simplify_as_binary()を呼び出して f をバイナリ変数用に簡約化する必要があります。 コンストラクタはsolverという名前の EasySolver オブジェクトを返します。 最適値が $f=0$ であることがわかっているので、search() にターゲットエネルギーを初期化子リストとして渡します。 solver のsearch()メンバ関数を呼び出すと、クラスqbpp::Solの解インスタンスsolが返され、std::cout で出力されます。

#include <qbpp/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);
  auto sol = solver.search({{"target_energy", 0}});
  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}}

最適解の1つが正しく出力されています。

Exhaustive Solver

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

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

#include <qbpp/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}}

すべての最適解は best_energy_sols パラメータを設定することで以下のように取得できます：

  auto solver = qbpp::exhaustive_solver::ExhaustiveSolver(f);
  auto sol = solver.search({{"best_energy_sols", 1}});

出力は以下のとおりです：

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

さらに、非最適解を含むすべての解は all_sols パラメータを設定することで以下のように取得できます：

  auto solver = qbpp::exhaustive_solver::ExhaustiveSolver(f);
  auto sol = solver.search({{"all_sols", 1}});

出力は以下のとおりです：

(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}}

Exhaustive Solverは、小さな式の解析やデバッグに非常に有用です。

ABS3 Solver

ABS3 Solverを使用するには、ヘッダファイルqbpp/abs3_solver.hppをインクルードします。 名前空間qbpp::abs3で定義されています。

ABS3 Solverは、CUDA GPUとマルチコアCPUを活用する高性能ソルバーです。 GPUが利用できない場合は、自動的にCPUのみモードにフォールバックします。

使用方法は以下の2ステップです：

  1. 式に対してqbpp::abs3::ABS3Solverオブジェクトを作成します。
  2. search()メンバ関数を呼び出します。パラメータは初期化子リストとして渡します。得られた解が返されます。
#include <qbpp/qbpp.hpp>
#include <qbpp/abs3_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::abs3::ABS3Solver(f);
  auto sol = solver.search({{"time_limit", 5.0}, {"target_energy", 0}, {"enable_default_callback", 1}});
  std::cout << sol << std::endl;
}

このプログラムの出力は以下のとおりです：

TTS = 0.000s Energy = 0
0:{{a,0},{b,1},{c,1},{d,0}}

パラメータ、コールバック、複数解の収集、ヒント解の詳細についてはABS3 Solverをご覧ください。