変数のベクトルを用いた分割問題の解決
分割問題
$w=(w_0, w_1, \ldots, w_{n-1})$ を $n$ 個の正の数とする。 分割問題とは、これらの数を $P$ と $Q$ ($Q=\overline{P}$) の二つの集合に分割し、二つの集合の要素の和を可能な限り近づけることである。 より具体的には、次の式を最小化する集合 $L \subseteq \lbrace 0,1,\ldots, n-1\rbrace$ を求める問題である：
\[\begin{aligned} P(L) &= \sum_{i\in L}w_i \\ Q(L) &= \sum_{i\not\in L}w_i \\ f(L) &= \left| P(L)-Q(L) \right| \end{aligned}\]この問題はQUBO問題として定式化できる。 集合$L$を表す二進変数$x=(x_0, x_1, \ldots, x_{n-1})$を定義する。 すなわち、$i\in L$は$x_i=1$である場合に限る。 $P(L)$、$Q(L)$、$f(L)$を$x$を用いて以下のように書き換えられる：
\[\begin{aligned} P(x) &= \sum_{i=0}^{n-1} w_ix_i \\ Q(x) &= \sum_{i=0}^{n-1} w_i (1-x_i) \\ f(x) &= \left( P(x)-Q(x) \right)^2 \end{aligned}\]明らかに、$f(x)=f(L)^2$ が成り立つ。 関数 $f(x)$ は $x$ の二次式であり、$f(x)$ を最小化する最適解は、元の分割問題に対する最適解も与える。
分割問題のためのQUBO++プログラム
以下のQUBO++プログラムは、固定された8個の数の集合に対する分割問題のQUBO形式を生成し、網羅的ソルバーを用いて解を求める。
#include "qbpp.hpp"
#include "qbpp_exhaustive_solver.hpp"
int main() {
std::vector<uint32_t> w = {64, 27, 47, 74, 12, 83, 63, 40};
auto x = qbpp::var("x", w.size());
auto p = qbpp::expr();
auto q = qbpp::expr();
for (size_t i = 0; i < w.size(); ++i) {
p += w[i] * x[i];
q += w[i] * (1 - x[i]);
}
auto f = qbpp::sqr(p - q);
std::cout << "f = " << f.simplify_as_binary() << std::endl;
auto solver = qbpp::exhaustive_solver::ExhaustiveSolver(f);
auto sol = solver.search();
std::cout << "Solution: " << sol << std::endl;
std::cout << "f(sol) = " << f(sol) << std::endl;
std::cout << "p(sol) = " << p(sol) << std::endl;
std::cout << "q(sol) = " << q(sol) << std::endl;
std::cout << "P :";
for (size_t i = 0; i < w.size(); ++i) {
if (x[i](sol) == 1) {
std::cout << " " << w[i];
}
}
std::cout << std::endl;
std::cout << "Q :";
for (size_t i = 0; i < w.size(); ++i) {
if (x[i](sol) == 0) {
std::cout << " " << w[i];
}
}
std::cout << std::endl;
}
このプログラムではw、 std::vector 8個の数字を持つオブジェクトとして定義される。
ベクトルx は w.size()=8 二値変数のベクトルが定義される。
二つの qbpp::Expr オブジェクトp とq が定義され、$P(x)$ および $Q(x)$ の式が
forループ内で構築されます。
オブジェクト qbpp::Expr オブジェクト は $f(x)f$ の式を格納します。
網羅的ソルバーオブジェクトsolver が f が作成され
解sol (オブジェクト) が得られる qbpp::Sol オブジェクト）が取得される。 search() メンバ関数を呼び出すことで得られる。
$f(x)$、$P(x)$、$Q(x)$ の値は、それぞれ、q(sol)p(sol)f(sol)、 、 を呼び出すことで評価される。
集合 $L$ および $\overline{L}$ 内の数値は、for ループを用いて表示される。
これらのループでは、x[i](sol)は x[i] を返す。 sol.
このプログラムは以下を出力する：
f = 168100 -88576*x[0] -41364*x[1] -68244*x[2] -99456*x[3] -19104*x[4] -108564*x[5] -87444*x[6] -59200*x[7] +13824*x[0]*x[1] +24064*x[0]*x[2] +37888*x[0]*x[3] +6144*x[0]*x[4] +42496*x[0]*x[5] +32256*x[0]*x[6] +20480*x[0]*x[7] +10152*x[1]*x[2] +15984*x[1]*x[3] +2592*x[1]*x[4] +17928*x[1]*x[5] +13608*x[1]*x[6] +8640*x[1]*x[7] +27824*x[2]*x[3] +4512*x[2]*x[4] +31208*x[2]*x[5] +23688*x[2]*x[6] +15040*x[2]*x[7] +7104*x[3]*x[4] +49136*x[3]*x[5] +37296*x[3]*x[6] +23680*x[3]*x[7] +7968*x[4]*x[5] +6048*x[4]*x[6] +3840*x[4]*x[7] +41832*x[5]*x[6] +26560*x[5]*x[7] +20160*x[6]*x[7]
Solution: 0:{{x[0],0},{x[1],0},{x[2],1},{x[3],0},{x[4],1},{x[5],1},{x[6],1},{x[7],0}}
f(sol) = 0
p(sol) = 205
q(sol) = 205
P : 47 12 83 63
Q : 64 27 74 40
注記 より詳細な
qbpp::Exprオブジェクトfおよびqbpp::Solオブジェクトsolに対して、両方のf(sol)とsol(f)はfを評価した結果の値を返します。solで評価された結果の値を返します。 同様に、qbpp::Varオブジェクトaの場合も、a(sol)とsol(a)の両方がaの値を返します。solの値を返します。 数学的な観点からは、関数を点で評価することに相当するため、形式f(sol)が自然です。 対照的に、オブジェクト指向プログラミングの観点では、sol(f)ソリューションオブジェクトが式を評価するため、形式 が自然です。 どちらの形式も、好みに応じて使用できます。
ベクトル演算を用いたQUBO++プログラム
QUBO++はコードを簡略化できる豊富なベクトル演算を備えています。
この目的qbpp::Vectorで、 std::vector クラスと同様の クラスを使用すべきですqbpp::Vector<uint32_t>。
以下のコードでは、w が クラスのオブジェクトとして定義されています。
また、x が クラスのオブジェクトqbpp::Vector<qbpp::Var>として定義されています。
オーバーロードされた演算子 * がオーバーロードされているため、 qbpp::Vector は2つのオブジェクトの要素ごとの積を返すため、
qbpp::Vector オブジェクトの要素ごとの積を返すためqbpp::sum(w * x)、 は qbpp::Exprオブジェクトを返します。
さらに、オーバーロードされた演算子 - はスカラーと qbpp::Vector オブジェクトに対するオーバーロードされた演算子は、
スカラーと qbpp::Vector オブジェクトを返します。その成分は、スカラーからベクトルのqbpp::sum(w * (1 - x))各要素を引いた値です。
したがって、 qbpp::Expr オブジェクトを返します。
qbpp::Vector<uint32_t> w = {64, 27, 47, 74, 12, 83, 63, 40};
auto x = qbpp::var("x", w.size());
auto p = qbpp::sum(w * x);
auto q = qbpp::sum(w * (1 - x));
auto f = qbpp::sqr(p - q);
これらのベクトル演算を利用することで、QUBO++プログラムを簡略化できる。 加えて、大規模ベクトルに対するベクトル演算はマルチスレッド化により並列化されるため、QUBOモデル生成プロセスを高速化できる。
注記 演算子
+,-, および*は、2つのqbpp::Vectorオブジェクト間、およびスカラーとqbpp::Vectorオブジェクトの両方でオーバーロードされています。 2つのqbpp::Vectorオブジェクトの場合、オーバーロードされた演算子は要素ごとの演算を実行します。 スカラーとqbpp::Vectorオブジェクトの場合、オーバーロードされた演算子はベクトルの各要素に対してスカラー演算を適用します。