# ソルバーについて ## Easy Solver と Exhaustive Solver、ABS3 Solver を用いた式の解法 :::{container} prog-cpp QUBO++ では、QUBO/HUBO 式に対して Easy Solver と Exhaustive Solver、ABS3 Solver を提供しています。 ::: :::{container} prog-python 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 の使用手順 :::{container} prog-cpp 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` を用いて出力します。 ```{literalinclude} ../../programFiles/cppPrograms/basic/solving-expressions-program1.cpp :language: cpp :caption: solving-expressions-program1.cpp ``` このプログラムの出力は次のとおりです： ```{include} ../../programFiles/markDown/basic/solving-expressions-program.md :start-after: :end-before: ``` 最適解のうちの 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` には最適解が格納されることが保証されています。 ```{literalinclude} ../../programFiles/cppPrograms/basic/solving-expressions-program2.cpp :language: cpp :caption: solving-expressions-program2.cpp ``` このプログラムの出力は次のとおりです： ```{include} ../../programFiles/markDown/basic/solving-expressions-program.md :start-after: :end-before: ``` すべての最適解は、`search_optimal_solutions()` メンバ関数を次のように呼び出すことで取得できます： ```{include} ../../programFiles/markDown/basic/solving-expressions-program.md :start-after: :end-before: ``` 出力は次のとおりです： ```{include} ../../programFiles/markDown/basic/solving-expressions-program.md :start-after: :end-before: ``` さらに、最適でない解も含めたすべての解は、`search_all_solutions()` メンバ関数を次のように呼び出すことで取得できます： ```{include} ../../programFiles/markDown/basic/solving-expressions-program.md :start-after: :end-before: ``` 出力は次のとおりです： ```{include} ../../programFiles/markDown/basic/solving-expressions-program.md :start-after: :end-before: ``` 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()`メンバ関数を呼び出します。得られた解が返されます。 ```{literalinclude} ../../programFiles/cppPrograms/basic/solving-expressions-program3.cpp :language: cpp :caption: solving-expressions-program3.cpp ``` このプログラムの出力は以下の通りです： ```{include} ../../programFiles/markDown/basic/solving-expressions-program.md :start-after: :end-before: ``` パラメータ、コールバック、複数解の収集の詳細についてはABS3 Solverをご覧ください。 ::: :::{container} prog-python 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` が返されます。 ```{literalinclude} ../../programFiles/pythonPrograms/basic/solving-expressions-program1.py :language: python :caption: solving-expressions-program1.py ``` このプログラムの出力は次のとおりです： ```{include} ../../programFiles/markDown/basic/solving-expressions-program.md :start-after: :end-before: ``` 最適解のうちの 1 つが正しく出力されています。 ## Exhaustive Solver クラス `ExhaustiveSolver` のインスタンス `solver` を、`f` をコンストラクタに渡して生成します。 `solver` に対して `search()` メンバ関数を呼び出すと、クラス `Sol` の解インスタンス `sol` が返されます。 Exhaustive Solver はすべての可能な割り当てを探索するため、`sol` には最適解が格納されることが保証されています。 ```{literalinclude} ../../programFiles/pythonPrograms/basic/solving-expressions-program2.py :language: python :caption: solving-expressions-program2.py ``` このプログラムの出力は次のとおりです： ```{include} ../../programFiles/markDown/basic/solving-expressions-program.md :start-after: :end-before: ``` すべての最適解は、`search_optimal_solutions()` メンバ関数を次のように呼び出すことで取得できます： ```{include} ../../programFiles/markDown/basic/solving-expressions-program.md :start-after: :end-before: ``` 出力は次のとおりです： ```{include} ../../programFiles/markDown/basic/solving-expressions-program.md :start-after: :end-before: ``` Exhaustive Solver は、小規模な式の解析やデバッグに非常に有用です。 ## ABS3 Solver **ABS3 Solver**は、CUDA GPUとマルチコアCPUを活用する高性能ソルバーです。 GPUが利用できない場合は、自動的にCPUのみモードにフォールバックします。 使用方法は以下の3ステップです： - 式に対して`ABS3Solver`オブジェクトを作成します。 - ソルバーオブジェクトのメソッドを使って探索オプションを設定します。 - `search()`メソッドを呼び出します。得られた解が返されます。 ```{literalinclude} ../../programFiles/pythonPrograms/basic/solving-expressions-program3.py :language: python :caption: solving-expressions-program3.py ``` このプログラムの出力は以下の通りです： ```{include} ../../programFiles/markDown/basic/solving-expressions-program.md :start-after: :end-before: ``` パラメータ、コールバック、複数解の収集の詳細についてはABS3 Solverをご覧ください。 :::