式の求解

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

• Easy Solver

  • シミュレーテッドアニーリングに基づくヒューリスティックアルゴリズムを実行します.

  • マルチコアCPU上で並列に動作します.

  • 最適性は保証されません.

• Exhaustive Solver

  • すべての可能な解を探索します.

  • 返される解の最適性が保証されます.

  • バイナリ変数の数が約30～40以下の場合にのみ計算が現実的です.

  • CUDA GPUが利用可能な場合,CPUスレッドと並行してGPUアクセラレーションが自動的に有効になります.

• ABS3 Solver

  • CUDA GPUとマルチコアCPUを活用する高性能ソルバーです.

  • 最適性は保証されませんが,Easy Solverよりはるかに強力です.

  • GPUが利用できない場合はCPUのみモードにフォールバックします.

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

1. ソルバーオブジェクト（qbpp::EasySolver,qbpp::ExhaustiveSolver,または**qbpp::ABS3Solver**）を作成します.

2. ソルバーオブジェクトの**search()メンバ関数を呼び出します.パラメータは初期化子リストとして渡すことができます.得られた解を格納するqbpp::Sol**オブジェクトが返されます.

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

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::EasySolver のインスタンスを構築します. その前に,simplify_as_binary()を呼び出して f をバイナリ変数用に簡約化する必要があります. コンストラクタはsolverという名前の EasySolver オブジェクトを返します. 最適値が \(f=0\) であることがわかっているので,search() にターゲットエネルギーを初期化子リストとして渡します. 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**で定義されています.

f をコンストラクタに渡してクラス**qbpp::ExhaustiveSolverのインスタンスsolverを構築します. 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}}

std::cout << sol はデフォルトで見つかった最良解のみを出力します. 収集された全解のリストはメンバ sol.sols からアクセスでき,これはエネルギー昇順にソートされた解のリストです.

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

  auto solver = qbpp::ExhaustiveSolver(f);
  auto sol = solver.search({{"best_energy_sols", 0}});
  for (size_t k = 0; k < sol.size(); ++k) {
    std::cout << "(" << k << ") " << sol.sols[k] << std::endl;
  }

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

(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::ExhaustiveSolver(f);
  auto sol = solver.search({{"all_sols", 1}});
  for (size_t k = 0; k < sol.size(); ++k) {
    std::cout << "(" << k << ") " << sol.sols[k] << std::endl;
  }

(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::ABS3Solver**オブジェクトを作成します.

2. **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
0:{{a,0},{b,1},{c,1},{d,0}}

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

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

• Easy Solver

  • シミュレーテッドアニーリングに基づくヒューリスティックアルゴリズムを実行します.

  • マルチコアCPU上で並列に動作します.

  • 最適性は保証されません.

• Exhaustive Solver

  • すべての可能な解を探索します.

  • 返される解の最適性が保証されます.

  • バイナリ変数の数が約30〜40以下の場合にのみ計算が現実的です.

  • CUDA GPUが利用可能な場合,CPUスレッドと並行してGPUアクセラレーションが自動的に有効になります.

• ABS3 Solver

  • CUDA GPUとマルチコアCPUを活用する高性能ソルバーです.

  • 最適性は保証されませんが,Easy Solverよりはるかに強力です.

  • GPUが利用できない場合はCPUのみモードにフォールバックします.

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

1. ソルバーオブジェクト（qbpp.EasySolver,qbpp.ExhaustiveSolver,または qbpp.ABS3Solver）を作成します.

2. ソルバーオブジェクトの search() メソッドを呼び出します.パラメータはキーワード引数として渡すことができます.得られた解が返されます.

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

Easy Solver

Easy Solverを使用するには,PyQBPPが提供するクラス qbpp.EasySolver を使用します.

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

\[ \begin{aligned} f(a,b,c,d) &= (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.EasySolver のインスタンスを構築します. その前に,simplify_as_binary() を呼び出して f をバイナリ変数用に簡約化する必要があります. コンストラクタは solver という名前の EasySolver オブジェクトを返します. 最適値が \(f=0\) であることがわかっているので,search() にキーワード引数 target_energy=0 を渡します.これは f の値が 0 以下となる解が見つかった時点で探索を終了することを意味します. solver の search() メソッドを呼び出すと,解 sol が返され,print() で出力されます.

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

Exhaustive Solverを使用するには,PyQBPPが提供するクラス qbpp.ExhaustiveSolver を使用します.

f をコンストラクタに渡してクラス qbpp.ExhaustiveSolver のインスタンス solver を構築します. solver の search() メソッドを呼び出すと,解 sol が返され,print() で出力されます. 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}}

print(sol) はデフォルトで見つかった最良解のみを出力します. 収集された全解のリストは属性 sol.sols からアクセスでき,これはエネルギー昇順にソートされた解のリストです.

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

solver = qbpp.ExhaustiveSolver(f)
sol = solver.search(best_energy_sols=0)
for i, s in enumerate(sol.sols):
    print(f"({i}) {s}")

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

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

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

solver = qbpp.ExhaustiveSolver(f)
sol = solver.search(all_sols=1)
for i, s in enumerate(sol.sols):
    print(f"({i}) {s}")

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

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

ABS3 Solver

ABS3 Solverを使用するには,PyQBPPが提供するクラス qbpp.ABS3Solver を使用します.

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

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

1. 式に対して qbpp.ABS3Solver オブジェクトを作成します.

2. 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
0:{{a,0},{b,1},{c,1},{d,0}}

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