Hi-QUBO

整数変数と連立方程式の解法

整数変数

QUBO++ は **整数変数** をサポートしており、内部では複数の二進変数を用いて実装されます。 整数値の表現には従来の二進符号化が用いられます。 $n$ 個の二進変数 $x_0, x_1, \ldots, x_{n-1}$ があるとします。 これらの変数は、以下の線形式を用いて $0$ から $2^n-1$ までの全整数を表現できます：

\[\begin{aligned} 2^0x_0+2^1x_1+\cdots 2^{n-1}x_{n-1} \end{aligned}\]

定数オフセット $l$ を導入し、$x_{n-1}$ の係数を任意の値 $d$ で置換すると、次の式が得られる：

\[\begin{aligned} l+2^0x_0+2^1x_1+\cdots +2^{n-2}x_{n-2}+dx_{n-1} \end{aligned}\]

この式は $l$ から $l+2^{n-1}+d-1$ までの全ての整数を表現できる。 この符号化に基づき、整数範囲が $[l,u]$ の変数は、$n$ と $d$ ($1\leq d\leq 2^{n-1}$) の適切な値を選択して以下を満たすように構築できる

\[\begin{aligned} u &= l+2^{n-1}+d-1 \end{aligned}\]

以下のQUBO++プログラムは整数変数の定義方法を示す：

#include "qbpp.hpp"

int main() {
  auto x = 1 <= qbpp::var_int("x") <= 8;
  auto y = -10 <= qbpp::var_int("y") <= 10;
  std::cout << "x = " << x << " uses " << x.size() << " variables.\n";
  std::cout << "y = " << y << " uses " << y.size() << " variables.\n";
}

整数変数は範囲演算子 <= <=を使用して定義され、変数が取り得る整数の範囲を指定します。 関数 qbpp::var_int("name") は、指定された整数範囲を持つ qbpp::VarInt オブジェクト object を生成し、与えられた nameを引数として、二進変数で符号化された線形式を表す オブジェクトを作成します。 プログラムは以下の式を出力します:

x = 1 +x[0] +2*x[1] +4*x[2] uses 3 variables.
y = -10 +y[0] +2*y[1] +4*y[2] +8*y[3] +5*y[4] uses 5 variables.

警告: 整数変数に必要な二値変数の数は、その範囲に対して対数的に増加します。 $u−l$が大きい場合、QUBOサイズは増加するため、可能な限り広い整数範囲は避けるべきです。

連立方程式を解くためのQUBO定式化

QUBO++は変数を整数変数として表現することで連立方程式を解くことができます。 例として、解が$x=4$かつ$y=6$となる以下の連立方程式に対するQUBO定式化を構築します：

\[\begin{aligned} x + y = 10\\ 2x+4y = 28 \end{aligned}\]

これらの方程式を解くため、整数変数 $x$ と $y$ を範囲 $[0,10]$ で定義し、それぞれを4つの二進変数で符号化します：

\[\begin{aligned} x = x_0 +2x_1 +4x_2 +3x_3\\ y = y_0 +2y_1 +4y_2 +3y_3 \end{aligned}\]

以下の各ペナルティ式は、対応する等式が満たされる場合に限り最小値0を取る：

\[\begin{aligned} f(x,y) &= (x+y-10)^2\\ &=(x_0 +2x_1 +4x_2 +3x_3+y_0 +2y_1 +4y_2 +3y_3-10)^2\\ g(x,y) &= (2x+4y -28)^2\\ &= (2\cdot(x_0 +2x_1 +4x_2 +3x_3)+4\cdot( y_0 +2y_1 +4y_2 +3y_3)-28)^2 \end{aligned}\]

したがって、結合式

\[\begin{aligned} h(x,y) &= f(x,y) +g(x,y) \end{aligned}\]

は、両方の式が同時に満たされる場合にのみ、最小値 0 を達成する。

QUBO++プログラム

以下のQUBO++プログラムは、QUBO式$h(x,y)$を構築し、これを解き、結果として得られる $x$と$y$の値をデコードする：

#include "qbpp.hpp"
#include "qbpp_easy_solver.hpp"

int main() {
  auto x = 0 <= qbpp::var_int("x") <= 10;
  auto y = 0 <= qbpp::var_int("y") <= 10;
  auto f = x + y == 10;
  auto g = 2 * x + 4 * y == 28;
  auto h = f + g;
  h.simplify_as_binary();
  auto solver = qbpp::easy_solver::EasySolver(h);
  solver.target_energy(0);
  auto sol = solver.search();
  std::cout << "sol = " << sol << std::endl;
  std::cout << "x = " << x << " = " << sol(x) << std::endl;
  std::cout << "y = " << y << " = " << sol(y) << std::endl;
  std::cout << "f = " << f << " = " << sol(f) << std::endl;
  std::cout << "g = " << g << " = " << sol(g) << std::endl;
  std::cout << "*f = " << *f << " = " << sol(*f) << std::endl;
  std::cout << "*g = " << *g << " = " << sol(*g) << std::endl;
}

まず、 qbpp::VarInt オブジェクトx とy が範囲 $[0,10]$ で定義される。 制約 を表すために qbpp::Expr オブジェクトf は制約 を表すためにx + y == 10作成される。 内部的には、これはQUBO式 qbpp::sqr(x + y -10)に相当する。 同様に、gは制約 を2 * x + 4 * y == 28表す。 結合式h = f + gは両方の式を符号化する。 Easy Solverインスタンスが hで作成され、目標エネルギーは 0に設定される。これは最適解が全ての制約を満たすためである。 関数 search() を呼び出すと、すべての二値変数の最適割当てを保持する qbpp::Sol solオブジェクトを返す。これは全ての二値変数の最適割当てを保持する。 最後に、プログラムは sol, sol(x), sol(y), sol(f), sol(g), sol(*f)と sol(*g)の値を出力する。 ここで、

とgについても同様である*g。

プログラムは以下の結果を出力する:

sol = 0:{{x[0],0},{x[1],1},{x[2],1},{x[3],0},{y[0],0},{y[1],0},{y[2],1},{y[3],0}}
x = x[0] +2*x[1] +4*x[2] +3*x[3] = 6
y = y[0] +2*y[1] +4*y[2] +3*y[3] = 4
f = 100 -19*x[0] -36*x[1] -64*x[2] -51*x[3] -19*y[0] -36*y[1] -64*y[2] -51*y[3] +4*x[0]*x[1] +8*x[0]*x[2] +6*x[0]*x[3] +2*x[0]*y[0] +4*x[0]*y[1] +8*x[0]*y[2] +6*x[0]*y[3] +16*x[1]*x[2] +12*x[1]*x[3] +4*x[1]*y[0] +8*x[1]*y[1] +16*x[1]*y[2] +12*x[1]*y[3] +24*x[2]*x[3] +8*x[2]*y[0] +16*x[2]*y[1] +32*x[2]*y[2] +24*x[2]*y[3] +6*x[3]*y[0] +12*x[3]*y[1] +24*x[3]*y[2] +18*x[3]*y[3] +4*y[0]*y[1] +8*y[0]*y[2] +6*y[0]*y[3] +16*y[1]*y[2] +12*y[1]*y[3] +24*y[2]*y[3] = 0
g = 784 -108*x[0] -208*x[1] -384*x[2] -300*x[3] -208*y[0] -384*y[1] -640*y[2] -528*y[3] +16*x[0]*x[1] +32*x[0]*x[2] +24*x[0]*x[3] +16*x[0]*y[0] +32*x[0]*y[1] +64*x[0]*y[2] +48*x[0]*y[3] +64*x[1]*x[2] +48*x[1]*x[3] +32*x[1]*y[0] +64*x[1]*y[1] +128*x[1]*y[2] +96*x[1]*y[3] +96*x[2]*x[3] +64*x[2]*y[0] +128*x[2]*y[1] +256*x[2]*y[2] +192*x[2]*y[3] +48*x[3]*y[0] +96*x[3]*y[1] +192*x[3]*y[2] +144*x[3]*y[3] +64*y[0]*y[1] +128*y[0]*y[2] +96*y[0]*y[3] +256*y[1]*y[2] +192*y[1]*y[3] +384*y[2]*y[3] = 0
*f = x[0] +2*x[1] +4*x[2] +3*x[3] +y[0] +2*y[1] +4*y[2] +3*y[3] = 10
*g = 2*x[0] +4*x[1] +8*x[2] +6*x[3] +4*y[0] +8*y[1] +16*y[2] +12*y[3] = 28

したがって、 x, y、および制約式 f, g, *f、および *g が解と整合していることを確認できます。

警告 QUBO++ は == 演算子は、左辺が式で右辺が整数の場合にのみサポートされます。 整数 == 式 または 式 == 式 の形式の比較はサポートされていません。 詳細は比較演算子で説明されています。

最終更新日: 2025.12.26