比較演算子¶
Hi-QUBO は、制約条件を作成するために 2 種類の演算子をサポートしています。
pyQUBO は、制約条件を作成するために 2 種類の演算子をサポートしています。
等号演算子(Equality operator):
\(f=n\) の形式で、\(f\) は式、\(n\) は整数です。範囲演算子(Range operator):
\(l \leq f \leq u\) の形式で、\(f\) は式、\(l\) と \(u\) \((l \leq u)\) は整数です。
これらの演算子は、対応する制約が満たされる場合にのみ最小値 0 を取る式を返します。
等号演算子¶
等号演算子 \(f=n\) は次の式を生成します:
この式は、等式 \(f=n\) が満たされる場合にのみ最小値 0 を取ります。
次のプログラムは、Exhaustive Solver を使って \(a+2b+3c=3\) を満たすすべての解を探索します。
#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", 1}});
for (const auto& sol : sols) {
std::cout << "a = " << a(sol) << ", b = " << b(sol) << ", c = " << c(sol)
<< ", f = " << f(sol) << ", 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() の値が次のように出力されます:
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 つの Expr オブジェクトを保持しています:
f: \((a+2b+3c-3)^2\). これは等式 \(a+2b+3c=3\) が成立する場合に最小値 0 を取ります。
f.bofy: \(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 は等式演算子を次の形式でのみサポートしています:
pyQBPP は等式演算子を次の形式でのみサポートしています:
expression == integer.
サポートされていない形式は以下の通りです:
integer == expression,expression1 == expression2.
expression1 == expression2 の代わりに、制約を次のように書き換えることができます:
expression1 - expression2 == 0.
これは完全にサポートされています。
範囲演算子¶
\(l \leq f \leq u~(l \leq u)\) の形の範囲演算子は、制約が満たされる場合に限り、最小値 0 をとる式を生成します。
ここでは、\(l\) と \(u\) の値に応じて、以下のケースを考えます。
Case1: \(u=l\),
Case2: \(u=l+1\),
Case3: \(u=l+2\),
Case4: \(u \geq l+3\).
Case1: \(u=l\)¶
もし \(u=l\) であれば、範囲制約は等式制約 \(f=l\) に帰着します。この制約は、等号演算子を用いて直接実装できます。
Case2: \(u=l+1\)¶
もし \(u=l+1\) の場合、次の式が生成されます。
\(l<x<u\) となる整数 \(x\) がないため、この式は \(f=l\) または \(f=u\) のときに限り、最小値 0 をとります。
Case3: \(u=l+2\)¶
補助的な二値変数 \(a \in \{0, 1\}\) を導入し、次の式を用います。
この式は、\(f=l,~l+1,~l+2\) のそれぞれの場合について、次のように評価されます。
いずれの場合においても、\(a\) を適切に選択することで最小値 0 をとることが可能です。したがって、この式は \(l \leq f \leq u\) が満たされる場合に、最小値 0 をとります。
\(g=f-l-a\) とします。このとき、次式が得られます。
これは、\(g \leq -1\) または \(g \geq 2\) の場合には常に正となります。したがって、この式は \(l \leq f \leq u\) が満たされる場合に限り、最小値 0 をとります。
Case4: \(u \geq l+3\)¶
範囲 \([l, u-1]\) の整数値をとる補助整数変数 \(a\) を導入します。このような整数変数は、「整数変数と連立方程式の解法」で説明したとおり、複数の二値変数を用いて定義できます。
この場合の式は次のとおりです :
Case3と同様に、\(f\) が \([l,u]\) に含まれない場合、この式は常に正となることを示すことができます。 \(f\) が範囲 \([l,u]\) の整数値をとると仮定します。ここで以下のように \(f\) の値に応じて \(a\) を選ぶと、
とできます。
したがって、任意の \(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,\cdots,x_{n-1}\) を用いて次のように表されます:
この式は、\(l\) から \(l+2^{n-1}+d-1\) までのすべての整数を表現できます。したがって、\(n\) および \(d\) は次の条件を満たすように選ぶことができます:
Case 4 では、QUBO++ は代わりに \(n-1\) 個のバイナリ変数 \(x_1,\cdots,x_{n-1}\) を用いた次の線形表現を使用します:
Case 4 では、PyQBPP は代わりに \(n-1\) 個のバイナリ変数 \(x_1,\cdots,x_{n-1}\) を用いた次の線形表現を使用します:
この式は、\(l\) から \(l+2^{n-1}+d-2\) までの整数を表します。したがって、\(n\) および \(d\) を次の条件を満たすように選択します:
このような整数変数 \(a\) を unit-gap 整数変数 と呼びます。
\([l,u]\) の中には \(a\) が取り得ない値もありますが、表現できない \(k \in [l,u]\) があった場合でも、\(k-1\) は表現可能です。
これは \(a-l-dx_{n-1}\) は 2 進数表記で \(x_{n-2}x_{n-1} \cdots x_1 0\) なので、\(k-l-dx_{n-1}\)が表現できない場合は下 1 桁が 1 になっている場合ですから、\((k-1)-l-dx_{n-1}\) は表現可能となることからわかります。
したがって、\(a\) または \(a+1\) のいずれかが範囲 \([l,u]\) 内の任意の値を取ることができ、これは範囲制約を課すためには十分です。
4つのケースに対する Hi-QUBO プログラム
次のプログラムは、4つのケースが Hi-QUBO でどのように実装されるかを示しています:
#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;
}
4つのケースに対する PyQBPP プログラム
次のプログラムは、4つのケースが PyQBPP でどのように実装されるかを示しています:
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*{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]
これらの出力は、次の式に対応しています:
範囲演算子を使用した Hi-QUBO プログラム
以下のプログラムは、Hi-QUBO における範囲演算子の使用方法を示しています。
#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", 1}});
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;
}
}
範囲演算子を使用した PyQBPP プログラム
以下のプログラムは、PyQBPPにおける範囲演算子の使用方法を示しています。
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\) に対して、このプログラムは次の制約を満たす解を探索します :
このプログラムは次の出力を生成します。
a = 0, b = 1, c = 0, f = 0, 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, 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, body = 13, sol = 0:{{a,1},{b,1},{c,0},{{0}[0],1},{{0}[1],1},{{0}[2],1}}
下限および上限の制約演算子¶
Hi-QUBO は、以下の 片側境界演算子 を直接サポートしていません。
pyQBPP は、以下の 片側境界演算子 を直接サポートしていません。
下限制約演算子: \(l \leq f\).
上限制約演算子: \(f \leq u\).
その代わりに、Hi-QUBO は 無限大(\(\infty\)) の記号表現(qbpp::inf)を提供しており、これらの制約は 範囲演算子 を用いて次のように実装されます。
下限制約演算子:
l <= f <= +qbpp::inf→ \(l \leq f \leq +\infty\).上限制約演算子:
-qbpp::inf <= f <= u→ \(-\infty \leq f \leq u\).
代わりに、PyQBPP は between の境界値を None とすることでこれらをサポートします:
下限制約演算子:
between(l, None)→ \(l \leq f \leq +\infty\).上限制約演算子:
between(None, u)→ \(-\infty \leq f \leq u\).
範囲演算子は内部的に補助変数(auxiliary variables)を導入するため、真の無限値を明示的に表現することはできません。
そのため、Hi-QUBO は式 \(f\) の 有限の最大値および最小値 を推定し、それぞれ \(+\infty\) および \(-\infty\) の代替値として使用します。
そのため、pyQBPP は式 \(f\) の 有限の最大値および最小値 を推定し、それぞれ \(+\infty\) および \(-\infty\) の代替値として使用します。
例えば、次の式を考えます :
ここで、\(a,b\) そして \(c\) は バイナリ変数 です。
この式 \(f\) が取り得る 最小値と最大値 はそれぞれ 0 と 24 です。
したがって、Hi-QBPP は対応する範囲制約を構築する際に、0 を \(-\infty\) の代替値、24 を \(+\infty\) の代替値として使用します。
したがって、pyQBPP は対応する範囲制約を構築する際に、0 を \(-\infty\) の代替値、24 を \(+\infty\) の代替値として使用します。
NOTE
Hi-QUBO では、不等式制約において 下限と上限の両方を明示的に指定すること を意図的に要求しています。これは次のような 解釈の曖昧さ を避けるためです。
pyQBPP では、不等式制約において 下限と上限の両方を明示的に指定すること を意図的に要求しています。これは次のような 解釈の曖昧さ を避けるためです。
MIP(Mixed Integer Programming)スタイルの解釈
例: \(f \leq u\) が \(0 \leq f \leq u\) を意味する。
QUBO スタイルの解釈
例:\(f \leq u\) が \(-\infty \leq f \leq u\) を意味する。
このような曖昧さは、微妙なモデリングエラーを引き起こす可能性があります。
下限および上限制約演算子の Hi-QUBO プログラム
Hi-QUBO では、\(+\infty\) は qbpp::inf によって表現されます。
下限および上限制約演算子の pyQBPP プログラム
pyQBPP では、\(+\infty\) は between の対応する側の None で表現されます。
以下のプログラムは 下限制約演算子(lower-bound operator) を示す例です。
#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 = 14 <= 4 * a + 9 * b + 11 * c <= +qbpp::inf;
f.simplify_as_binary();
auto solver = qbpp::ExhaustiveSolver(f);
auto sols = solver.search({{"best_energy_sols", 1}});
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;
}
}
このプログラムでは、+qbpp::inf は正の無限大の値を表しており、自動的に 24 に置き換えられます。
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 = 0, b = 1, c = 1, f = 0, body = 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, body = 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, body = 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, body = 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, body = 24, sol = 0:{{a,1},{b,1},{c,1},{{0}[0],1},{{0}[1],1},{{0}[2],1}}
次のプログラムは、上限制約演算子 を示しています。
#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 = -qbpp::inf <= 4 * a + 9 * b + 11 * c <= 14;
f.simplify_as_binary();
auto solver = qbpp::ExhaustiveSolver(f);
auto sols = solver.search({{"best_energy_sols", 1}});
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;
}
}
このプログラムでは、-qbpp::inf は負の無限大の値を表しており、自動的に 0 に置き換えられます。
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 = 0:{{a,0},{b,0},{c,0},{{0}[0],0},{{0}[1],0},{{0}[2],0}}
a = 0, b = 0, c = 1, f = 0, body = 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, body = 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, body = 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, body = 13, sol = 0:{{a,1},{b,1},{c,0},{{0}[0],1},{{0}[1],1},{{0}[2],1}}
演算子による省略構文
利便性のため、PyQBPPは式と整数の間の比較演算子 ==, <=, >= も受け付けます。 これらは qbpp.constrain() と同等の制約式を生成します:
演算子による形式 |
等価な |
生成される penalty |
|---|---|---|
|
|
\((f - n)^2\) |
|
|
\(\min(f) \leq f \leq n\) のとき 0 |
|
|
\(n \leq f \leq \max(f)\) のとき 0 |
ここで \(\min(f)\) と \(\max(f)\) は \(f\) の係数から導かれる構造的な境界であり、上記の 下界・上界制約で説明したルールに従います。反転形式 \(n <= f\), \(n >= f\) も Python の標準的な反射規則により動作します。
例えば、上の上界制約のプログラムは次のように書き換えられます:
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=範囲を 明示的に指定してください。var1 == var2のような変数の同一性比較(辞書のキーとして使うために bool を返すもの)は影響を受けません。演算子オーバーロードはExprおよび式の配列に対してのみ 定義されているためです。
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\) を連鎖記法で書いたものです:
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 にしてください。