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

このページでは，バイナリエンコーディングによる整数変数を説明します． 整数値をそのまま保持するネイティブ整数変数も利用できます．

整数変数

Hi-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} \]

以下のHi-QUBOプログラムは整数変数の定義方法を示しています:

integer-variables-and-linear-systems-program1.cpp
#include <qbpp/exhaustive_solver.hpp>
#include <qbpp/qbpp.hpp>

int main() {
  auto x = 0 <= qbpp::int_var("x") <= 10;
  auto f = x * x - 4 * x;
  f.simplify_as_binary();
  auto solver = qbpp::ExhaustiveSolver(f);
  auto sol = solver.search();
  std::cout << "x = " << sol(x) << std::endl;
  std::cout << "f = " << sol.energy() << std::endl;
}

整数変数は範囲演算子 **<= <=**を用いて定義され,変数が取りうる整数の範囲を指定します. **qbpp::var_int("name")を範囲演算子と組み合わせた式全体が,指定されたnameを持つqbpp::Expr**オブジェクトを作成し,バイナリ変数でエンコードされた線形式を表現します. プログラムの出力は次のとおりです:

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.

WARNING 整数変数に必要なバイナリ変数の数は,その範囲に対して対数的に増加します. \(u−l\)が大きい場合,QUBOのサイズが増大するため,広い整数範囲はできる限り避けるべきです.

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

Hi-QUBOは,変数を整数変数として表現することで連立方程式を解くことができます. 例として,解が\(x=4\),\(y=6\)である以下の方程式に対するQUBO定式化を構築します:

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

これらの方程式を解くために,範囲\([0,10]\)の整数変数\(x\)と\(y\)を定義し,それぞれ4つのバイナリ変数でエンコードします:

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

以下の各ペナルティ式は,対応する方程式が満たされるとき,かつそのときに限り最小値0をとります:

\[\begin{split} \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} \end{split}\]

したがって,結合式

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

は,両方の方程式が同時に満たされるとき,正確にその最小値0を達成します.

Hi-QUBOプログラム

以下のHi-QUBOプログラムはQUBO式\(h(x,y)\)を構築し,それを解き,結果の\(x\)と\(y\)の値をデコードします:

integer-variables-and-linear-systems-program2.cpp
#include <qbpp/easy_solver.hpp>
#include <qbpp/qbpp.hpp>

int main() {
  auto x = 0 <= qbpp::int_var("x") <= 1000;
  auto y = -1000 <= qbpp::int_var("y") <= 1000;
  auto f = qbpp::sqr(x + 2 * y - 700) + qbpp::sqr(x - y - 100);
  f.simplify_as_binary();
  auto solver = qbpp::EasySolver(f);
  auto sol = solver.search({{"time_limit", 1.0}});
  std::cout << "x = " << sol(x) << ", y = " << sol(y) << std::endl;
  std::cout << "f = " << sol.energy() << std::endl;
}

これにより,x,y,および制約式f,g,f.body(),g.body()の値が解と整合していることが確認できます.

WARNING Hi-QUBOは,左辺が式で右辺が整数の場合にのみ==演算子をサポートしています. 整数==式や式==式の形式の比較はサポートされていません. 詳細は比較演算子で説明しています.

このページでは，バイナリエンコーディングによる整数変数を説明します． 整数値をそのまま保持するネイティブ整数変数も利用できます．

整数変数

PyQBPPは整数変数をサポートしており,内部的には複数のバイナリ変数を用いて実装されています. 整数値の表現には従来のバイナリエンコーディングが使用されます. \(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} \]

以下のプログラムは整数変数の定義方法を示しています.

integer-variables-and-linear-systems-program1.py
import pyqbpp as qbpp

x = qbpp.var("x", integer=(0, 10))
f = x * x - 4 * x
f.simplify_as_binary()
solver = qbpp.ExhaustiveSolver(f)
sol = solver.search()
print(f"x = {sol(x)}")
print(f"f = {sol.energy}")

整数変数は between= キーワード引数を使って定義し,変数がとりうる整数範囲を指定します. qbpp.var("name", between=(min, max)) は,指定された name を持つ整数変数 Expr オブジェクトを作成し,バイナリ変数でエンコードされた線形式を表現します. プログラムの出力は以下の通りです.

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.

注意 整数変数に必要なバイナリ変数の数は,その範囲に対して対数的に増加します. max - min が大きい場合,QUBOのサイズが増大するため,広い整数範囲はできる限り避けるべきです.

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

PyQBPPは,変数を整数変数として表現することで連立方程式を解くことができます. 例として,解が \(x=4\),\(y=6\) である以下の方程式に対するQUBO定式化を構築します.

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

これらの方程式を解くために,範囲 \([0,10]\) の整数変数 \(x\) と \(y\) を定義し,それぞれ4つのバイナリ変数でエンコードします:

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

以下の各ペナルティ式は,対応する方程式が満たされるとき,かつそのときに限り最小値0をとります:

\[\begin{split} \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} \end{split}\]

したがって,結合式

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

は,両方の方程式が同時に満たされるとき,正確にその最小値0を達成します.

PyQBPP プログラム

以下のプログラムはQUBO式 \(h(x,y)\) を構築し,それを解いて結果の \(x\) と \(y\) の値をデコードします.

integer-variables-and-linear-systems-program2.py
import pyqbpp as qbpp

x = qbpp.var("x", integer=(0, 1000))
y = qbpp.var("y", integer=(-1000, 1000))
f = qbpp.sqr(x + 2 * y - 700) + qbpp.sqr(x - y - 100)
f.simplify_as_binary()
solver = qbpp.EasySolver(f)
sol = solver.search(time_limit=1.0)
print(f"x = {sol(x)}, y = {sol(y)}")
print(f"f = {sol.energy}")

これにより,x,y,および制約式 f,g,f.body,g.body の値が解と整合していることが確認できます.

注意 PyQBPPの qbpp.constrain(expr, equal=n) の n には,整数のほか式（Var/Term/Expr）も指定できます. penalty は sqr(expr - n),body は expr になります（例: qbpp.constrain(x + y, equal=2*z)）. 演算子形式の 式 == 式 は直接サポートされていないため,式同士の等価制約には equal= か qbpp.constrain(expr1 - expr2, equal=0) を使ってください. 詳細は比較制約で説明しています.