比較演算子

Hi-QUBOは,制約を作成するための2種類の演算子をサポートしています:

  • 等式演算子: \(f=n\),ここで \(f\) は式,\(n\) は整数.

  • 範囲演算子: \(l\leq f\leq u\),ここで \(f\) は式,\(l\) と \(u\) (\(l\leq u\)) は整数.

これらの演算子は,対応する制約が満たされる場合に限り最小値0をとる式を返します.

等式演算子

等式演算子 \(f=n\) は以下の式を生成します:

\[ (f−n)^2 \]

この式は,等式 \(f=n\) が満たされる場合に限り最小値0をとります.

以下のHi-QUBOプログラムは,Exhaustive Solverを使用して \(a+2b+3c=3\) を満たす全ての解を探索します:

comparison-operators-program1.cpp
#include <qbpp/qbpp.hpp>
#include <qbpp/exhaustive_solver.hpp>

int main() {
  auto a = qbpp::var("a");
  auto b = qbpp::var("b");
  auto c = qbpp::var("c");
  auto f = a + 2 * b + 3 * c == 3;
  f.simplify_as_binary();
  std::cout << "f = " << f << std::endl;
  std::cout << "f.body() = " << f.body() << std::endl;

  auto solver = qbpp::ExhaustiveSolver(f);
  auto sols = solver.search({{"best_energy_sols", 0}});
  for (const auto& sol : sols) {
    std::cout << "a = " << a(sol) << ", b = " << b(sol) << ", c = " << c(sol)
              << ", f = " << f(sol) << ", f.body() = " << f.body(sol) << std::endl;
  }
}

このプログラムでは,f は内部的に2つの qbpp::Expr オブジェクトを保持しています:

  • f: \((a+2b+3c−3)^2\),等式 \(a+2b+3c=3\) が満たされる場合に最小値0をとります.

  • f.body(): 等式の左辺,\(a+2b+3c\).

f に対して作成されたExhaustive Solverオブジェクトを使用し,全ての最適解が sols に格納されます. sols を反復処理することで,全ての解と f および f.body() の値が以下のように出力されます:

f = 9 -5*a -8*b -9*c +4*a*b +6*a*c +12*b*c
f.body() = a +2*b +3*c
a = 0, b = 0, c = 1, f = 0, f.body() = 3
a = 1, b = 1, c = 0, f = 0, f.body() = 3

これらの結果から,2つの最適解が f = 0 を達成し,f.body() = 3 を満たしていることが確認できます.

サポートされる等式の形式に関する注意

Hi-QUBOは等式演算子を以下の形式でのみサポートしています:

  • expression == integer

以下の形式はサポートされていません:

  • integer == expression

  • expression1 == expression2

expression1 == expression2 の代わりに,以下のように書き換えることができます:

  • expression1 - expression2 == 0

これは完全にサポートされています.

範囲演算子

Hi-QUBO は \(l\leq f \leq u\) (\(l\leq u\)) の形式の両側範囲演算子をサポートします:

  • 範囲演算子: \(l \leq f \leq u\) — l <= expr <= u と書きます

この演算子は,制約が満たされる場合に限り最小値0をとる式を生成します.

注意 l <= expr <= u のチェイン構文は両端の境界が整数リテラルである必要があります. 片側の境界を無限にしたい場合は,後述の片側演算子 (expr >= l または expr <= u) を使ってください.l <= expr <= +qbpp::inf や -qbpp::inf <= expr <= u の代わりに 推奨される書き方です.

\(l\) と \(u\) の値に応じて,以下の場合分けを考えます.

  • 場合1: \(u=l\)

  • 場合2: \(u=l+1\)

  • 場合3: \(u=l+2\)

  • 場合4: \(u\geq l+3\)

場合1: \(u=l\)

\(u=l\) の場合,範囲制約は等式制約 \(f=l\) に帰着し,等式演算子を直接使用して実装できます.

場合2: \(u=l+1\)

\(u=l+1\) の場合,以下の式が生成されます:

\[ (f-l)(f-u) \]

\(l\) と \(u\) の間に整数が存在しないため,この式は \(f=l\) または \(f=u\) の場合に限り最小値0をとります.

場合3: \(u=l+2\)

補助バイナリ変数 \(a \in \lbrace 0,1\rbrace\) を導入し,以下の式を使用します:

\[ \begin{aligned} (f-l-a)(f-l-(a+1)) \end{aligned} \]

この式は \(f=l\), \(l+1\), \(l+2\) に対して以下のように評価されます:

\[\begin{split} \begin{aligned} (f-l-a)(f-l-(a+1)) &= (-a)(-(a+1)) && \text{if } f=l \\ &= (1-a)(-a) && \text{if } f=l+1 \\ &=(2-a)(1-a) && \text{if } f=l+2 \end{aligned} \end{split}\]

全ての場合において,\(a\) の適切な選択により最小値0が達成可能です. したがって,\(l\leq f\leq u\) が満たされる場合,この式は最小値0をとります.

\(g = f-l-a\) とおくと,

\[ \begin{aligned} (f-l-a)(f-l-(a+1)) &= g(g-1) \end{aligned} \]

となり,\(g\leq -1\) または \(g\geq 2\) の場合は常に正の値をとります. したがって,この式は \(l\leq f\leq u\) が満たされる場合に限り最小値0をとります.

場合4: \(u\geq l+3\)

範囲 \([l,u−1]\) の整数値をとる補助整数変数 \(a\) を導入します. このような整数変数は,整数変数と連立方程式の求解で説明されているように,複数のバイナリ変数を用いて定義できます.

この場合の式は:

\[ \begin{aligned} (f-a)(f-(a+1)) \end{aligned} \]

場合3と同様に,\(f\) が \([l,u]\) に含まれない場合,この式は常に正の値をとることが示せます.

\(f\) が範囲 \([l,u]\) の整数値をとると仮定します. \(a=f\) を選ぶと,

\[\begin{split} \begin{aligned} f-a &= 0 & {\rm if\,\,} f\in [l,u-1]\\ f-(a+1) &= 0& {\rm if\,\,} f\in [l+1,u] \end{aligned} \end{split}\]

したがって,任意の \(f\in[l,u]\) に対して \(f−a=0\) または \(f−(a+1)=0\) のいずれかが成り立ちます. よって,\((f−a)(f−(a+1))\) は \(l\leq f\leq u\) の場合に限り最小値0をとります.

バイナリ変数数の削減

整数変数と連立方程式の求解では,整数変数 \(a\in [l,u]\) は \(n\) 個のバイナリ変数 \(x_0, x_1, \ldots, x_{n-1}\) を用いて以下のように表現されます:

\[ \begin{aligned} a & = 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\) までの全ての整数を表現できます. したがって,以下を満たすように \(n\) と \(d\) を選ぶことができます:

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

場合4では,Hi-QUBOは代わりに \(n-1\) 個のバイナリ変数 \(x_1, \ldots, x_{n-1}\) を用いた以下の線形式を使用します:

\[ \begin{aligned} a &= l+2^1x_1+\cdots +2^{n-2}x_{n-2}+dx_{n-1} \end{aligned} \]

この式は \(l\) から \(l+2^{n-1}+d-2\) までの整数を表現します. それに応じて,以下を満たすように \(n\) と \(d\) を選びます:

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

このような整数変数 \(a\) をユニットギャップ整数変数と呼びます. \([l,u]\) 内の一部の値は \(a\) で表現できませんが,表現できない任意の \(k\in[l,u]\) に対して \(k−1\) は表現可能です. したがって,\(a\) または \(a+1\) は範囲 \([l,u]\) の任意の値をとることができ,範囲制約の適用には十分です.

4つの場合のHi-QUBOプログラム

以下のプログラムは,Hi-QUBOにおける4つの場合の実装を示しています:

comparison-operators-program2.cpp
#include <qbpp/qbpp.hpp>

int main() {
  auto f = qbpp::toExpr(qbpp::var("f"));
  auto f1 = 1 <= f <= 1;
  auto f2 = 1 <= f <= 2;
  auto f3 = 1 <= f <= 3;
  auto f4 = 1 <= f <= 5;
  std::cout << "f1 = " << f1.simplify() << std::endl;
  std::cout << "f2 = " << f2.simplify() << std::endl;
  std::cout << "f3 = " << f3.simplify() << std::endl;
  std::cout << "f4 = " << f4.simplify() << std::endl;
}

このプログラムは以下の出力を生成します:

f1 = 1 -2*f +f*f
f2 = 2 -3*f +f*f
f3 = 2 -3*f +3*{s0} +f*f -2*f*{s0} +{s0}*{s0}
f4 = 2 -3*f +6*{s1}[0] +3*{s1}[1] +f*f -4*f*{s1}[0] -2*f*{s1}[1] +4*{s1}[0]*{s1}[0] +4*{s1}[0]*{s1}[1] +{s1}[1]*{s1}[1]

これらの出力は以下の式に対応します:

\[\begin{split} \begin{aligned} f_1 &= (f-1)^2\\ f_2 &= (f-1)(f-2)\\ f_3 &= (f-x_0)(f-(x_0+1))\\ f_4 &= (f-(2x_{1,0}+x_{1,1}+1))(f-(2x_{1,0}+x_{1,1}+2)) \end{aligned} \end{split}\]

範囲演算子を使用するHi-QUBOプログラム

以下のプログラムは,Hi-QUBOにおける範囲演算子の使用方法を示しています:

comparison-operators-program3.cpp
#include <qbpp/qbpp.hpp>
#include <qbpp/exhaustive_solver.hpp>

int main() {
  auto a = qbpp::var("a");
  auto b = qbpp::var("b");
  auto c = qbpp::var("c");
  auto f = 5 <= 4 * a + 9 * b + 15 * c <= 14;
  f.simplify_as_binary();
  auto solver = qbpp::ExhaustiveSolver(f);
  auto sols = solver.search({{"best_energy_sols", 0}});
  for (const auto& sol : sols) {
    std::cout << "a = " << a(sol) << ", b = " << b(sol) << ", c = " << c(sol)
              << ", f = " << f(sol) << ", f.body() = " << f.body(sol)
              << ", sol = " << sol << std::endl;
  }
}

3つのバイナリ変数 \(a\), \(b\), \(c\) に対して,このプログラムは以下の制約を満たす解を探索します:

\[ \begin{aligned} 5\leq 4a+9b+15c \leq 14 \end{aligned} \]

このプログラムは以下の出力を生成します:

a = 0, b = 1, c = 0, f = 0, f.body() = 9, sol = 0:{{a,0},{b,1},{c,0},{{0}[0],0},{{0}[1],1},{{0}[2],0}}
a = 0, b = 1, c = 0, f = 0, f.body() = 9, sol = 0:{{a,0},{b,1},{c,0},{{0}[0],1},{{0}[1],0},{{0}[2],1}}
a = 1, b = 1, c = 0, f = 0, f.body() = 13, sol = 0:{{a,1},{b,1},{c,0},{{0}[0],1},{{0}[1],1},{{0}[2],1}}

下界・上界演算子

Hi-QUBOは以下の片側境界演算子をサポートしています:

  • 下界演算子: \(l\leq f\) — expr >= n と書きます (n <= expr <= +qbpp::inf の代わりに使えます)

  • 上界演算子: \(f\leq u\) — expr <= n と書きます (-qbpp::inf <= expr <= n の代わりに使えます)

注意 整数を左辺に置いた n >= expr はコンパイルエラーになります. n <= expr はチェイン形 l <= expr <= u 専用の中間値を返すため,単独の片側制約としては使えません. 片側制約を書くときは常に式を <= / >= の左側に置いてください.

範囲演算子は内部的に補助変数を導入するため,真の無限大は明示的に表現できません. チェイン形 (後方互換用に残されています) で qbpp::inf を用いると,Hi-QUBOは式 \(f\) の有限の最大値と最小値を推定し,それぞれ \(+\infty\) と \(-\infty\) の代わりに使用します.

例えば,以下の式を考えます:

\[ \begin{aligned} f=4a + 9 b + 11 c \end{aligned} \]

ここで \(a\), \(b\), \(c\) はバイナリ変数です. \(f\) の取りうる最小値と最大値はそれぞれ0と24です. したがって,Hi-QUBOは対応する範囲制約を構築する際に,\(-\infty\) と \(+\infty\) の代わりに0と24を使用します.

下界・上界演算子のHi-QUBOプログラム

以下のプログラムは下界演算子を示しています:

comparison-operators-program4.cpp
#include <qbpp/qbpp.hpp>
#include <qbpp/exhaustive_solver.hpp>

int main() {
  auto a = qbpp::var("a");
  auto b = qbpp::var("b");
  auto c = qbpp::var("c");
  auto f = 4 * a + 9 * b + 11 * c >= 14;
  f.simplify_as_binary();
  auto solver = qbpp::ExhaustiveSolver(f);
  auto sols = solver.search({{"best_energy_sols", 0}});
  for (const auto& sol : sols) {
    std::cout << "a = " << a(sol) << ", b = " << b(sol) << ", c = " << c(sol)
              << ", f = " << f(sol) << ", f.body() = " << f.body(sol)
              << ", sol = " << sol << std::endl;
  }
}

このプログラムでは,f は単独下界演算子 >= で構築されています.上界は内部で expr.pos_sum() = 24 (本体が取りうる最大値) に設定されるので,14 <= 4 * a + 9 * b + 11 * c <= +qbpp::inf と書いた場合と等価です.

このプログラムは以下の出力を生成します:

a = 1, b = 0, c = 1, f = 0, f.body() = 15, sol = 0:{{a,1},{b,0},{c,1},{{s0}[0],0},{{s0}[1],0},{{s0}[2],0}}
a = 0, b = 1, c = 1, f = 0, f.body() = 20, sol = 0:{{a,0},{b,1},{c,1},{{s0}[0],1},{{s0}[1],1},{{s0}[2],0}}
a = 0, b = 1, c = 1, f = 0, f.body() = 20, sol = 0:{{a,0},{b,1},{c,1},{{s0}[0],1},{{s0}[1],0},{{s0}[2],1}}
a = 1, b = 1, c = 1, f = 0, f.body() = 24, sol = 0:{{a,1},{b,1},{c,1},{{s0}[0],1},{{s0}[1],1},{{s0}[2],1}}

以下のプログラムは上界演算子を示しています:

comparison-operators-program5.cpp
int main() {
  auto a = qbpp::var("a");
  auto b = qbpp::var("b");
  auto c = qbpp::var("c");
  auto f = 4 * a + 9 * b + 11 * c <= 14;
  f.simplify_as_binary();
  auto solver = qbpp::ExhaustiveSolver(f);
  auto sols = solver.search({{"best_energy_sols", 0}});
  for (const auto& sol : sols) {
    std::cout << "a = " << a(sol) << ", b = " << b(sol) << ", c = " << c(sol)
              << ", f = " << f(sol) << ", f.body() = " << f.body(sol)
              << ", sol = " << sol << std::endl;
  }
}

このプログラムでは,f は単独上界演算子 <= で構築されています.下界は内部で expr.neg_sum() = 0 (本体が取りうる最小値) に設定されるので,-qbpp::inf <= 4 * a + 9 * b + 11 * c <= 14 と書いた場合と等価です.

このプログラムは以下の出力を生成します:

a = 0, b = 0, c = 0, f = 0, f.body() = 0, sol = 0:{{a,0},{b,0},{c,0},{{s0}[0],0},{{s0}[1],0},{{s0}[2],0}}
a = 1, b = 0, c = 0, f = 0, f.body() = 4, sol = 0:{{a,1},{b,0},{c,0},{{s0}[0],0},{{s0}[1],1},{{s0}[2],0}}
a = 0, b = 1, c = 0, f = 0, f.body() = 9, sol = 0:{{a,0},{b,1},{c,0},{{s0}[0],1},{{s0}[1],0},{{s0}[2],1}}
a = 0, b = 0, c = 1, f = 0, f.body() = 11, sol = 0:{{a,0},{b,0},{c,1},{{s0}[0],0},{{s0}[1],1},{{s0}[2],1}}
a = 1, b = 1, c = 0, f = 0, f.body() = 13, sol = 0:{{a,1},{b,1},{c,0},{{s0}[0],1},{{s0}[1],1},{{s0}[2],1}}

PyQBPPは,2種類の制約をサポートしています:

  • 等式制約: qbpp.constrain(f, equal=n),ここで f は式,n は整数.

  • 範囲制約: qbpp.constrain(f, between=(l, u)),ここで f は式,l と u (\(l\leq u\)) は整数.

いずれも,対応する制約が満たされる場合に限り最小値0をとる制約式を返します.

等式制約

等式制約 qbpp.constrain(f, equal=n) は以下の式を生成します:

\[ (f-n)^2 \]

この式は,等式 \(f=n\) が満たされる場合に限り最小値0をとります.

以下のPyQBPPプログラムは,Exhaustive Solverを使用して \(a+2b+3c=3\) を満たす全ての解を探索します:

comparison-operators-program1.py
import pyqbpp as qbpp

a = qbpp.var("a")
b = qbpp.var("b")
c = qbpp.var("c")
f = qbpp.constrain(a + 2 * b + 3 * c, equal=3)
f.simplify_as_binary()
print("f =", f)
print("body =", f.body)

solver = qbpp.ExhaustiveSolver(f)
result = solver.search(best_energy_sols=0)
for sol in result.sols:
    print(f"a={sol(a)}, b={sol(b)}, c={sol(c)}, "
          f"f={sol(f)}, body={sol(f.body)}")

このプログラムでは,f は内部的に2つの式を保持しています:

  • f: \((a+2b+3c-3)^2\),等式 \(a+2b+3c=3\) が満たされる場合に最小値0をとります.

  • f.body: 等式の左辺,\(a+2b+3c\).

f に対して作成されたExhaustive Solverを使用し,全ての最適解が result.sols に格納されます. result.sols を反復処理することで,全ての解と f および f.body の値が以下のように出力されます:

f = 9 -5*a -8*b -9*c +4*a*b +6*a*c +12*b*c
body = a +2*b +3*c
a=0, b=0, c=1, f=0, body=3
a=1, b=1, c=0, f=0, body=3

これらの結果から,2つの最適解が f = 0 を達成し,body = 3 を満たしていることが確認できます.

サポートされる等式の形式に関する注意

PyQBPPは等式制約を以下の2つの等価な形式でサポートしています:

expression1 == expression2（両辺が式）の形式は直接サポートされていません. 代わりに,以下のように書き換えてください:

  • qbpp.constrain(expression1 - expression2, equal=0) — または等価に (expression1 - expression2) == 0

これらは完全にサポートされています.

範囲制約

範囲制約 qbpp.constrain(f, between=(l, u)) (\(l\leq u\)) は,制約が満たされる場合に限り最小値0をとる式を生成します.

\(l\) と \(u\) の値に応じて,以下の場合分けを考えます.

  • 場合1: \(u=l\)

  • 場合2: \(u=l+1\)

  • 場合3: \(u=l+2\)

  • 場合4: \(u\geq l+3\)

場合1: \(u=l\)

\(u=l\) の場合,範囲制約は等式制約 \(f=l\) に帰着し,等式制約を直接使用して実装できます.

場合2: \(u=l+1\)

\(u=l+1\) の場合,以下の式が生成されます:

\[ (f-l)(f-u) \]

\(l\) と \(u\) の間に整数が存在しないため,この式は \(f=l\) または \(f=u\) の場合に限り最小値0をとります.

場合3: \(u=l+2\)

補助バイナリ変数 \(a \in \lbrace 0,1\rbrace\) を導入し,以下の式を使用します:

\[ \begin{aligned} (f-l-a)(f-l-(a+1)) \end{aligned} \]

この式は \(f=l\), \(l+1\), \(l+2\) に対して以下のように評価されます:

\[\begin{split} \begin{aligned} (f-l-a)(f-l-(a+1)) &= (-a)(-(a+1)) && \text{if } f=l \\ &= (1-a)(-a) && \text{if } f=l+1 \\ &=(2-a)(1-a) && \text{if } f=l+2 \end{aligned} \end{split}\]

全ての場合において,\(a\) の適切な選択により最小値0が達成可能です. したがって,\(l\leq f\leq u\) が満たされる場合,この式は最小値0をとります.

\(g = f-l-a\) とおくと,

\[ \begin{aligned} (f-l-a)(f-l-(a+1)) &= g(g-1) \end{aligned} \]

となり,\(g\leq -1\) または \(g\geq 2\) の場合は常に正の値をとります. したがって,この式は \(l\leq f\leq u\) が満たされる場合に限り最小値0をとります.

場合4: \(u\geq l+3\)

範囲 \([l,u-1]\) の整数値をとる補助整数変数 \(a\) を導入します. このような整数変数は,整数変数と連立方程式の求解で説明されているように,複数のバイナリ変数を用いて定義できます.

この場合の式は:

\[ \begin{aligned} (f-a)(f-(a+1)) \end{aligned} \]

場合3と同様に,\(f\) が \([l,u]\) に含まれない場合,この式は常に正の値をとることが示せます.

\(f\) が範囲 \([l,u]\) の整数値をとると仮定します. \(a=f\) を選ぶと,

\[\begin{split} \begin{aligned} f-a &= 0 & {\rm if\,\,} f\in [l,u-1]\\ f-(a+1) &= 0& {\rm if\,\,} f\in [l+1,u] \end{aligned} \end{split}\]

したがって,任意の \(f\in[l,u]\) に対して \(f-a=0\) または \(f-(a+1)=0\) のいずれかが成り立ちます. よって,\((f-a)(f-(a+1))\) は \(l\leq f\leq u\) の場合に限り最小値0をとります.

バイナリ変数数の削減

整数変数と連立方程式の求解では,整数変数 \(a\in [l,u]\) は \(n\) 個のバイナリ変数 \(x_0, x_1, \ldots, x_{n-1}\) を用いて以下のように表現されます:

\[ \begin{aligned} a & = 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\) までの全ての整数を表現できます. したがって,以下を満たすように \(n\) と \(d\) を選ぶことができます:

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

場合4では,PyQBPPは代わりに \(n-1\) 個のバイナリ変数 \(x_1, \ldots, x_{n-1}\) を用いた以下の線形式を使用します:

\[ \begin{aligned} a &= l+2^1x_1+\cdots +2^{n-2}x_{n-2}+dx_{n-1} \end{aligned} \]

この式は \(l\) から \(l+2^{n-1}+d-2\) までの整数を表現します. それに応じて,以下を満たすように \(n\) と \(d\) を選びます:

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

このような整数変数 \(a\) をユニットギャップ整数変数と呼びます. \([l,u]\) 内の一部の値は \(a\) で表現できませんが,表現できない任意の \(k\in[l,u]\) に対して \(k-1\) は表現可能です. したがって,\(a\) または \(a+1\) は範囲 \([l,u]\) の任意の値をとることができ,範囲制約の適用には十分です.

4つの場合のPyQBPPプログラム

以下のプログラムは,PyQBPPにおける4つの場合の実装を示しています:

comparison-operators-program2.py
import pyqbpp as qbpp

f = qbpp.var("f")
f1 = qbpp.constrain(f, between=(1, 1))
f2 = qbpp.constrain(f, between=(1, 2))
f3 = qbpp.constrain(f, between=(1, 3))
f4 = qbpp.constrain(f, between=(1, 5))
f1.simplify()
f2.simplify()
f3.simplify()
f4.simplify()
print("f1 =", f1)
print("f2 =", f2)
print("f3 =", f3)
print("f4 =", f4)

このプログラムは以下の出力を生成します:

f1 = 1 -2*f +f*f
f2 = 2 -3*f +f*f
f3 = 2 -3*f +3*{s0} +f*f -2*f*{s0} +{s0}*{s0}
f4 = 2 -3*f +6*{s1}[0] +3*{s1}[1] +f*f -4*f*{s1}[0] -2*f*{s1}[1] +4*{s1}[0]*{s1}[0] +4*{s1}[0]*{s1}[1] +{s1}[1]*{s1}[1]

これらの出力は以下の式に対応します:

\[\begin{split} \begin{aligned} f_1 &= (f-1)^2\\ f_2 &= (f-1)(f-2)\\ f_3 &= (f-x_0)(f-(x_0+1))\\ f_4 &= (f-(2x_{1,0}+x_{1,1}+1))(f-(2x_{1,0}+x_{1,1}+2)) \end{aligned} \end{split}\]

範囲制約を使用するPyQBPPプログラム

以下のプログラムは,PyQBPPにおける範囲制約の使用方法を示しています:

comparison-operators-program3.py
import pyqbpp as qbpp

a = qbpp.var("a")
b = qbpp.var("b")
c = qbpp.var("c")
f = qbpp.constrain(4 * a + 9 * b + 15 * c, between=(5, 14))
f.simplify_as_binary()
solver = qbpp.ExhaustiveSolver(f)
result = solver.search(best_energy_sols=0)
for sol in result.sols:
    print(f"a={sol(a)}, b={sol(b)}, c={sol(c)}, "
          f"f={sol(f)}, body={sol(f.body)}, sol={sol}")

3つのバイナリ変数 \(a\), \(b\), \(c\) に対して,このプログラムは以下の制約を満たす解を探索します:

\[ \begin{aligned} 5\leq 4a+9b+15c \leq 14 \end{aligned} \]

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

a=0, b=1, c=0, f=0, body=9, sol=Sol(energy=0, {a: 0, b: 1, c: 0, {s0}[0]: 0, {s0}[1]: 1, {s0}[2]: 0})
a=0, b=1, c=0, f=0, body=9, sol=Sol(energy=0, {a: 0, b: 1, c: 0, {s0}[0]: 1, {s0}[1]: 0, {s0}[2]: 1})
a=1, b=1, c=0, f=0, body=13, sol=Sol(energy=0, {a: 1, b: 1, c: 0, {s0}[0]: 1, {s0}[1]: 1, {s0}[2]: 1})

下界・上界制約

PyQBPPは以下の片側境界制約を独立した構文としては直接サポートしていません. 代わりに,PyQBPPは between の境界値を None とすることでこれらをサポートします:

  • 下界制約: between=(l, None) → \(l\leq f\leq +\infty\)

  • 上界制約: between=(None, u) → \(-\infty \leq f\leq u\)

範囲制約は内部的に補助変数を導入するため,真の無限大は明示的に表現できません. そのため,PyQBPPは式 \(f\) の有限の最大値と最小値を推定し,それぞれ \(+\infty\) と \(-\infty\) の代わりに使用します.

例えば,以下の式を考えます:

\[ \begin{aligned} f=4a + 9 b + 11 c \end{aligned} \]

ここで \(a\), \(b\), \(c\) はバイナリ変数です. \(f\) の取りうる最小値と最大値はそれぞれ0と24です. したがって,PyQBPPは対応する範囲制約を構築する際に,\(-\infty\) と \(+\infty\) の代わりに0と24を使用します.

注釈 qbpp.constrain(f, between=(l, None)) や qbpp.constrain(f, between=(None, u)) を使う場合, PyQBPPはQUBOスタイルの解釈を採用します.すなわち,None 側は \(f\) の係数から導かれる 構造的な境界（全変数がバイナリのときに \(f\) が取りうる最大値・最小値）で置き換えられます. これは MIPスタイルの解釈（例: \(f\leq u\) を \(0\leq f\leq u\) と解釈する流儀）とは異なります. QUBOスタイルを採用しているのは,ユーザーが書いた以上の暗黙の制約を勝手に追加しないためです.

下界・上界制約のPyQBPPプログラム

PyQBPPでは,無限大の値は between の対応する側の None で表現されます.

以下のプログラムは下界制約を示しています:

comparison-operators-program4.py
import pyqbpp as qbpp

a = qbpp.var("a")
b = qbpp.var("b")
c = qbpp.var("c")
f = qbpp.constrain(4 * a + 9 * b + 11 * c, between=(14, None))
f.simplify_as_binary()
solver = qbpp.ExhaustiveSolver(f)
result = solver.search(best_energy_sols=0)
for sol in result.sols:
    print(f"a={sol(a)}, b={sol(b)}, c={sol(c)}, "
          f"f={sol(f)}, body={sol(f.body)}, sol={sol}")

このプログラムでは,between=(14, None) の None は正の無限大を表し,自動的に24に置き換えられます.

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

a=1, b=0, c=1, f=0, body=15, sol=Sol(energy=0, {a: 1, b: 0, c: 1, {s0}[0]: 0, {s0}[1]: 0, {s0}[2]: 0})
a=0, b=1, c=1, f=0, body=20, sol=Sol(energy=0, {a: 0, b: 1, c: 1, {s0}[0]: 1, {s0}[1]: 1, {s0}[2]: 0})
a=0, b=1, c=1, f=0, body=20, sol=Sol(energy=0, {a: 0, b: 1, c: 1, {s0}[0]: 1, {s0}[1]: 0, {s0}[2]: 1})
a=1, b=1, c=1, f=0, body=24, sol=Sol(energy=0, {a: 1, b: 1, c: 1, {s0}[0]: 1, {s0}[1]: 1, {s0}[2]: 1})

以下のプログラムは上界制約を示しています:

comparison-operators-program5.py
import pyqbpp as qbpp

a = qbpp.var("a")
b = qbpp.var("b")
c = qbpp.var("c")
f = qbpp.constrain(4 * a + 9 * b + 11 * c, between=(None, 14))
f.simplify_as_binary()
solver = qbpp.ExhaustiveSolver(f)
result = solver.search(best_energy_sols=0)
for sol in result.sols:
    print(f"a={sol(a)}, b={sol(b)}, c={sol(c)}, "
          f"f={sol(f)}, body={sol(f.body)}, sol={sol}")

このプログラムでは,between=(None, 14) の None は負の無限大を表し,自動的に0に置き換えられます.

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

a=0, b=0, c=0, f=0, body=0, sol=Sol(energy=0, {a: 0, b: 0, c: 0, {s0}[0]: 0, {s0}[1]: 0, {s0}[2]: 0})
a=1, b=0, c=0, f=0, body=4, sol=Sol(energy=0, {a: 1, b: 0, c: 0, {s0}[0]: 0, {s0}[1]: 1, {s0}[2]: 0})
a=0, b=1, c=0, f=0, body=9, sol=Sol(energy=0, {a: 0, b: 1, c: 0, {s0}[0]: 1, {s0}[1]: 0, {s0}[2]: 1})
a=0, b=0, c=1, f=0, body=11, sol=Sol(energy=0, {a: 0, b: 0, c: 1, {s0}[0]: 0, {s0}[1]: 1, {s0}[2]: 1})
a=1, b=1, c=0, f=0, body=13, sol=Sol(energy=0, {a: 1, b: 1, c: 0, {s0}[0]: 1, {s0}[1]: 1, {s0}[2]: 1})

演算子による省略構文

利便性のため,PyQBPPは式と整数の間の比較演算子 ==, <=, >= も受け付けます. これらは qbpp.constrain() の単なる糖衣構文であり,同等の制約式を生成します:

演算子による形式

等価な qbpp.constrain() 形式

生成される penalty

f == n

qbpp.constrain(f, equal=n)

\((f-n)^2\)

f <= n

qbpp.constrain(f, between=(None, n))

\(\min(f) \leq f \leq n\) のとき \(0\)

f >= n

qbpp.constrain(f, between=(n, None))

\(n \leq f \leq \max(f)\) のとき \(0\)

ここで \(\min(f)\) と \(\max(f)\) は \(f\) の係数から導かれる構造的な境界であり,上記の 下界・上界制約で説明したルールに従います. 反転形式 n <= f, n >= f も Python の標準的な反射規則により動作します.

例えば,上の上界制約のプログラムは次のように書き換えられます:

comparison-operators-program6.py
import pyqbpp as qbpp

a = qbpp.var("a")
b = qbpp.var("b")
c = qbpp.var("c")
f = (4 * a + 9 * b + 11 * c) <= 14   # qbpp.constrain(..., between=(None, 14)) と等価
f.simplify_as_binary()

これらの演算子は式の配列に対しても定義されており,その場合は要素ごとに制約が適用され, 制約式の配列が返されます.

注釈 右辺には int のみを受け付けます.expression1 <= expression2 の形式はサポートされておらず, (expression1 - expression2) <= 0 に書き換えるか,qbpp.constrain() で between= 範囲を 明示的に指定してください.x == 3 のように裸の Var/Term と整数の比較も制約式になります. ただし var1 == var2 のような変数同士の比較は同一性判定（辞書のキーとして使うために bool を返すもの）のままで,制約にはなりません.

qbpp.same による範囲制約の連鎖記法

qbpp.constrain(f, between=(l, u)) を書くもう一つの方法として,上界制約と下界制約を & で連結する記法が用意されています. ここで,もう一方の側にある式 f をプレースホルダ qbpp.same で参照します:

(l <= f) & (qbpp.same <= u)        # qbpp.constrain(f, between=(l, u)) と等価
(qbpp.same >= l) & (f <= u)        # 同上

<= / >= の向きや左右はどの組合せでも構いません.& の左右どちらに qbpp.same を置いても解釈されます.

qbpp.same を介在させる理由は,f が大きな式や配列の場合でも,両側の制約に対して補助変数を 1 組だけ生成するためです. qbpp.constrain(f, between=(l, u)) と完全に同じ QUBO 式が得られます（補助変数の割り当ても同一です — 片側制約は & で合流するまで補助変数を確保しない遅延評価のため）.

連鎖記法のPyQBPPプログラム

以下のプログラムは,範囲制約を使用するPyQBPPプログラム と同じ制約 \(5 \leq 4a + 9b + 15c \leq 14\) を連鎖記法で書いたものです:

comparison-operators-program7.py
import pyqbpp as qbpp

a = qbpp.var("a")
b = qbpp.var("b")
c = qbpp.var("c")
f = (5 <= 4 * a + 9 * b + 15 * c) & (qbpp.same <= 14)
f.simplify_as_binary()
solver = qbpp.ExhaustiveSolver(f)
result = solver.search(best_energy_sols=0)
for sol in result.sols:
    print(f"a={sol(a)}, b={sol(b)}, c={sol(c)}, "
          f"f={sol(f)}, body={sol(f.body)}, sol={sol}")

qbpp.constrain(4*a + 9*b + 15*c, between=(5, 14)) を使った版と同一の出力が得られます.

配列に対する連鎖記法

qbpp.same は式の配列に対しても使えます.配列の各要素に同じ範囲制約が適用され,制約式の配列が返されます:

x = qbpp.var("x", shape=3)
fs = qbpp.array([2 * x[0], x[1] + x[2], 3 * x[0] + x[1]])
constraints = (1 <= fs) & (qbpp.same <= 2)   # fs の各要素に 1 ≤ ... ≤ 2 を適用
total = qbpp.sum(constraints)

サポートされない形式

両側に同じ式を書いた (l <= f) & (f <= u) の形式はサポートされていません.連鎖記法では片側を qbpp.same にしてください.