Exhaustive Solverの使い方

Exhaustive SolverはQUBO/HUBO式のための完全探索ソルバーです. すべての可能な割り当てが検査されるため,解の最適性が保証されます. 探索はCPUスレッドを使用して並列化され,CUDA GPUが利用可能な場合は,探索をさらに高速化するためにGPUアクセラレーションが自動的に有効になります.

Exhaustive Solverを使って問題を解くには,以下の2つのステップで行います：

  1. Exhaustive Solver（qbpp::ExhaustiveSolver）オブジェクトを作成します.

  2. search() メンバ関数を呼び出します.パラメータは初期化子リストとして渡すことができます.

Exhaustive Solverオブジェクトの作成

Exhaustive Solverを使用するには,式（qbpp::Expr）オブジェクトを引数としてExhaustive Solverオブジェクト（qbpp::ExhaustiveSolver）を以下のように構築します：

  • qbpp::ExhaustiveSolver(const qbpp::Expr& f): ここで,f は解くべき式です. 事前に simplify_as_binary() 関数を呼び出してバイナリ式として簡約化しておく必要があります. この関数は与えられた式 f を解探索中に使用される内部フォーマットに変換します.

パラメータの設定

探索パラメータは search() に初期化子リストとして直接渡します. 以下のパラメータが利用可能です：

パラメータ

値

説明

target_energy

エネルギー文字列

早期終了のためのターゲットエネルギー値を設定します.ソルバーがターゲット以下のエネルギーを持つ解を見つけると,探索は直ちに終了します.

verbose

"1" or "true"

探索の進捗をパーセンテージで表示します.総実行時間の推定に役立ちます.

enable_default_callback

"1" or "true"

新たに得られた最良解を出力するデフォルトコールバック関数を有効にします.

topk_sols

整数文字列

最小エネルギーのtop-k解を収集します.

best_energy_sols

"0"

最適解（最小エネルギーの解）を収集します.値は保持する最大数で,0 は無制限（すべて収集）.

all_sols

"1" or "true"

すべての \(2^n\) 個の解を収集します.

解の探索

  • search(): 見つかった最良解を返します（パラメータなし）.CUDA GPUが利用可能な場合,CPUスレッドと並行してGPUを使用した探索の高速化が自動的に行われます.

  • search(params): Sol オブジェクトを返します.topk_sols,best_energy_sols,all_sols が設定されている場合,収集された解は sol.sols でエネルギーの昇順にアクセスできます.

プログラム例

以下のプログラムは,Exhaustive Solverを使用して**Low Autocorrelation Binary Sequences (LABS)**問題の解を探索します：

exhaustive-solver-usage-program1.cpp
#include <qbpp/qbpp.hpp>
#include <qbpp/exhaustive_solver.hpp>

int main() {
  size_t size = 20;
  auto x = qbpp::var("x", size);
  auto f = qbpp::toExpr(0);
  for (size_t d = 1; d < size; ++d) {
    auto temp = qbpp::toExpr(0);
    for (size_t i = 0; i < size - d; ++i) {
      temp += (2 * x[i] - 1) * (2 * x[i + d] - 1);
    }
    f += qbpp::sqr(temp);
  }
  f.simplify_as_binary();

  auto solver = qbpp::ExhaustiveSolver(f);
  auto sol = solver.search({{"enable_default_callback", 1}});
  std::cout << sol.energy() << ": ";
  for (auto val : sol(x)) {
    std::cout << (val == 0 ? "-" : "+");
  }
  std::cout << std::endl;
}

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

TTS = 0.001s Energy = 1786
TTS = 0.001s Energy = 1546
TTS = 0.001s Energy = 926
TTS = 0.001s Energy = 422
TTS = 0.001s Energy = 350
TTS = 0.001s Energy = 282
TTS = 0.001s Energy = 266
TTS = 0.001s Energy = 254
TTS = 0.002s Energy = 226
TTS = 0.002s Energy = 158
TTS = 0.002s Energy = 150
TTS = 0.002s Energy = 122
TTS = 0.002s Energy = 114
TTS = 0.002s Energy = 110
TTS = 0.002s Energy = 98
TTS = 0.002s Energy = 82
TTS = 0.002s Energy = 74
TTS = 0.002s Energy = 66
TTS = 0.003s Energy = 58
TTS = 0.008s Energy = 34
TTS = 0.023s Energy = 26
26: -+-+----+----++-++--

すべての最適解は best_energy_sols を設定することで取得できます：

  auto solver = qbpp::ExhaustiveSolver(f);
  auto sol = solver.search({{"best_energy_sols", 0}});
  for (const auto& s : sol.sols) {
    std::cout << s.energy() << ": ";
    for (auto val : s(x)) {
      std::cout << (val == 0 ? "-" : "+");
    }
    std::cout << std::endl;
  }

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

26: -----+-+++-+--+++--+
26: --++-++----+----+-+-
26: -+-+----+----++-++--
26: -++---++-+---+-+++++
26: +--+++--+-+++-+-----
26: +-+-++++-++++--+--++
26: ++--+--++++-++++-+-+
26: +++++-+---+-++---++-

最小エネルギーのtop-k解は topk_sols を設定することで取得できます：

  auto solver = qbpp::ExhaustiveSolver(f);
  auto sol = solver.search({{"topk_sols", 10}});
  for (const auto& s : sol.sols) {
    std::cout << s.energy() << ": ";
    for (auto val : s(x)) {
      std::cout << (val == 0 ? "-" : "+");
    }
    std::cout << std::endl;
  }

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

26: -----+-+++-+--+++--+
26: --++-++----+----+-+-
26: -+-+----+----++-++--
26: -++---++-+---+-+++++
26: +--+++--+-+++-+-----
26: +-+-++++-++++--+--++
26: ++--+--++++-++++-+-+
26: +++++-+---+-++---++-
34: ++--++--+-++-+-+++++
34: +++---+-+-++++-++-++

さらに,非最適解を含むすべての解は all_sols を設定することで取得できます. すべての \(2^n\) 個の解をメモリに格納することに注意してください.ここで \(n\) は変数の数です. 例えば,\(n = 20\) の場合,100万個以上の解が格納され,メモリ使用量は \(n\) に対して指数的に増加します. \(n\) が十分小さい場合にのみ使用してください.

  auto solver = qbpp::ExhaustiveSolver(f);
  auto sol = solver.search({{"all_sols", 1}});
  for (const auto& s : sol.sols) {
    std::cout << s.energy() << ": ";
    for (auto val : s(x)) {
      std::cout << (val == 0 ? "-" : "+");
    }
    std::cout << std::endl;
  }

以下に示すように,すべての \(2^{20}\) 個の解がエネルギーの昇順で出力されます：

26: -----+-+++-+--+++--+
26: --++-++----+----+-+-
26: -+-+----+----++-++--
26: -++---++-+---+-+++++
26: +--+++--+-+++-+-----
26: +-+-++++-++++--+--++
26: ++--+--++++-++++-+-+
26: +++++-+---+-++---++-
34: -----+-+--+-++--++--
34: ----+----++-++---+-+
34: ----+--+++--+-+++-+-
34: ---+++-+-+----+--+--
34: ---+++++-+++-++-+-++
34: --+--+----+-+-+++---
34: --+-+--+---+-----+++
34: --++--++-+--+-+-----
34: -+--+------+-+++---+
34: -+--+-+---+---+++++-
[omitted]

Exhaustive SolverはQUBO/HUBO式のための完全探索ソルバーです. すべての可能な割り当てが検査されるため,解の最適性が保証されます. 探索はCPUスレッドを使用して並列化され,CUDA GPUが利用可能な場合は,探索をさらに高速化するためにGPUアクセラレーションが自動的に有効になります.

Exhaustive Solverを使って問題を解くには,以下の2つのステップで行います:

  1. Exhaustive Solver（qbpp.ExhaustiveSolver）オブジェクトを作成します.

  2. search() メソッドを呼び出します.パラメータはキーワード引数として渡すことができます.

Exhaustive Solverオブジェクトの作成

Exhaustive Solverを使用するには,式を引数としてExhaustive Solverオブジェクト（qbpp.ExhaustiveSolver）を以下のように構築します:

  • qbpp.ExhaustiveSolver(f)

ここで,f は解くべき式です. 事前に simplify_as_binary() メソッドを呼び出してバイナリ式として簡約化しておく必要があります. コンストラクタは式をホストメモリにロードし,利用可能な GPU がある場合はデバイスメモリにも転送します.以降 search() を複数回呼び出してもこのロードは1度きりなので,同じ式に対して繰り返し探索する際のオーバーヘッドがありません.

探索パラメータの設定

探索パラメータは search() メソッドにキーワード引数として直接渡します. 以下のパラメータが利用可能です:

パラメータ

型

説明

デフォルト

target_energy

int

早期終了のためのターゲットエネルギー値を設定します.ソルバーがこの値以下のエネルギーを持つ解を見つけると,探索は直ちに終了します.

(なし)

verbose

int (0 または 1)

1 に設定すると,探索の進捗をパーセンテージで表示します.総実行時間の推定に役立ちます.

0

enable_default_callback

int (0 または 1)

1 に設定すると,新たに得られた最良解のエネルギーと TTS を表示するデフォルトコールバック関数を有効にします.

0

topk_sols

int

最小エネルギーの top-k 解を収集します.

(無効)

best_energy_sols

int

最適解（最小エネルギーの解）を収集します.値は保持する最大数で,0 は無制限（すべて収集）.

(無効)

all_sols

int (0 または 1)

1 に設定すると,すべての \(2^n\) 個の解を収集します.メモリ使用量は変数数 n に対して指数的に増加するため,n が十分小さい場合にのみ使用してください.

(無効)

パラメータは search() にキーワード引数として渡します:

sol = solver.search(target_energy=0, enable_default_callback=1)

未知のパラメータキーを指定すると実行時エラーになります.

解の探索

Exhaustive Solver は search() メソッドを呼び出して解を探索します.パラメータはキーワード引数として渡せます. このメソッドは見つかった最良解を返します. CUDA GPU が利用可能な場合,CPU スレッドと並行して GPU を使用した探索の高速化が自動的に行われます. 返される解は sol.energy（エネルギー値）,sol(x)（変数値の取得）,sol.info（ソルバー情報の辞書）などを提供します.詳細は QR_SOLUTION を参照してください.

topk_sols,best_energy_sols,all_sols が設定されている場合,search() が返す解には収集された解も含まれます. 以下のプロパティと操作で取得できます:

  • sol.sols: エネルギーの昇順にソートされた解のリスト.

  • sol.sols: 格納されている解のリスト（エネルギーの昇順）.

  • sol.sols[i]: i 番目の解を返します.

  • len(sol.sols): 格納されている解の個数.

プログラム例

以下のプログラムは,Exhaustive Solverを使用して**Low Autocorrelation Binary Sequences (LABS)**問題の解を探索します:

exhaustive-solver-usage-program1.py
import pyqbpp as qbpp

size = 20
x = qbpp.var("x", shape=size)
f = qbpp.expr()
for d in range(1, size):
    temp = qbpp.expr()
    for i in range(size - d):
        temp += (2 * x[i] - 1) * (2 * x[i + d] - 1)
    f += qbpp.sqr(temp)
f.simplify_as_binary()

solver = qbpp.ExhaustiveSolver(f)
sol = solver.search(enable_default_callback=1)
bits = "".join("-" if sol(x[i]) == 0 else "+" for i in range(size))
print(f"{sol.energy}: {bits}")

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

TTS = 0.001s Energy = 1786
TTS = 0.001s Energy = 1546
TTS = 0.001s Energy = 926
TTS = 0.001s Energy = 422
TTS = 0.001s Energy = 350
TTS = 0.001s Energy = 282
TTS = 0.001s Energy = 266
TTS = 0.001s Energy = 254
TTS = 0.002s Energy = 226
TTS = 0.002s Energy = 158
TTS = 0.002s Energy = 150
TTS = 0.002s Energy = 122
TTS = 0.002s Energy = 114
TTS = 0.002s Energy = 110
TTS = 0.002s Energy = 98
TTS = 0.002s Energy = 82
TTS = 0.002s Energy = 74
TTS = 0.002s Energy = 66
TTS = 0.003s Energy = 58
TTS = 0.008s Energy = 34
TTS = 0.023s Energy = 26
26: -+-+----+----++-++--

すべての最適解は best_energy_sols を設定することで取得できます:

solver = qbpp.ExhaustiveSolver(f)
sol = solver.search(best_energy_sols=0)
for s in sol.sols:
    bits = "".join("-" if s(x[i]) == 0 else "+" for i in range(size))
    print(f"{s.energy}: {bits}")

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

26: -----+-+++-+--+++--+
26: --++-++----+----+-+-
26: -+-+----+----++-++--
26: -++---++-+---+-+++++
26: +--+++--+-+++-+-----
26: +-+-++++-++++--+--++
26: ++--+--++++-++++-+-+
26: +++++-+---+-++---++-

最小エネルギーのtop-k解は topk_sols を設定することで取得できます:

solver = qbpp.ExhaustiveSolver(f)
sol = solver.search(topk_sols=10)
for s in sol.sols:
    bits = "".join("-" if s(x[i]) == 0 else "+" for i in range(size))
    print(f"{s.energy}: {bits}")

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

26: -----+-+++-+--+++--+
26: --++-++----+----+-+-
26: -+-+----+----++-++--
26: -++---++-+---+-+++++
26: +--+++--+-+++-+-----
26: +-+-++++-++++--+--++
26: ++--+--++++-++++-+-+
26: +++++-+---+-++---++-
34: ++--++--+-++-+-+++++
34: +++---+-+-++++-++-++

さらに,非最適解を含むすべての解は all_sols を設定することで取得できます. すべての \(2^n\) 個の解をメモリに格納することに注意してください.ここで \(n\) は変数の数です. 例えば,\(n = 20\) の場合,100万個以上の解が格納され,メモリ使用量は \(n\) に対して指数的に増加します. \(n\) が十分小さい場合にのみ使用してください.

solver = qbpp.ExhaustiveSolver(f)
sol = solver.search(all_sols=1)
for s in sol.sols:
    bits = "".join("-" if s(x[i]) == 0 else "+" for i in range(size))
    print(f"{s.energy}: {bits}")

以下に示すように,すべての \(2^{20}\) 個の解がエネルギーの昇順で出力されます:

26: -----+-+++-+--+++--+
26: --++-++----+----+-+-
26: -+-+----+----++-++--
26: -++---++-+---+-+++++
26: +--+++--+-+++-+-----
26: +-+-++++-++++--+--++
26: ++--+--++++-++++-+-+
26: +++++-+---+-++---++-
34: -----+-+--+-++--++--
34: ----+----++-++---+-+
34: ----+--+++--+-+++-+-
34: ---+++-+-+----+--+--
34: ---+++++-+++-++-+-++
34: --+--+----+-+-+++---
34: --+-+--+---+-----+++
34: --++--++-+--+-+-----
34: -+--+------+-+++---+
34: -+--+-+---+---+++++-
[omitted]