Easy Solver の使用方法

Easy Solver は QUBO/HUBO 式のヒューリスティックソルバーです。

Easy Solver を使って問題を解く手順は以下の3ステップで構成されます：

  1. Easy Solver（または qbpp::easy_solver::EasySolver）オブジェクトを作成する。

  2. qbpp::Params オブジェクトのメンバ関数を呼び出して検索オプションを設定する。

  3. search(params) メンバ関数を呼び出して解を検索する。これにより、qbpp::easy_solver::Sols オブジェクトが返されます。

Easy Solver オブジェクトの作成

Easy Solver を使用するには、次のように式（または qbpp::Expr）オブジェクトを用いて Easy Solver オブジェクト（または qbpp::easy_solver::EasySolver）を構築します：

  • qbpp::easy_solver::EasySolver(const qbpp::Expr& f)

ここで f は解く対象の式です。事前に simplify_as_binary() 関数を呼び出して、二値式として簡略化されている必要があります。この関数は、与えられた式 f を解探索中に使用される内部フォーマットに変換します。

探索パラメータの設定

探索パラメータは search() オブジェクトを使用して設定します。 以下のパラメータが利用可能です：

パラメータ

説明

デフォルト

time_limit

制限時間（秒）。"0" で時間制限なし。

"10.0"

target_energy

ターゲットエネルギー。この値以下の解が見つかると探索を終了。

（なし）

enable_default_callback

"1" で新たに得られた最良解を出力。

"0"

topk_sols

保持するtop-k解の数。

（無効）

best_energy_sols

最良エネルギーの解を保持。"0" で無制限。

（無効）

パラメータは search() に初期化子リストとして渡します：

auto sol = solver.search({{"time_limit", 5.0}, {"target_energy", 900}, {"enable_default_callback", 1}});

未知のパラメータキーを設定するとランタイムエラーが発生します。

解の探索

Easy Solver は、Easy Solver オブジェクトの search() メンバ関数を呼び出すだけで解を探索します。

プログラム例

以下のプログラムは、Easy Solver を用いて 低自己相関二値列（Low Autocorrelation Binary Sequences, LABS）問題 の解を探索します：

easy-solver-usage-program1.cpp
#include <qbpp/qbpp.hpp>
#include <qbpp/easy_solver.hpp>

int main() {
  size_t size = 100;
  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::EasySolver(f);

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

この例では、以下のオプションが設定されています：

  • 5.0秒の時間制限

  • 目標エネルギー900

  • デフォルトのコールバックが有効

したがって、ソルバーは経過時間が5.0秒に達するか、エネルギー900以下の解が見つかった時点で終了します。

例えば、このプログラムは次のような出力を生成します：

TTS = 0.000s Energy = 300162 thread = 0 Random
TTS = 0.000s Energy = 273350 thread = 0 Random(neighbor)
TTS = 0.000s Energy = 248706 thread = 0 Greedy(neighbor)
TTS = 0.000s Energy = 226086 thread = 0 Greedy(neighbor)
TTS = 0.000s Energy = 205274 thread = 0 Greedy(neighbor)
TTS = 0.000s Energy = 186142 thread = 0 Greedy(neighbor)
TTS = 0.000s Energy = 168442 thread = 0 Greedy(neighbor)
TTS = 0.000s Energy = 152134 thread = 0 Greedy(neighbor)
TTS = 0.000s Energy = 137162 thread = 0 Greedy(neighbor)
TTS = 0.000s Energy = 123374 thread = 0 Greedy(neighbor)
TTS = 0.001s Energy = 110650 thread = 0 Greedy(neighbor)
TTS = 0.001s Energy = 98990 thread = 0 Greedy(neighbor)
TTS = 0.001s Energy = 88346 thread = 0 Greedy(neighbor)
TTS = 0.001s Energy = 78678 thread = 0 Greedy(neighbor)
TTS = 0.001s Energy = 69802 thread = 0 Greedy(neighbor)
TTS = 0.001s Energy = 61798 thread = 0 Greedy(neighbor)
TTS = 0.001s Energy = 54626 thread = 0 Greedy(neighbor)
TTS = 0.001s Energy = 47982 thread = 0 Greedy(neighbor)
TTS = 0.001s Energy = 42034 thread = 0 Greedy(neighbor)
TTS = 0.001s Energy = 36598 thread = 0 Greedy(neighbor)
TTS = 0.001s Energy = 31778 thread = 0 Greedy(neighbor)
TTS = 0.001s Energy = 27446 thread = 0 Greedy(neighbor)
TTS = 0.001s Energy = 23658 thread = 0 Greedy(neighbor)
TTS = 0.002s Energy = 20286 thread = 0 Greedy(neighbor)
TTS = 0.002s Energy = 17250 thread = 0 Greedy(neighbor)
TTS = 0.002s Energy = 14614 thread = 0 Greedy(neighbor)
TTS = 0.002s Energy = 12306 thread = 0 Greedy(neighbor)
TTS = 0.002s Energy = 10350 thread = 0 Greedy(neighbor)
TTS = 0.002s Energy = 8682 thread = 0 Greedy(neighbor)
TTS = 0.002s Energy = 7214 thread = 0 Greedy(neighbor)
TTS = 0.002s Energy = 5994 thread = 0 Greedy(neighbor)
TTS = 0.002s Energy = 4990 thread = 0 Greedy(neighbor)
TTS = 0.002s Energy = 4130 thread = 0 Greedy(neighbor)
TTS = 0.002s Energy = 3478 thread = 0 Greedy(neighbor)
TTS = 0.003s Energy = 2882 thread = 0 Greedy(neighbor)
TTS = 0.003s Energy = 2414 thread = 0 Greedy(neighbor)
TTS = 0.003s Energy = 2122 thread = 0 Greedy(neighbor)
TTS = 0.003s Energy = 1822 thread = 0 Greedy(neighbor)
TTS = 0.003s Energy = 1706 thread = 0 Greedy(neighbor)
TTS = 0.003s Energy = 1574 thread = 0 Greedy(neighbor)
TTS = 0.003s Energy = 1442 thread = 0 Greedy(neighbor)
TTS = 0.003s Energy = 1350 thread = 0 Greedy(neighbor)
TTS = 0.007s Energy = 1306 thread = 7 MoveTo
TTS = 0.008s Energy = 1274 thread = 12 Greedy
TTS = 0.008s Energy = 1262 thread = 12 Greedy(neighbor)
TTS = 0.008s Energy = 1202 thread = 12 Greedy(neighbor)
TTS = 0.016s Energy = 1170 thread = 20 PosMin
TTS = 0.018s Energy = 1166 thread = 23 PosMin
TTS = 0.018s Energy = 994 thread = 23 PosMin(neighbor)
TTS = 0.066s Energy = 986 thread = 7 Greedy
TTS = 0.066s Energy = 982 thread = 7 Greedy(neighbor)
TTS = 0.184s Energy = 954 thread = 10 PosMin
TTS = 0.371s Energy = 942 thread = 12 PosMin
TTS = 0.912s Energy = 930 thread = 4 PosMin
TTS = 0.913s Energy = 902 thread = 4 PosMin(neighbor)
TTS = 2.691s Energy = 898 thread = 15 PosMin
898: ++-++-----+--+--++++++---++-+-+--++-------++-++-+-+-+-+-++-++++-++-+++++-+-+--++++++---+++--+++---++

高度な使用法

複数のトップk解の保持

Easy Solverは探索中に見つかった複数のtop-k解を保持できます。 この機能を有効にするには、topk_sols パラメータを設定します。

このパラメータが設定されると、search()によって返されるソリューションオブジェクトには保存されたトップk解が含まれます。返されたオブジェクトsolsに対しては、インデックスまたはイテレータを使用して保存された解にアクセスできます：

  • sols[i]：i番目のqbpp::Solオブジェクトを返します。

  • size()：保存された解の数を返します。

  • begin(), end(), cbegin(), cend()：範囲ベースのforループを使用して順番に各解にアクセスできるイテレータです。

以下のプログラムは、Easy Solverを使用して低自己相関二進列（Low Autocorrelation Binary Sequence、LABS）問題を解きます。enable_topk_sols(20)が呼び出されているため、ソルバーは最大20個のトップk解を保持します。プログラムは範囲ベースのforループを使用して各保存された解を出力します。

easy-solver-usage-program2.cpp
#include <qbpp/qbpp.hpp>
#include <qbpp/easy_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::EasySolver(f);

  auto sols = solver.search({{"time_limit", 5.0}, {"topk_sols", 20}});
  for (const auto& sol : sols) {
    std::cout << sol.energy() << ": ";
    for (auto val : sol(x)) {
      std::cout << (val == 0 ? "-" : "+");
    }
    std::cout << std::endl;
  }
}

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

26: -----+-+++-+--+++--+
26: +--+++--+-+++-+-----
26: -+-+----+----++-++--
26: --++-++----+----+-+-
26: -++---++-+---+-+++++
34: ---+++++-+++-++-+-++
34: +-+-+++++----++--++-
34: -+++++---+---+-+--+-
34: +++-----+---+--+-+--
34: --++--++-+--+-+-----
34: -+--+-+---+---+++++-
34: ---+++-+-+----+--+--
38: -++-++-+-+---++-----
38: --++++--+-+--+---+--
38: -+-+---++------++-++
38: ++++-++-+--+++-+---+
38: ----+--+-++---+-+++-
42: -+++++++--++-+-+-++-
42: -+-+----+++++-++--++
42: ++-----+---+--+-+--+

複数の最良エネルギー解を保持する

Easy Solverは探索中に見つかった最良（最小）エネルギーを共有する複数の解を保持できます。 この機能を有効にするには、best_energy_sols パラメータを設定します。 値は保持する最大解数を指定します。0 で無制限です。

使い方は topk_sols と同じです。 したがって、上記のQUBO++プログラムでこの機能を有効にするには、topk_sols を best_energy_sols に置き換えます：

  auto sols = solver.search({{"time_limit", 5.0}, {"best_energy_sols", 0}});  // 無制限

このパラメータが設定された場合、ソルバーは見つかった最良エネルギーと等しいエネルギーの解のみを保持します。 結果として得られるプログラムは、すべて最良エネルギー値26を持つ以下の解を生成します：

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

Easy Solver は QUBO/HUBO 式のヒューリスティックソルバーです。

Easy Solver を使って問題を解く手順は以下の2ステップで構成されます：

  1. 解きたい式に対して EasySolver オブジェクトを作成します。

  2. キーワード引数を渡して search() メソッドを呼び出し、解を探索します。見つかった最良解が返されます。

Easy Solver オブジェクトの作成

Easy Solverを使用するには、以下のように式を引数として EasySolver オブジェクトを作成します:

  • EasySolver(f)

ここで f は解く対象の式です。事前に simplify_as_binary() 関数を呼び出して、二値式として簡略化されている必要があります。この関数は、与えられた式 f を解探索中に使用される内部フォーマットに変換します。コンストラクタは式をホストメモリにロードします。以降 search() を複数回呼び出してもこのロードは1度きりなので、同じ式に対して繰り返し探索する際のオーバーヘッドがありません。

探索パラメータの設定

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

パラメータ

型

説明

デフォルト

time_limit

float

制限時間（秒）。0 で時間制限なし。

10.0

target_energy

int

目標エネルギー。この値以下の解が見つかると探索を終了します。

（なし）

enable_default_callback

int (0 または 1)

1 に設定すると、新たに得られた最良解のエネルギーとTTSを自動的に出力します。

0

topk_sols

int

保持するtop-k解の数。

（無効）

best_energy_sols

int

最良エネルギーの解を保持。0 で無制限。

（無効）

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

sol = solver.search(time_limit=5.0, target_energy=900, enable_default_callback=1)

未知のパラメータキーを設定するとランタイムエラーが発生します。

解の探索

Easy Solverは、search() メソッドを呼び出すことで解を探索します。必要に応じてパラメータをキーワード引数として渡すことができます。 このメソッドは、見つかった最良解を返します。返される解は sol.energy（エネルギー値）、sol(x)（変数値の取得）、sol.info（ソルバー情報の辞書）などを提供します。詳細は QR_SOLUTION を参照してください。

プログラム例

以下のプログラムは、Easy Solver を用いて 低自己相関二値列（Low Autocorrelation Binary Sequences, LABS） 問題の解を探索します：

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

size = 100
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.EasySolver(f)
sol = solver.search(time_limit=5.0, target_energy=900, enable_default_callback=1)
bits = "".join("-" if v == 0 else "+" for v in sol(x))
print(f"{sol.energy}: {bits}")

この例では、以下のオプションが設定されています：

  • 5.0秒の時間制限

  • 目標エネルギー900

  • 新しい最良解が見つかるたびにエネルギーとTTSを表示するコールバック。

したがって、ソルバーは経過時間が5.0秒に達するか、エネルギー900以下の解が見つかった時点で終了します。

例えば、このプログラムは次のような出力を生成します：

TTS = 0.000s Energy = 300162 thread = 0 Random
TTS = 0.000s Energy = 273350 thread = 0 Random(neighbor)
TTS = 0.000s Energy = 248706 thread = 0 Greedy(neighbor)
TTS = 0.000s Energy = 226086 thread = 0 Greedy(neighbor)
TTS = 0.000s Energy = 205274 thread = 0 Greedy(neighbor)
TTS = 0.000s Energy = 186142 thread = 0 Greedy(neighbor)
TTS = 0.000s Energy = 168442 thread = 0 Greedy(neighbor)
TTS = 0.000s Energy = 152134 thread = 0 Greedy(neighbor)
TTS = 0.000s Energy = 137162 thread = 0 Greedy(neighbor)
TTS = 0.000s Energy = 123374 thread = 0 Greedy(neighbor)
TTS = 0.001s Energy = 110650 thread = 0 Greedy(neighbor)
TTS = 0.001s Energy = 98990 thread = 0 Greedy(neighbor)
TTS = 0.001s Energy = 88346 thread = 0 Greedy(neighbor)
TTS = 0.001s Energy = 78678 thread = 0 Greedy(neighbor)
TTS = 0.001s Energy = 69802 thread = 0 Greedy(neighbor)
TTS = 0.001s Energy = 61798 thread = 0 Greedy(neighbor)
TTS = 0.001s Energy = 54626 thread = 0 Greedy(neighbor)
TTS = 0.001s Energy = 47982 thread = 0 Greedy(neighbor)
TTS = 0.001s Energy = 42034 thread = 0 Greedy(neighbor)
TTS = 0.001s Energy = 36598 thread = 0 Greedy(neighbor)
TTS = 0.001s Energy = 31778 thread = 0 Greedy(neighbor)
TTS = 0.001s Energy = 27446 thread = 0 Greedy(neighbor)
TTS = 0.001s Energy = 23658 thread = 0 Greedy(neighbor)
TTS = 0.002s Energy = 20286 thread = 0 Greedy(neighbor)
TTS = 0.002s Energy = 17250 thread = 0 Greedy(neighbor)
TTS = 0.002s Energy = 14614 thread = 0 Greedy(neighbor)
TTS = 0.002s Energy = 12306 thread = 0 Greedy(neighbor)
TTS = 0.002s Energy = 10350 thread = 0 Greedy(neighbor)
TTS = 0.002s Energy = 8682 thread = 0 Greedy(neighbor)
TTS = 0.002s Energy = 7214 thread = 0 Greedy(neighbor)
TTS = 0.002s Energy = 5994 thread = 0 Greedy(neighbor)
TTS = 0.002s Energy = 4990 thread = 0 Greedy(neighbor)
TTS = 0.002s Energy = 4130 thread = 0 Greedy(neighbor)
TTS = 0.002s Energy = 3478 thread = 0 Greedy(neighbor)
TTS = 0.003s Energy = 2882 thread = 0 Greedy(neighbor)
TTS = 0.003s Energy = 2414 thread = 0 Greedy(neighbor)
TTS = 0.003s Energy = 2122 thread = 0 Greedy(neighbor)
TTS = 0.003s Energy = 1822 thread = 0 Greedy(neighbor)
TTS = 0.003s Energy = 1706 thread = 0 Greedy(neighbor)
TTS = 0.003s Energy = 1574 thread = 0 Greedy(neighbor)
TTS = 0.003s Energy = 1442 thread = 0 Greedy(neighbor)
TTS = 0.003s Energy = 1350 thread = 0 Greedy(neighbor)
TTS = 0.007s Energy = 1306 thread = 7 MoveTo
TTS = 0.008s Energy = 1274 thread = 12 Greedy
TTS = 0.008s Energy = 1262 thread = 12 Greedy(neighbor)
TTS = 0.008s Energy = 1202 thread = 12 Greedy(neighbor)
TTS = 0.016s Energy = 1170 thread = 20 PosMin
TTS = 0.018s Energy = 1166 thread = 23 PosMin
TTS = 0.018s Energy = 994 thread = 23 PosMin(neighbor)
TTS = 0.066s Energy = 986 thread = 7 Greedy
TTS = 0.066s Energy = 982 thread = 7 Greedy(neighbor)
TTS = 0.184s Energy = 954 thread = 10 PosMin
TTS = 0.371s Energy = 942 thread = 12 PosMin
TTS = 0.912s Energy = 930 thread = 4 PosMin
TTS = 0.913s Energy = 902 thread = 4 PosMin(neighbor)
TTS = 2.691s Energy = 898 thread = 15 PosMin
898: ++-++-----+--+--++++++---++-+-+--++-------++-++-+-+-+-+-++-++++-++-+++++-+-+--++++++---+++--+++---++

複数のtop-k解の保持

Easy Solverは探索中に見つかった複数のtop-k解を保持できます。 この機能を有効にするには、topk_sols パラメータを設定します。

このパラメータが設定されると、search() が返す解は保持されたtop-k解も保持します。 これらは以下のプロパティや操作でアクセスできます:

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

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

  • len(sol.sols): 保持されている解の数。

以下のプログラムは、Easy Solverを使用してLABS問題を解きます。 topk_sols を 20 に設定しているため、ソルバーは最大20個のtop-k解を保持します。 プログラムはrange-based forループを使用して各保持解を出力します。

easy-solver-usage-program2.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.EasySolver(f)
sol = solver.search(time_limit=5.0, topk_sols=20)
for s in sol.sols:
    bits = "".join("-" if v == 0 else "+" for v in s(x))
    print(f"{s.energy}: {bits}")

このプログラムは以下のような出力を表示します:

26: -----+-+++-+--+++--+
26: +--+++--+-+++-+-----
26: -+-+----+----++-++--
26: --++-++----+----+-+-
26: -++---++-+---+-+++++
34: ---+++++-+++-++-+-++
34: +-+-+++++----++--++-
34: -+++++---+---+-+--+-
34: +++-----+---+--+-+--
34: --++--++-+--+-+-----
34: -+--+-+---+---+++++-
34: ---+++-+-+----+--+--
38: -++-++-+-+---++-----
38: --++++--+-+--+---+--
38: -+-+---++------++-++
38: ++++-++-+--+++-+---+
38: ----+--+-++---+-+++-
42: -+++++++--++-+-+-++-
42: -+-+----+++++-++--++
42: ++-----+---+--+-+--+

複数の最良エネルギー解を保持する

Easy Solverは探索中に見つかった最良（最小）エネルギーを共有する複数の解を保持できます。 この機能を有効にするには、best_energy_sols パラメータを設定します。 値は保持する最大解数を指定します。0 で無制限です。

使い方は topk_sols と同じです。 したがって、上記のプログラムでこの機能を有効にするには、topk_sols を best_energy_sols に置き換えます:

sol = solver.search(time_limit=5.0, best_energy_sols=0)  # 無制限

このパラメータが設定された場合、ソルバーは見つかった最良エネルギーと等しいエネルギーの解のみを保持します。 結果として得られるプログラムは、すべて最良エネルギー値26を持つ以下の解を生成します:

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