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 を、解探索時に使用される内部形式へ変換します。

Exhaustive Solver オプションの設定

パラメータ

値

説明

target_energy

エネルギー文字列

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

verbose

"1" or "true"

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

enable_default_callback

"1" or "true"

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

topk_sols

整数文字列

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

best_energy_sols

"1"

すべての最適解（最小エネルギーの解）を収集します。

all_sols

"1" or "true"

すべての解を収集します。

解の探索

Exhaustive Solver は、ソルバーオブジェクトの以下のいずれかのメンバー関数を呼び出すことで解を探索します。

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

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

プログラム例

以下のプログラムは、Exhaustive Solverを使用して、低自己相関二進列（Low Autocorrelation Binary Sequence、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.000s Energy = 1506
TTS = 0.000s Energy = 1030
TTS = 0.000s Energy = 502
TTS = 0.000s Energy = 446
TTS = 0.000s Energy = 234
TTS = 0.000s Energy = 110
TTS = 0.001s Energy = 106
TTS = 0.001s Energy = 74
TTS = 0.001s Energy = 66
TTS = 0.001s Energy = 42
TTS = 0.001s Energy = 34
TTS = 0.004s Energy = 26
26: --++-++----+----+-+-

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

  auto solver = qbpp::ExhaustiveSolver(f);
  auto sol = solver.search({{"best_energy_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;
  }

このプログラムは次の出力を表示します:

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: -+--+-+---+---+++++-

  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 または 1)

1 に設定すると、すべての最適解（最小エネルギーの解）を収集します。

無効

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[i]: i 番目の解を返します。

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

プログラム例

以下のプログラムは、Exhaustive Solverを使用して、低自己相関二進列（Low Autocorrelation Binary Sequence、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.000s Energy = 1506
TTS = 0.000s Energy = 1030
TTS = 0.000s Energy = 502
TTS = 0.000s Energy = 446
TTS = 0.000s Energy = 234
TTS = 0.000s Energy = 110
TTS = 0.001s Energy = 106
TTS = 0.001s Energy = 74
TTS = 0.001s Energy = 66
TTS = 0.001s Energy = 42
TTS = 0.001s Energy = 34
TTS = 0.004s Energy = 26
26: --++-++----+----+-+-

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

solver = qbpp.ExhaustiveSolver(f)
sol = solver.search(best_energy_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}")

このプログラムは次の出力を表示します:

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: -+--+-+---+---+++++-