比較演算子

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 を達成する。

以下の QUBO++ プログラムは、 $a+2b+3c=3$ を満たすすべての解を、網羅的ソルバーを用いて探索します：

#include "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 = " << *f << std::endl;

  auto solver = qbpp::exhaustive_solver::ExhaustiveSolver(f);
  auto sols = solver.search_optimal_solutions();
  for (const auto& sol : sols) {
    std::cout << "a = " << a(sol) << ", b = " << b(sol) << ", c = " << c(sol)
              << ", f = " << f(sol) << ", *f = " << (*f)(sol) << std::endl;
  }
}

このプログラムでは、 f 内部で2つのqbpp::Exprオブジェクトを保持している：

f: $(a+2b+3c−3)^2$（等式 $a+2b+3c=3$ が成立する場合に最小値 0 を取る）
*f: 等式の左辺、$a+2b+3c$。

作成された網羅的ソルバーオブジェクト fすべての最適解がに格納されますsols。を反復処理することで solsを反復処理することで、全ての解と f および *f の値を反復処理することで、以下の通り出力される：

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

これらの結果は、2つの最適解が f = 0 を満たし、 *f = 3.

等号演算子のサポート形式に関する注記

QUBO++ は等号演算子を以下の形式でのみサポートします:

expression == integer.

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

integer == expression
expression1 == expression2

代わりに expression1 == expression2の代わりに、制約を次のように書き換えることができます:

expression1 - expression2 == 0

この形式は完全にサポートされています。

範囲演算子

$l\leq f \leq 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$ の間に厳密に介在する整数がないため、この式が最小値 0 を取る条件は $f=l$ または $f=u$ である場合に限られる。

ケース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{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}\]

いずれの場合も、$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$ の場合に常に正となる。したがって、式が最小値 0 を取る条件は、$l\leq f\leq u$ が満たされることと同値である。

ケース4: $u\geq l+3$

補助整数変数 $a$ を導入する。$a$ は整数範囲 $[l,u−1]$ で値を取る。このような整数変数は、複数の二進変数を用いて定義できる（詳細は「整数変数と連立方程式の解法」を参照）。

この場合の式は次の通りである：

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

ケース3と同様に、$f$が$[l,u]$に属さない場合、この式は常に正であることを示せる。

$f$ が整数値を取り得る範囲が $[l,u]$ であると仮定する。 $a=f$ を選択すると、

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

したがって、任意の $f\in[l,u]$ に対して $f−a=0$ または $f−(a+1)=0$ が成り立つ。よって、$(f−a)(f−(a+1))$ が最小値 0 を取る条件は、 $l\leq f\leq u$ であることである。

二進変数の数の削減

整数変数と連立方程式の解法において、整数変数 $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では、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$ を表現できる。したがって、$[l,u]$の範囲内の任意の値は、$a$または$a+1$のいずれかが取り得る。これは範囲制約を強制するのに十分である。

4つのケースに対するQUBO++プログラム

以下のプログラムは、4つのケースがQUBO++で実装される方法を示す：

#include "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*{0} +f*f -2*f*{0} +{0}*{0}
f4 = 2 -3*f +6*{1}[0] +3*{1}[1] +f*f -4*f*{1}[0] -2*f*{1}[1] +4*{1}[0]*{1}[0] +4*{1}[0]*{1}[1] +{1}[1]*{1}[1]

これらの出力は次の式に対応する:

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

範囲演算子を使用したQUBO++プログラム

以下のプログラムは、QUBO++における範囲演算子の使用例を示します：

#include "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::exhaustive_solver::ExhaustiveSolver(f);
  auto sols = solver.search_optimal_solutions();
  for (const auto& sol : sols) {
    std::cout << "a = " << a(sol) << ", b = " << b(sol) << ", c = " << c(sol)
              << ", f = " << f(sol) << ", *f = " << (*f)(sol)
              << ", sol = " << sol << std::endl;
  }
}

3つの二値変数 $a$、$b$、$c$ に対し、このプログラムは次の制約を満たす解を検索する

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

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

a = 0, b = 1, c = 0, f = 0, *f = 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 = 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 = 13, sol = 0:{{a,1},{b,1},{c,0},{{0}[0],1},{{0}[1],1},{{0}[2],1}}

下限および上限演算子

QUBO++は、以下の片側境界演算子を直接サポートしていません:

下限演算子: $l\leq f$
上限演算子: $f\leq u$

代わりに、QUBO++ は無限大の記号表現 ($\infty$) を提供し、これらの制約は範囲演算子を用いて以下のように実装されます:

下限演算子: $l\leq f\leq +\infty$
上限演算子: $-\infty \leq f\leq u$

範囲演算子は内部で補助変数を導入するため、真の無限値を明示的に表現することはできません。したがって、QUBO++は式$f$の有限の最大値と最小値を推定し、それぞれ$+\infty$と$-\infty$に代入します。

例えば、次の式を考えてみましょう

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

ここで $a$、$b$、$c$ は二値変数である。 $f$ の可能な最小値と最大値はそれぞれ 0 と 24 である。したがって、QUBO++ は対応する範囲制約を構築する際、 $-\infty$ および $+\infty$ の代わりに 0 と 24 を使用する。

注記 QUBO++では、不等式制約において意図的に下限と上限の両方の指定を要求します。これにより、MIPスタイルの解釈（例：$f\leq u$が$0\leq f\leq u$を意味する）とQUBOスタイルの解釈（例：$f\leq u$が$-\infty\leq f\leq u$を意味する）の間の曖昧さが回避され、さもないと微妙なモデリングエラーにつながる可能性があります。

下限・上限演算子用QUBO++プログラム

QUBO++では、無限大はで表されますqbpp::inf。

以下のプログラムは下限演算子を示します：

#include "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 = 14 <= 4 * a + 9 * b + 11 * c <= +qbpp::inf;
  f.simplify_as_binary();
  auto solver = qbpp::exhaustive_solver::ExhaustiveSolver(f);
  auto sols = solver.search_optimal_solutions();
  for (const auto& sol : sols) {
    std::cout << "a = " << a(sol) << ", b = " << b(sol) << ", c = " << c(sol)
              << ", f = " << f(sol) << ", *f = " << (*f)(sol)
              << ", sol = " << sol << std::endl;
  }
}

このプログラムではが正の無限大+qbpp::infを表し、自動的に 24 に置換されます。

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

a = 0, b = 1, c = 1, f = 0, *f = 20, sol = 0:{{a,0},{b,1},{c,1},{{0}[0],1},{{0}[1],0},{{0}[2],1}}
a = 0, b = 1, c = 1, f = 0, *f = 20, sol = 0:{{a,0},{b,1},{c,1},{{0}[0],1},{{0}[1],1},{{0}[2],0}}
a = 1, b = 0, c = 1, f = 0, *f = 15, sol = 0:{{a,1},{b,0},{c,1},{{0}[0],0},{{0}[1],0},{{0}[2],0}}
a = 1, b = 1, c = 1, f = 0, *f = 24, sol = 0:{{a,1},{b,1},{c,1},{{0}[0],1},{{0}[1],1},{{0}[2],1}}

次のプログラムは上限演算子を示します：

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

このプログラムでは、-qbpp::infが負の無限大を表し、自動的に 0 に置換されます。

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

a = 0, b = 0, c = 0, f = 0, *f = 0, sol = 0:{{a,0},{b,0},{c,0},{{0}[0],0},{{0}[1],0},{{0}[2],0}}
a = 0, b = 0, c = 1, f = 0, *f = 11, sol = 0:{{a,0},{b,0},{c,1},{{0}[0],0},{{0}[1],1},{{0}[2],1}}
a = 0, b = 1, c = 0, f = 0, *f = 9, sol = 0:{{a,0},{b,1},{c,0},{{0}[0],1},{{0}[1],0},{{0}[2],1}}
a = 1, b = 0, c = 0, f = 0, *f = 4, sol = 0:{{a,1},{b,0},{c,0},{{0}[0],0},{{0}[1],1},{{0}[2],0}}
a = 1, b = 1, c = 0, f = 0, *f = 13, sol = 0:{{a,1},{b,1},{c,0},{{0}[0],1},{{0}[1],1},{{0}[2],1}}

最終更新日: 2025.12.26