QUBO++ の表現力

QUBO/HUBO ソルバーが最終的に受け取るのは，バイナリ変数の多項式です． そのため従来は，解きたい問題を自分でそこまで降ろす必要がありました． 整数はバイナリ変数の列に展開し，不等式にはスラック変数を足し， 絶対値や最大値は補助変数と場合分けで表現し，3 次以上の項は 2 次に落とす． 変換のたびに変数が増え，ペナルティの重みを調整する手間が生まれ， 元の問題の構造は見えなくなります．

QUBO++ はこの作業を要求しません． 書いたモデルが，そのまま解かれるモデルです．

従来の QUBO で必要な手作業 QUBO++ での書き方 詳細
3 次以上の項を補助変数で 2 次に落とす そのまま書く HUBO と QUBO
$\bar{x}$ を $1-x$ に展開する（項数が爆発する） ~x と書く 否定リテラル
整数をバイナリ変数の列に展開する qbpp::int_var() で宣言する ネイティブ整数変数
絶対値・最大値を補助変数と場合分けで表す qbpp::abs()・qbpp::max() と書く 非線形関数とネイティブ制約
不等式にスラック変数を足し，重みを調整する qbpp::cons() で囲む 非線形関数とネイティブ制約
係数のオーバーフローを自分で管理する 型を選ぶ 変数と式のデータ型

本ページはこれらの機能の概観です． それぞれの詳しい説明は表の右端のリンク先を参照してください．

任意の次数の項

QUBO++ の式は 2 次に限定されません． 3 次以上の項をそのまま書くことができます．

auto y = qbpp::var("y", 4);
auto cubic = 2 * y[0] * y[1] * y[2] - 3 * y[1] * y[2] * y[3];
std::cout << "cubic = " << cubic << std::endl;

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

cubic = 2*y[0]*y[1]*y[2] -3*y[1]*y[2]*y[3]

QUBO++ にバンドルされているソルバーは HUBO をそのまま扱うため， 2 次化は必要ありません． 2 次のモデルしか受け取らない外部ソルバーに渡すときだけ， HUBO の QUBO への変換で 2 次化してください．

否定リテラル

バイナリ変数 $x$ の否定 $\bar{x}$ は ~x と書けます． $\bar{x}$ を $1-x$ に置き換えて展開する必要はありません．

auto x = qbpp::var("x", 4);
auto neg = ~x[0] * ~x[1] * ~x[2] * ~x[3];
auto expanded = qbpp::simplify((1 - x[0]) * (1 - x[1]) * (1 - x[2]) * (1 - x[3]));
std::cout << "neg      = " << neg << std::endl;
std::cout << "expanded = " << expanded << std::endl;

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

neg      = ~x[0]*~x[1]*~x[2]*~x[3]
expanded = 1 -x[0] -x[1] -x[2] -x[3] +x[0]*x[1] +x[0]*x[2] +x[0]*x[3] +x[1]*x[2] +x[1]*x[3] +x[2]*x[3] -x[0]*x[1]*x[2] -x[0]*x[1]*x[3] -x[0]*x[2]*x[3] -x[1]*x[2]*x[3] +x[0]*x[1]*x[2]*x[3]

どちらも同じ値を持つ式ですが，項数は 1 対 16 です． 否定リテラルが 1 つ増えるたびに展開後の項数は 2 倍になるため， この差は変数が増えるほど広がります．

整数変数 — 2 つの選択肢

QUBO++ には性格の異なる 2 種類の整数変数があります．

auto a = 0 <= qbpp::var_int("a") <= 10;   // バイナリエンコーディング
auto b = 0 <= qbpp::int_var("b") <= 10;   // ネイティブ整数変数
std::cout << "a = " << a << std::endl;
std::cout << "b = " << b << std::endl;

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

a = a[0] +2*a[1] +4*a[2] +3*a[3]
b = b

qbpp::var_int() で宣言した整数変数は， その場でバイナリ変数の重み付き和に展開されます（整数変数）． qbpp::int_var() で宣言した整数変数は展開されず， 整数値をそのまま保持します（ネイティブ整数変数）． どちらも式の中では同じように扱えます．

  qbpp::var_int() qbpp::int_var()
式の中での実体 バイナリ変数の重み付き和 整数値そのもの
バンドルソルバー バイナリ変数として探索 整数値のまま探索
範囲を広げたとき 変数の個数が増える 変数の個数は増えない
バイナリ専用の外部ソルバー そのまま渡せる qbpp::binarize() で変換
MILP ソルバー バイナリ変数として渡る 整数変数のまま渡せる

数量（個数・時刻・在庫量など）にはネイティブ整数変数が適しています． どれを選ぶかというラベル（訪問順序・色など）には， 整数変数よりも one-hot 表現が適しています．

非線形関数

絶対値・ReLU・最大値・最小値を，式の中で直接使えます． 補助変数を導入したり場合分けを書いたりする必要はありません．

auto q = 0 <= qbpp::int_var("q") <= 10;
auto r = 0 <= qbpp::int_var("r") <= 10;
auto over = 2 * qbpp::relu(q - 6);   // 6 を超えた分だけ増えるコスト
auto gap = qbpp::abs(q - 5);         // 5 からのずれ
auto peak = qbpp::max(q, r);         // 2 つの式の最大値

qbpp::abs(f, 2)・qbpp::relu(f, 2) と書くと 2 乗になります． 詳しくは非線形関数とネイティブ制約を参照してください．

制約の宣言

式の中の制約部分を qbpp::cons() で囲むと， その部分は制約とみなされて特別に処理されます． スラック変数を自分で足す必要はありません．

auto w = qbpp::var("w", 3);
auto load = 3 * w[0] + 5 * w[1] + 7 * w[2];
auto obj = -qbpp::sum(w)                         // 目的関数
         + 100 * qbpp::cons(load <= 10)          // 不等式制約
         + 100 * qbpp::cons(qbpp::sum(w) == 2);  // 等式制約

等式・片側の不等式・両側の範囲を同じ書き方で宣言できます． 制約を満たす解が見つかったかどうかは，ソルバーが違反本数として報告します． 詳しくは非線形関数とネイティブ制約を参照してください．

係数の型

係数とエネルギー値の型は，マクロ 1 つで切り替えられます． int32_t から，128 ビット整数，桁数無制限の qbpp::cpp_int， 実数の double まで選べます． 式の書き方は型によらず同じです． 一覧は変数と式のデータ型を参照してください．

すべてを 1 つのモデルに

ここまでの機能は組み合わせて使えます． 次のプログラムは，3 本の生産ラインへの割当を求めます．

  • ライン $i$ を使うかどうかをバイナリ変数 use[i] で表し，使うと段取り費 5 がかかる
  • ライン $i$ の生産量をネイティブ整数変数 q[i]（0 以上 10 以下）で表す
  • 生産量が 6 を超えた分には超過費が 2 倍でかかる（relu）
  • ライン 0 と 1 の生産量の偏りをコストに加える（abs）
  • 停止しているラインでは生産できない（不等式制約）
  • 3 本の生産量の合計はちょうど 20（等式制約）
  • 3 本すべてを止めた場合は違約金 50（3 次の否定リテラル項）
#include <qbpp/exhaustive_solver.hpp>
#include <qbpp/qbpp.hpp>

int main() {
  auto use = qbpp::var("use", 3);              // バイナリ変数
  auto q = 0 <= qbpp::int_var("q", 3) <= 10;   // ネイティブ整数変数

  auto f = qbpp::toExpr(0);
  for (int i = 0; i < 3; ++i) {
    f += 5 * use[i];                                 // 段取り費
    f += 2 * qbpp::relu(q[i] - 6);                   // 超過費
    f += 100 * qbpp::cons(q[i] - 10 * use[i] <= 0);  // 停止中は生産できない
  }
  f += qbpp::abs(q[0] - q[1]);                       // ライン間の偏り
  f += 50 * ~use[0] * ~use[1] * ~use[2];             // 全停止の違約金
  f += 100 * qbpp::cons(qbpp::sum(q) == 20);         // 需要をちょうど満たす

  f.simplify_as_binary();
  auto solver = qbpp::ExhaustiveSolver(f);
  auto sol = solver.search();
  for (int i = 0; i < 3; ++i)
    std::cout << "use[" << i << "] = " << sol(use[i])
              << ", q[" << i << "] = " << sol(q[i]) << std::endl;
  std::cout << "energy = " << sol.energy() << std::endl;
}

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

use[0] = 1, q[0] = 7
use[1] = 1, q[1] = 7
use[2] = 1, q[2] = 6
energy = 19

段取り費 15，超過費 4（生産量 7 が 2 本），偏り 0，制約違反なしで合計 19 です． このモデルには，補助変数もスラック変数も 1 つも現れていません．

従来の形式へ降ろす

外部のソルバーに渡すなど，従来の形式が必要になったときは， モデルを明示的に降ろすことができます．

関数 変換
qbpp::binarize(f) ネイティブ整数変数をバイナリエンコーディングに
qbpp::expand_cons(f) qbpp::cons() の宣言を従来のペナルティ式に
qbpp::reduce(f) 3 次以上の項を 2 次に 
auto n = 0 <= qbpp::int_var("n") <= 10;
auto bits = qbpp::binarize(n);
std::cout << "bits = " << bits << std::endl;

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

bits = n#0 +2*n#1 +4*n#2 +3*n#3

MILP ソルバーへは，整数変数を整数のまま渡す ILP モードも利用できます．

次に読むページ

Back to top

Page last modified: 2026.08.26.

© 2026 中野浩嗣, 広島大学