ソルバーについて

Easy Solver と Exhaustive Solver、ABS3 Solver を用いた式の解法

QUBO++ では、QUBO/HUBO 式に対して Easy Solver と Exhaustive Solver、ABS3 Solver を提供しています。

PyQBPP では、QUBO/HUBO 式に対して Easy Solver と Exhaustive Solver、ABS3 Solver を提供しています。

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 オブジェクトが返されます。

注釈: qbpp::Sol は可変な値型です — 他の QUBO++ の値と同じく代入・コピー・更新が できます（エイリアスとコピーを参照）。 ソルバーオブジェクト（EasySolver、ExhaustiveSolver、ABS3Solver）は 重い計算リソースを所有しているため コピー不可 です（コピーコンストラクタが 削除されています）。新しいソルバーが必要な場合は別途作成してください。

Easy Solver

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

以下\(f(a, b, c, d)\)の式を例として使用します：

\[ f(a, b, c, d)=(a+2b+3c+4d-5)^2 \]

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

次のプログラムでは、式 f をシンボリック計算によって作成しています。
関数 qbpp::sqr() は、引数の二乗を返すことに注意してください。

その後、クラス qbpp::easy_solver::EasySolver のインスタンスを、f をコンストラクタに渡して生成します。
その前に、simplify_as_binary() を呼び出して、f をバイナリ変数用に簡約しておく必要があります。

コンストラクタは solver という名前の EasySolver オブジェクトを返します。
最適値が\(f=0\)であることが分かっているため、target_energy() メンバ関数を呼び出して、目標エネルギーを\(0\)に設定します。

solver に対して search() メンバ関数を呼び出すと、クラス qbpp::Sol の解インスタンス sol が返されます。
これを std::cout を用いて出力します。

solving-expressions-program1.cpp
#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::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 内で定義されています。

クラス qbpp::exhaustive_solver::ExhaustiveSolver のインスタンス solver を、f をコンストラクタに渡して生成します。
solver に対して search() メンバ関数を呼び出すと、クラス qbpp::Sol の解インスタンス sol が返され、std::cout を用いて出力されます。

Exhaustive Solver はすべての可能な割り当てを探索するため、sol には最適解が格納されることが保証されています。

solving-expressions-program2.cpp
#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::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}}

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

ABS3 Solver

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

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

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

  • 式に対してqbpp::abs3::ABS3Solverオブジェクトを作成します。

  • qbpp::abs3::Paramsオブジェクトを作成し、探索オプションを設定します。

  • search()メンバ関数を呼び出します。得られた解が返されます。

solving-expressions-program3.cpp
#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::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
Sol(energy=0, a=0, b=1, c=1, d=0)

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

  1. ソルバオブジェクトEasySolver または ExhaustiveSolverを作成します。

  2. ソルバオブジェクトの search() メンバ関数を呼び出します。
    返り値として、得られた解を格納する Sol オブジェクトが返されます。

注釈: 返される解は可変オブジェクトです。別の変数に代入すると エイリアス が 作られます（Python の参照セマンティクス）。独立した深いコピーが欲しい場合は qbpp.Sol(other_sol) を使ってください。詳細は エイリアスとコピー を参照してください。 ソルバーオブジェクトは重い計算リソースを所有しているためコピーすべきでは ありません。必要があれば新しいソルバーを作成してください。

Easy Solver

以下\(f(a, b, c, d)\)の式を例として使用します：

\[ f(a, b, c, d)=(a+2b+3c+4d-5)^2 \]

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

次のプログラムでは、式 f をシンボリック計算によって作成しています。
関数 sqr() は、引数の二乗を返すことに注意してください。

その後、クラス EasySolver のインスタンスを、f をコンストラクタに渡して生成します。
その前に、simplify_as_binary() を呼び出して、f をバイナリ変数用に簡約しておく必要があります。

最適値が\(f=0\)であることが分かっているため、target_energy() メンバ関数を呼び出して、目標エネルギーを\(0\)に設定します。

solver に対して search() メソッドを呼び出すと、クラス Sol の解インスタンス sol が返されます。

solving-expressions-program1.py
import pyqbpp as qbpp

a = qbpp.var("a")
b = qbpp.var("b")
c = qbpp.var("c")
d = qbpp.var("d")
f = qbpp.sqr(a + 2 * b + 3 * c + 4 * d - 5)
print("f =", f.simplify_as_binary())

solver = qbpp.EasySolver(f)
sol = solver.search(target_energy=0)
print(sol)

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

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

クラス ExhaustiveSolver のインスタンス solver を、f をコンストラクタに渡して生成します。
solver に対して search() メンバ関数を呼び出すと、クラス Sol の解インスタンス sol が返されます。

Exhaustive Solver はすべての可能な割り当てを探索するため、sol には最適解が格納されることが保証されています。

solving-expressions-program2.py
import pyqbpp as qbpp

a = qbpp.var("a")
b = qbpp.var("b")
c = qbpp.var("c")
d = qbpp.var("d")
f = qbpp.sqr(a + 2 * b + 3 * c + 4 * d - 5)
f.simplify_as_binary()

solver = qbpp.ExhaustiveSolver(f)
sol = solver.search()
print(sol)

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

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

すべての最適解は、search_optimal_solutions() メンバ関数を次のように呼び出すことで取得できます：

sols = solver.search_optimal_solutions()
for i, sol in enumerate(sols):
    print(f"({i}) {sol}")

出力は次のとおりです：

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

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

ABS3 Solver

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

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

  • 式に対してABS3Solverオブジェクトを作成します。

  • ソルバーオブジェクトのメソッドを使って探索オプションを設定します。

  • search()メソッドを呼び出します。得られた解が返されます。

solving-expressions-program3.py
import pyqbpp as qbpp

a = qbpp.var("a")
b = qbpp.var("b")
c = qbpp.var("c")
d = qbpp.var("d")
f = qbpp.sqr(a + 2 * b + 3 * c + 4 * d - 5)
f.simplify_as_binary()

solver = qbpp.ABS3Solver(f)
sol = solver.search(time_limit=5.0, target_energy=0)
print(sol)

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

TTS = 0.000s Energy = 0
Sol(energy=0, a=0, b=1, c=1, d=0)

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