置換関数

QUBO++ は、式内の変数値を修正するために使用できる以下の置換関数を提供します。

qbpp::replace(const qbpp::Expr& f, const qbpp::MapList& ml)

式内の変数値を置換（固定）します f 指定されたマッピングに従って ml.

置換関数による変数値の固定

分割問題用の QUBOqbpp::replace()++プログラムを用いて関数を説明します。このプログラムは、以下のベクトル内の数値を2つの部分集合$P$と$Q$（w$=\overline{L}$）に分割し、それらの和の差を最小化する分割を見つけます：

  std::vector<uint32_t> w = {64, 27, 47, 74, 12, 83, 63, 40};

この分割問題を修正し、64は$P$に、27は$Q$に属さねばならず、かつそれらが互いに異なる部分集合に配置されるようにする。

この制約を強制するため、 x[0] と x[1] をそれぞれ1と0に固定します。 qbpp::replace() 関数を用いて固定する。

完全なQUBO++プログラムを以下に示す：

#include "qbpp.hpp"
#include "qbpp_exhaustive_solver.hpp"

int main() {
  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);
  qbpp::MapList ml({{x[0], 1}, {x[1], 0}});
  auto g = qbpp::replace(f, ml);
  g.simplify_as_binary();
  auto solver = qbpp::exhaustive_solver::ExhaustiveSolver(g);
  auto sol = solver.search();

  qbpp::Sol full_sol(f);
  full_sol.set(sol);
  full_sol.set(ml);
  std::cout << "sol = " << sol << std::endl;
  std::cout << "ml = " << ml << std::endl;
  std::cout << "full_sol = " << full_sol << std::endl;
  std::cout << "f(full_sol) = " << f(full_sol) << std::endl;
  std::cout << "p(full_sol) = " << p(full_sol) << std::endl;
  std::cout << "q(full_sol) = " << q(full_sol) << std::endl;
  std::cout << "P :";
  for (size_t i = 0; i < w.size(); ++i) {
    if (x[i](full_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](full_sol) == 0) {
      std::cout << " " << w[i];
    }
  }
  std::cout << std::endl;
}

まず、変数 qbpp::MapList オブジェクトmlが定義され、変数 x[0] および x[1]の固定値を指定します。分割問題の元の式 f が与えられた場合、分割問題と qbpp::MapList オブジェクト mlが与えられるqbpp::replace()と、関数を用いて x[0] および x[1] を f をそれぞれ定数1と0に置換するために使用される。結果の式はに格納されるg。

その後、網羅的ソルバーが適用され g に適用され、最適解が求められ、 solに格納される。なお、式 g には変数 x[0] および x[1]を含まず、したがって sol これらの変数に対する代入も含まれていない。

すべての変数を含む完全な解決策を構築するには、元の式から qbpp::Sol オブジェクトfull_solを作成します fを作成します。初期状態では、 full_sol は全ゼロ解を表す。次に set() メンバー関数を用いて両方を組み込みます：

簡約化された問題から得られたsol解と
で指定された固定ml割り当てこれらを統合し、 full_sol.

以下の出力から、意図通り64が$P$に、27が$Q$に配置されていることを確認できる：

sol = 4:{{x[2],1},{x[3],0},{x[4],1},{x[5],1},{x[6],0},{x[7],0}}
ml = {{x[0],1},{x[1],0}}
full_sol = 4:{{x[0],1},{x[1],0},{x[2],1},{x[3],0},{x[4],1},{x[5],1},{x[6],0},{x[7],0}}
f(full_sol) = 4
p(full_sol) = 206
q(full_sol) = 204
P : 64 47 12 83
Q : 27 74 63 40

置換関数を使用して変数を式で置き換える

replace関数は replace() 関数は定数値だけでなく、変数を式で置換することも可能である。

ここで、前述の分割問題において64と27を互いに異なる部分集合に確実に配置する、より洗練された方法を提示する。核心となるアイデアは、式中の変数 x[0] を式 f を式 1 - x[1]で置き換えることです。これにより、 x[0] および x[1] が常に反対の値を取るという制約を強制し、対応する要素（64と27）が異なる部分集合に属することを保証する。

以下のC++プログラムはこの考え方を実装している：

  qbpp::MapList ml({{x[0], 1 - x[1]}});
  auto g = qbpp::replace(f, ml);
  g.simplify_as_binary();
  auto solver = qbpp::exhaustive_solver::ExhaustiveSolver(g);
  auto sol = solver.search();

  qbpp::Sol full_sol(f);
  full_sol.set(sol);
  full_sol.set({{x[0], sol(1 - x[1])}});

このプログラムでは、qbpp::MapList オブジェクト ml を定義し、変数 x[0] が式 1 - x[1].

が置換される。 qbpp::replace() 関数は元の式 fを適用し、結果の式を gに格納されます。結果として、 g には変数 x[0]を含まなくなり、代わりに x[0] は式 1 - x[1].

その後、網羅的ソルバーを用いて gに対する最適解を求め、その結果は solに格納される。 x[0] は gに現れないため、解 sol も x[0].

元の式に対する完全な解を構築するには fに対する完全な解を構築するには、 qbpp::Sol オブジェクト full_sol が作成される。まず、 sol がコピーされ full_solにコピーされる。次に、 x[0] が式 1 - x[1]を呼び出すことで明示的に設定される。 solを呼び出して評価される式

  full_sol.set({{x[0], sol(1 - x[1])}});

これにより、最終的な解決策において制約 x[0] = 1 - x[1] が最終的な解において一貫して適用されることを保証します。

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

sol = 4:{{x[1],0},{x[2],1},{x[3],0},{x[4],1},{x[5],1},{x[6],0},{x[7],0}}
ml = {{x[0],1 -x[1]}}
full_sol = 4:{{x[0],1},{x[1],0},{x[2],1},{x[3],0},{x[4],1},{x[5],1},{x[6],0},{x[7],0}}
f(full_sol) = 4
p(full_sol) = 206
q(full_sol) = 204
P : 64 47 12 83
Q : 27 74 63 40

次のことが確認できます:

解には sol x[0]を含まず、
x[0] かつ x[1] 反対の値を取り、
64 と 27 は意図通り異なる部分集合に配置されています。

整数変数の関数置換

整数変数は、 replace() 関数を用いて固定整数値で置換できます。

ここでは、単純な乗算式を用いてこの機能を示す。 $p$、$q$、$r$ を整数変数とし、次の制約を考える：

\[\begin{aligned} p\times q - r &=0 \end{aligned}\]

この式は複数の解釈が可能であり、異なる種類の問題につながります：

乗算: $p$ と $q$ を固定値とした場合、式を満たす $r$ を求める。
因数分解：$r$の固定値に対して、式を満たす$p$と$q$を求める。
除法：$p$ と $r$ の値が固定されている場合、式を満たす $q$ を求める。

関数qbpp::replace()を使用することで、整数変数を定数値に固定できる。これらの問題を解くQUBO++プログラムを以下に示す qbpp::replace().

乗算

以下のプログラムは $p=5$ と $q=7$ を固定し、積 $r=35$ を求める：

#include "qbpp.hpp"
#include "qbpp_easy_solver.hpp"

int main() {
  auto p = 2 <= qbpp::var_int("p") <= 8;
  auto q = 2 <= qbpp::var_int("q") <= 8;
  auto r = 2 <= qbpp::var_int("r") <= 40;
  auto f = p * q - r == 0;
  qbpp::MapList ml({{p, 5}, {q, 7}});
  auto g = qbpp::replace(f, ml);
  g.simplify_as_binary();
  std::cout << "g = " << g << std::endl;
  auto solver = qbpp::easy_solver::EasySolver(g);
  solver.target_energy(0);
  auto sol = solver.search();
  qbpp::Sol full_sol(f);
  full_sol.set(sol);
  full_sol.set(ml);
  std::cout << "p= " << full_sol(p) << ", q= " << full_sol(q)
            << ", r= " << full_sol(r) << std::endl;
}

このプログラムでは、 qbpp::MapList オブジェクト ml を使用して整数変数の値を固定します p と q の値を固定します fの値を固定するために使用されます。を適用することで qbpp::replace(f, ml)を適用することで、変数 p と q は f はそれぞれ定数5と7に置換される。結果の式は gに格納され、この時点では変数 rのみを含むようになる。その後、イージーソルバーが gに適用され、得られた解は solに格納される。元の式 fの完全な解を構築するには、 qbpp::Sol オブジェクト full_sol が作成される。 solから得られた代入値と、 ml によって指定された固定値を組み合わせ、 full_solに格納される。最後に、$p$、$q$、$r$ の値が出力される。

このプログラムは以下の出力を生成し、乗算結果が正しく得られることを確認する:

g = 1089 -65*r[0] -128*r[1] -248*r[2] -464*r[3] -800*r[4] -413*r[5] +4*r[0]*r[1] +8*r[0]*r[2] +16*r[0]*r[3] +32*r[0]*r[4] +14*r[0]*r[5] +16*r[1]*r[2] +32*r[1]*r[3] +64*r[1]*r[4] +28*r[1]*r[5] +64*r[2]*r[3] +128*r[2]*r[4] +56*r[2]*r[5] +256*r[3]*r[4] +112*r[3]*r[5] +224*r[4]*r[5]
p= 5, q= 7, r= 35

因数分解

$r=35$ の因数分解では、 qbpp::MapList オブジェクト ml は次のように変更される：

  qbpp::MapList ml({{r, 35}});

$r$の値を固定することで、ソルバーは制約条件

\[\begin{aligned} p\times &=35 \end{aligned}\]

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

g = 961 -120*p[0] -232*p[1] -336*p[2] -120*q[0] -232*q[1] -336*q[2] +16*p[0]*p[1] +24*p[0]*p[2] -45*p[0]*q[0] -80*p[0]*q[1] -105*p[0]*q[2] +48*p[1]*p[2] -80*p[1]*q[0] -136*p[1]*q[1] -168*p[1]*q[2] -105*p[2]*q[0] -168*p[2]*q[1] -189*p[2]*q[2] +16*q[0]*q[1] +24*q[0]*q[2] +48*q[1]*q[2] +20*p[0]*p[1]*q[0] +48*p[0]*p[1]*q[1] +84*p[0]*p[1]*q[2] +30*p[0]*p[2]*q[0] +72*p[0]*p[2]*q[1] +126*p[0]*p[2]*q[2] +20*p[0]*q[0]*q[1] +30*p[0]*q[0]*q[2] +60*p[0]*q[1]*q[2] +60*p[1]*p[2]*q[0] +144*p[1]*p[2]*q[1] +252*p[1]*p[2]*q[2] +48*p[1]*q[0]*q[1] +72*p[1]*q[0]*q[2] +144*p[1]*q[1]*q[2] +84*p[2]*q[0]*q[1] +126*p[2]*q[0]*q[2] +252*p[2]*q[1]*q[2] +16*p[0]*p[1]*q[0]*q[1] +24*p[0]*p[1]*q[0]*q[2] +48*p[0]*p[1]*q[1]*q[2] +24*p[0]*p[2]*q[0]*q[1] +36*p[0]*p[2]*q[0]*q[2] +72*p[0]*p[2]*q[1]*q[2] +48*p[1]*p[2]*q[0]*q[1] +72*p[1]*p[2]*q[0]*q[2] +144*p[1]*p[2]*q[1]*q[2]
p= 5, q= 7, r= 35

除算

$r=35$ および $p=5$ における除算 $r/p$ を計算するため、QUBO++ プログラム内の qbpp::MapList オブジェクト ml は以下のように変更されます:

  qbpp::MapList ml({{p, 5}, {r, 35}});

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

g = 625 -225*q[0] -400*q[1] -525*q[2] +100*q[0]*q[1] +150*q[0]*q[2] +300*q[1]*q[2]
p= 5, q= 7, r= 35

これにより、除算結果 $q=r/p=7$ が正しく得られることが確認されます。

注記 QUBO++ は式に対して replace() をメンバー関数として提供しています。つまり:

f.replace(ml) は式を f を、指定された置換を適用してその場で更新します。 ml.

qbpp::replace(f, ml) 元の式を変更せずに置換を適用した新しい式を返します f。既存の式を恒久的に変更したい場合は f.replace(ml) 既存の式を恒久的に変更したい場合に使用し、 qbpp::replace(f, ml) 元の式を変更せずに保持したい場合に使用します。

最終更新日: 2025.12.26