Replace functions

QUBO++ provides the following replace function, which can be used to fix variable values in an expression.

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

Replaces (fixes) variable values in the expression f according to the mapping specified by ml.

Using the replace function to fix variable values

We explain the qbpp::replace() function using the QUBO++ program for partitioning problem. This program finds a partition of the numbers in the following array w into two subsets $P$ and $Q$ ($=\overline{P}$) such that the difference between their sums is minimized:

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

We modify this partitioning problem so that 64 must belong to $P$ and 27 must belong to $Q$, ensuring that they are placed in distinct subsets.

To enforce this constraint, the values of x[0] and x[1] are fixed to 1 and 0, respectively, using the qbpp::replace() function.

The complete QUBO++ program is shown below:

#include <qbpp/qbpp.hpp>
#include <qbpp/exhaustive_solver.hpp>

int main() {
  auto w = qbpp::int_array({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 * ~x);
  auto f = qbpp::sqr(p - q);
  f.simplify_as_binary();

  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();

  auto full_sol = qbpp::Sol(f).set(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;
}

First, a qbpp::MapList object ml is defined, which specifies fixed values for the variables x[0] and x[1]. Given the original expression f for the partitioning problem and the qbpp::MapList object ml, the qbpp::replace() function is used to replace x[0] and x[1] in f with the constants 1 and 0, respectively. The resulting expression is stored in g.

The Exhaustive Solver is then applied to g to find an optimal solution, which is stored in sol. Note that the expression g no longer contains the variables x[0] and x[1], and consequently, sol also does not include assignments for these variables.

To construct a complete solution that includes all variables, we create a zero-initialized qbpp::Sol object for f and then set the binary values using set() with sol and ml.

From the output below, we can confirm that 64 is placed in $P$ and 27 is placed in $Q$, as intended:

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

Using the replace function to replace variables with expressions

The replace() function can also replace a variable with an expression, not only with a constant value.

Here, we present a more sophisticated way to ensure that 64 and 27 are placed in distinct subsets in the partitioning problem introduced above. The key idea is to replace the variable x[0] in the expression f with the negated literal ~x[1]. This enforces the constraint that x[0] and x[1] always take opposite values, guaranteeing that the corresponding elements (64 and 27) belong to different subsets.

The following C++ program implements this idea:

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

  auto full_sol = qbpp::Sol(f).set(sol, ml);

In this program, a qbpp::MapList object ml is defined so that the variable x[0] is replaced by the negated literal ~x[1].

The qbpp::replace() function applies this substitution to the original expression f, and the resulting expression is stored in g. As a result, g no longer contains the variable x[0]; instead, all occurrences of x[0] are replaced by ~x[1].

The Exhaustive Solver is then used to find an optimal solution for g, which is stored in sol. Since x[0] does not appear in g, the solution sol also does not include an assignment for x[0].

To construct a complete solution over the original variables in f, we start with a zero-initialized qbpp::Sol(f) and then populate it by calling set(sol, ml). Note that sol and ml must be passed to set() together, because the mapping in ml (e.g., x[0] = ~x[1]) may depend on variable values contained in sol.

This program produces the following output:

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],~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

We can confirm that:

• the solution sol does not include x[0],
• x[0] and x[1] take opposite values, and
• 64 and 27 are placed in distinct subsets, as intended.

Replace Functions for Integer Variables

Integer variables can be replaced with fixed integer values using the replace() functions.

Here, we demonstrate this feature using a simple multiplication expression. Let $p$, $q$, and $r$ be integer variables, and consider the following constraint:

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

This expression can be interpreted in several ways, leading to different types of problems:

• Multiplication: For fixed values of $p$ and $q$, find $r$ that satisfies the expression.
• Factorization: For a fixed value of $r$, find $p$ and $q$ that satisfy the expression.
• Division: For fixed values of $p$ and $r$, find $q$ that satisfies the expression.

Using the qbpp::replace() function, integer variables can be fixed to constant values. We demonstrate QUBO++ programs that solve these problems using qbpp::replace().

Multiplication

The folloing program fixes $p=5$ and $q=7$ and finds the product $r=35$:

#include <qbpp/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;
  f.simplify_as_binary();

  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);
  auto sol = solver.search({{"target_energy", 0}});

  auto full_sol = qbpp::Sol(f).set(sol).set(ml);
  std::cout << "p= " << full_sol(p) << ", q= " << full_sol(q)
            << ", r= " << full_sol(r) << std::endl;
}

In this program, a qbpp::MapList object ml is used to fix the values of the integer variables p and q in the original expression f. By applying qbpp::replace(f, ml), the variables p and q in f are replaced with the constants 5 and 7, respectively. The resulting expression is stored in g, which now contains only the variable r. The Easy Solver is then applied to g, and the resulting solution is stored in sol. To construct a complete solution that includes all variables, we create a zero-initialized qbpp::Sol object for f and then set the binary values using set() with sol and ml. Finally, the values of p, q, and r are printed.

This program produces the following output, confirming that the multiplication result is obtained correctly:

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

Factorization

For the factorization of $r=35$, the qbpp::MapList object ml in the QUBO++ program is modified as follows:

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

By fixing the value of $r$, the solver searches for integer values of $p$ and $q$ that satisfy the constraint

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

This program produces the following output:

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

Division

To compute the division $r/p$ with $r=35$ and $p=5$, the qbpp::MapList object ml in the QUBO++ program is modified as follows:

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

This program produces the following output:

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

This confirms that the division result $q=r/p=7$ is correctly obtained.

NOTE QUBO++ also provides a member function version of replace() for expressions. In other words:

• f.replace(ml) updates the expression f in place by applying the replacements specified in ml.
• qbpp::replace(f, ml) returns a new expression in which the replacements have been applied, without modifying the original expression f. Use f.replace(ml) when you want to permanently modify an existing expression, and use qbpp::replace(f, ml) when you want to keep the original expression unchanged.

NOTE: Negated literals and replace() The replace() function treats x and ~x as independent keys. Specifying {x, 0} in a MapList does not automatically replace ~x with 1. If the expression contains negated literals such as ~x, you should explicitly include both mappings:

qbpp::MapList ml({{x, 0}, {~x, 1}});

置換関数

QUBO++は、式中の変数の値を固定するために使用できる以下の置換関数を提供しています。

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

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

置換関数を使用した変数値の固定

QUBO++の分割問題プログラムを用いて qbpp::replace() 関数を説明します。 このプログラムは、以下の配列 w の数値を2つの部分集合 $P$ と $Q$ ($=\overline{P}$) に分割し、それらの和の差が最小となるものを求めます:

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

この分割問題を修正して、64は $P$ に、27は $Q$ に属するようにし、異なる部分集合に配置されることを保証します。

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

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

#include <qbpp/qbpp.hpp>
#include <qbpp/exhaustive_solver.hpp>

int main() {
  auto w = qbpp::int_array({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 * ~x);
  auto f = qbpp::sqr(p - q);
  f.simplify_as_binary();

  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();

  auto full_sol = qbpp::Sol(f).set(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;
}

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

次に、Exhaustive Solverを g に適用して最適解を求め、sol に格納します。 式 g にはもはや変数 x[0] と x[1] が含まれていないため、sol にもこれらの変数の割り当ては含まれません。

全ての変数を含む完全な解を構築するために、f に対するゼロ初期化された qbpp::Sol オブジェクトを作成し、set() で sol と ml を使用してバイナリ値を設定します。

以下の出力から、意図した通り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() 関数は、定数値だけでなく、変数を式に置換することもできます。

ここでは、上述の分割問題において64と27を異なる部分集合に配置するための、より洗練された方法を示します。 鍵となるアイデアは、式 f 中の変数 x[0] を否定リテラル ~x[1] に置換することです。 これにより x[0] と x[1] が常に反対の値をとるという制約が適用され、対応する要素（64と27）が異なる部分集合に属することが保証されます。

以下のC++プログラムはこのアイデアを実装しています:

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

  auto full_sol = qbpp::Sol(f).set(sol, ml);

このプログラムでは、変数 x[0] が否定リテラル ~x[1] に置換されるように qbpp::MapList オブジェクト ml を定義しています。

qbpp::replace() 関数がこの代入を元の式 f に適用し、結果の式は g に格納されます。 その結果、g にはもはや変数 x[0] が含まれず、x[0] の全ての出現が ~x[1] に置き換えられています。

次に、Exhaustive Solverを使用して g の最適解を求め、sol に格納します。 x[0] は g に現れないため、解 sol にも x[0] の割り当ては含まれません。

f の元の変数に対する完全な解を構築するために、ゼロ初期化された qbpp::Sol(f) から始め、set(sol, ml) を呼び出して値を設定します。 sol と ml は set() に一緒に渡す必要があることに注意してください。これは ml のマッピング（例: x[0] = ~x[1]）が sol に含まれる変数値に依存する場合があるためです。

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

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],~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() 関数を使用すると、整数変数を定数値に固定できます。 qbpp::replace() を使用してこれらの問題を解くQUBO++プログラムを示します。

乗算

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

#include <qbpp/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;
  f.simplify_as_binary();

  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);
  auto sol = solver.search({{"target_energy", 0}});

  auto full_sol = qbpp::Sol(f).set(sol).set(ml);
  std::cout << "p= " << full_sol(p) << ", q= " << full_sol(q)
            << ", r= " << full_sol(r) << std::endl;
}

このプログラムでは、qbpp::MapList オブジェクト ml を使用して、元の式 f 中の整数変数 p と q の値を固定しています。 qbpp::replace(f, ml) を適用することで、f 中の変数 p と q がそれぞれ定数5と7に置き換えられます。 結果の式は g に格納され、変数 r のみを含みます。 次にEasy Solverを g に適用し、結果の解を sol に格納します。 全ての変数を含む完全な解を構築するために、f に対するゼロ初期化された qbpp::Sol オブジェクトを作成し、set() で sol と ml を使用してバイナリ値を設定します。 最後に、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$ の因数分解では、QUBO++プログラム中の qbpp::MapList オブジェクト ml を以下のように変更します:

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

$r$ の値を固定することで、ソルバーは以下の制約を満たす $p$ と $q$ の整数値を探索します:

\[\begin{aligned} p\times q&=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$ が正しく得られたことが確認できます。

NOTE QUBO++は式に対する replace() のメンバ関数版も提供しています。 つまり:

• f.replace(ml) は ml で指定された置換を適用して式 f をその場で更新します。
• qbpp::replace(f, ml) は置換が適用された新しい式を返し、元の式 f は変更しません。 既存の式を恒久的に変更したい場合は f.replace(ml) を、元の式を変更せずに保持したい場合は qbpp::replace(f, ml) を使用してください。

NOTE: 否定リテラルと replace() replace() 関数は x と ~x を独立したキーとして扱います。 MapList に {x, 0} を指定しても、~x が自動的に 1 に置換されるわけではありません。 式に ~x のような否定リテラルが含まれている場合、両方のマッピングを明示的に指定してください:

qbpp::MapList ml({{x, 0}, {~x, 1}});