式のクラス

QUBO++ の最も重要な機能は、組合せ最適化問題を解くための式を作成できることです。この目的のために、以下の 3 つのクラスが使用されます。

クラス	内容	詳細
qbpp::Var	変数	32 ビットの ID と表示用の文字列
qbpp::Term	積項	0 個以上の変数と整数係数
qbpp::Expr	式	0 個以上の項と整数定数項

qbpp::Expr オブジェクトは生成方法によって以下のいずれかを格納します:

格納する内容	生成方法	追加のメタデータ
式	x + 2*y, qbpp::expr(...) など	なし
整数変数	0 <= qbpp::var_int("x") <= 10 など	範囲 [min, max]、binary 変数列、係数
制約式	e == 5, 0 <= e <= 10 など	penalty（Expr 自身） + body（元の式）

いずれの形も同一の qbpp::Expr 型なので、どの内容を格納していても同じ算術・関数が同様に使えます。

qbpp::Var クラス

このクラスのインスタンスは、変数を記号的に表します。多くの場合、二値変数を表すために使用されます。しかし、このクラスは特定の変数属性に関連付けられておらず、そのインスタンスは任意の型の変数を記号的に表すために使用できます。

各 qbpp::Var インスタンスは単純に次の要素から構成されます:

• 一意の 32 ビット ID,

• 表示用の文字列

例えば、次のプログラムは qbpp::Var オブジェクト x を作成し、自動生成された ID が割り当てられ、表示には文字列 "x" が使用されます:

expression-class-program1.cpp

#include <qbpp/qbpp.hpp>

int main() {
  auto x = qbpp::var("x");
  std::cout << x << std::endl;
}

これは単純に x を出力します。変数のシンボルと同じ文字列を使用することが推奨されますが、異なる表示文字列を使用することも可能です:

expression-class-program2.cpp

#include <qbpp/qbpp.hpp>

int main() {
  auto x = qbpp::var("symbol_x");
  std::cout << x << std::endl;
}

これは symbol_x を出力します。

qbpp::Term クラス

このクラスのインスタンスは、次の要素から構成される**積の項（product term）**を表します。

• 整数係数

• 0 個以上の qbpp::Var オブジェクト

例えば、次のプログラムは整数係数 2 と変数 x および y を持つ qbpp::Term オブジェクト t を作成します。

expression-class-program3.cpp

#include <qbpp/qbpp.hpp>

int main() {
  auto x = qbpp::var("x");
  auto y = qbpp::var("y");
  auto t = 2 * x * y;
  std::cout << t << std::endl;
}

このプログラムは次のように出力します。

2*x*y

qbpp::Expr クラス

このクラスのインスタンスは、生成方法に応じて以下の 3 つの形を表現できます。

• 式 — 整数定数項と 0 個以上の qbpp::Term の和

• 整数変数 — 指定された整数範囲の値をとり、内部的にバイナリ変数列で表現される

• 制約式 — 比較演算子や範囲演算子で生成され、penalty と body の 2 つを保持する いずれも同一の qbpp::Expr 型であり、どの形を保持していても算術演算や関数を共通に使えます。

式

このクラスのインスタンスは、次の要素から構成される 式（expression） を表します。

• 整数の定数項

• 0個以上の qbpp::Term オブジェクト

例えば、次のプログラムは、定数項 3 と、項 2*x*y および 3*x を持つ qbpp::Expr オブジェクト f を作成します。

expression-class-program4.cpp

#include <qbpp/qbpp.hpp>

int main() {
  auto x = qbpp::var("x");
  auto y = qbpp::var("y");
  auto f = 3 + 2 * x * y + 3 * x;
  std::cout << f << std::endl;
}

このプログラムは次のように出力します。

3 +2*x*y +3*x

式は、+、-、* などの基本演算子や、括弧 ( と ) を使って記述できます。 式は自動的に展開され、qbpp::Expr オブジェクトとして保存されます。
例えば、次のプログラムは、展開された式を保持する qbpp::Expr オブジェクト f を作成します。

expression-class-program5.cpp

#include <qbpp/qbpp.hpp>

int main() {
  auto x = qbpp::var("x");
  auto y = qbpp::var("y");
  auto f = (x + y - 2) * (x - 2 * y + 3);
  std::cout << f << std::endl;
}

このプログラムは次のように出力します。

-6 +x*x +y*x -2*x*y -2*y*y +3*x +3*y -2*x +4*y

これらの数学演算は式を展開するだけであることに注意してください。
式を簡約（simplify）するには、以下のように simplify 関数を明示的に呼び出す必要があります。

expression-class-program6.cpp

#include <qbpp/qbpp.hpp>

int main() {
  auto x = qbpp::var("x");
  auto y = qbpp::var("y");
  auto f = (x + y - 2) * (x - 2 * y + 3);
  f.simplify();
  std::cout << f << std::endl;
}

このプログラムは次のように出力します。

-6 +x +7*y +x*x -x*y -2*y*y

利用可能な simplify 関数や演算子の詳細については、基本演算子と関数 を参照してください。

整数変数

qbpp::Expr は整数変数も表現でき、指定された整数範囲の値をとります。内部的には複数のバイナリ qbpp::Var でエンコードされています。 整数変数は範囲チェーン構文で作成します:

expression-class-program7.cpp

#include <qbpp/qbpp.hpp>

int main() {
  auto x = 0 <= qbpp::var_int("x") <= 10;   // [0, 10] の範囲の整数変数
  std::cout << x << std::endl;
}

基礎となる線形式（2のべき乗で重み付けされたバイナリ変数とオフセット）が出力されます:

x[0] +2*x[1] +4*x[2] +3*x[3]

整数変数はそのまま qbpp::Expr なので、式が期待される場所でそのまま使用できます:

auto y = 0 <= qbpp::var_int("y") <= 10;
auto f = qbpp::sqr(x + y - 7);            // そのまま算術に使える

埋め込みの式に加えて、整数変数は min_val()、max_val()、および基礎となるバイナリ Var のメタデータを保持します。詳細と使用例は 整数変数 を参照してください。

制約式

qbpp::Expr は、式に比較演算子や範囲演算子を適用した結果として得られる制約式も表現できます。制約式は 2 つの部分を保持します:

• penalty: 制約が満たされるとき 0 となり、そうでないとき正の値をとる Expr

• body: 元の式（ee.body() で取得、解における実際の値を確認する際に便利） 典型的な構築方法:

auto x = 0 <= qbpp::var_int("x") <= 10;
auto c1 = (x == 3);                    // penalty = sqr(x - 3), body = x
auto c2 = (2 <= x <= 5);               // penalty = 0 (2 <= x <= 5 のとき), body = x

制約式はそのまま算術式として使え、算術文脈ではその penalty 部分として振る舞います:

auto f = c1 + c2 + qbpp::sqr(x - 4);   // 制約式と通常の式を自由に組み合わせられる
f.simplify_as_binary();

評価前の body にアクセスするには ee.body() を使います（例えば ee.body(sol) で解における body の値を取得）。詳細と対応する比較構文の一覧は 比較演算子 を参照してください。

式（Expression）に関する重要な注意点

qbpp::Term クラスは qbpp::Expr よりも単純なデータ構造を持つため、必要なメモリ量が少なく、演算のオーバーヘッドも小さくなります。
しかし、qbpp::Term オブジェクトは完全な式（expression）を保持することはできません。

例えば、次の Hi-QUBO プログラムでは、t が qbpp::Term オブジェクトであるため、コンパイルエラーになります。

expression-class-program8.cpp

#include <qbpp/qbpp.hpp>

int main() {
  auto x = qbpp::var("x");
  auto y = qbpp::var("y");
  auto t = 2 * x * y;
  t += 3 * x;
  std::cout << t << std::endl;
}

式を保存・操作するには、次のように qbpp::toExpr() 関数を使って 明示的に qbpp::Expr オブジェクトを作成する必要があります :

expression-class-program9.cpp

#include <qbpp/qbpp.hpp>

int main() {
  auto x = qbpp::var("x");
  auto y = qbpp::var("y");
  auto t = qbpp::toExpr(2 * x * y);
  t += 3 * x;
  std::cout << t << std::endl;
}

このプログラムは qbpp::Expr オブジェクト t を作成し、次のように出力します :

2*x*y +3*x

オブジェクトが式を保持する目的で使われる場合は、整数・変数・項（term）から構築する際に qbpp::toExpr() を使用することが推奨されます。

  auto x = qbpp::var("x");
  auto f = qbpp::toExpr(0);
  auto g = qbpp::toExpr(x);
  auto h = qbpp::toExpr(3 * x);
  std::cout << "f = " << f << std::endl;
  std::cout << "g = " << g << std::endl;
  std::cout << "h = " << h << std::endl;

このプログラムでは、f、g、h はすべて qbpp::Expr オブジェクト として作成されます。
もし qbpp::toExpr() を使用しない場合、それぞれ次の型になります。

• f → int

• g → qbpp::Var

• h → qbpp::Term

例えば、次のプログラムは qbpp::Expr オブジェクト f を使って、式を段階的に構築しています。

expression-class-program10.cpp

#include <qbpp/qbpp.hpp>

int main() {
  auto x = qbpp::var("x", 4);
  auto f = qbpp::toExpr(-1);
  for (size_t i = 0; i < x.size(); ++i) {
    f += x[i];
  }
  std::cout << f << std::endl;
}

このプログラムは次のように出力します。

-1 +x[0] +x[1] +x[2] +x[3]

しかし qbpp::toExpr() を使用しない場合、f は int 型の変数となり、+= 演算子を適用した時点で コンパイルエラーが発生します。

PyQBPP の最も重要な機能は、組合せ最適化問題を解くための式を作成できることです。この目的のために、以下の 3 つのクラスが使用されます。

クラス	内容	詳細
pyqbpp.Var	変数	32 ビットの ID と表示用の文字列
pyqbpp.Term	積項	0 個以上の変数と整数係数
pyqbpp.Expr	式	0 個以上の項と整数定数項

pyqbpp.Expr オブジェクトは生成方法によって以下のいずれかを格納します:

格納する内容	生成方法	追加のメタデータ
式	x + 2*y, qbpp.expr(...) など	なし
整数変数	qbpp.var(..., between=(l, u)) など	範囲 [min, max]、binary 変数列、係数
制約式	qbpp.constrain(e, equal=5), qbpp.constrain(e, between=(0, 10)) など	penalty（Expr 自身） + body（元の式）

いずれの形も同一の pyqbpp.Expr 型なので、どの内容を格納していても同じ算術・関数が同様に使えます。 PyQBPPではこれらのクラスの違いを意識する必要はありません。 Pythonの動的型付けが必要に応じて自動的に型変換を行います。 例えば、2 * x * y は内部的に Term を生成しますが、+= 等の演算子を使えば自動的に Expr に変換されます。ただし、内部的にどの形が使われているかを理解しておくと、エラーメッセージの解釈や高速化のヒントになります。

pyqbpp.Var クラス

このクラスのインスタンスは変数をシンボリックに表現します。多くの場合、2値変数を表現するために使用されます。ただし、このクラスは特定の変数属性に関連付けられておらず、そのインスタンスは任意の型の変数をシンボリックに表現するために使用できます。

各 Var インスタンスは単純に以下で構成されます。

• 一意の32ビットID

• 表示用の文字列

例えば、以下のプログラムは変数 x を作成します。自動生成されたIDが割り当てられ、表示には文字列 "x" が使用されます。

expression-class-program1.py

import pyqbpp as qbpp

x = qbpp.var("x")
print(x)

これは単に x と出力します。変数シンボルと同じ文字列を使用することが推奨されますが、異なる表示文字列を使用することもできます。

expression-class-program2.py

import pyqbpp as qbpp

x = qbpp.var("symbol_x")
print(x)

これは symbol_x と出力します。

pyqbpp.Term クラス

このクラスのインスタンスは以下を含む積の項を表現します。

• 整数係数

• 0個以上の Var オブジェクト

例えば、以下のプログラムは整数係数 2 と変数 x、y を持つ積の項 t を作成します。

expression-class-program3.py

import pyqbpp as qbpp

x = qbpp.var("x")
y = qbpp.var("y")
t = 2 * x * y
print(t)

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

2*x*y

pyqbpp.Expr クラス

このクラスのインスタンスは、生成方法に応じて以下の 3 つの形を表現できます。

• 式 — 整数定数項と 0 個以上の Term オブジェクトの和

• 整数変数 — 指定された整数範囲の値をとり、内部的にバイナリ変数列で表現される

• 制約式 — 比較演算子や範囲演算子（通常は qbpp.constrain()）で生成され、penalty と body の 2 つを保持する

いずれも同一の pyqbpp.Expr 型であり、どの形を保持していても算術演算や関数を共通に使えます。

式

最も基本的な形では、Expr のインスタンスは以下を含む式を表現します。

• 整数定数項

• 0個以上の Term オブジェクト

例えば、以下のプログラムは定数項 3 と項 2*x*y および 3*x を持つ式 f を作成します。

expression-class-program4.py

import pyqbpp as qbpp

x = qbpp.var("x")
y = qbpp.var("y")
f = 3 + 2 * x * y + 3 * x
print(f)

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

3 +2*x*y +3*x

式は +, -, * などの基本演算子と、括弧 ( および ) を使って記述できます。

式は自動的に展開され、Expr オブジェクトとして格納されます。例えば、以下のプログラムは展開された形を格納する式 f を作成します。

expression-class-program5.py

import pyqbpp as qbpp

x = qbpp.var("x")
y = qbpp.var("y")
f = (x + y - 2) * (x - 2 * y + 3)
print(f)

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

-6 +x*x +y*x -2*x*y -2*y*y +3*x +3*y -2*x +4*y

これらの数学演算は式を展開するだけであることに注意してください。式を簡約化するには、以下のように simplify() 関数を明示的に呼び出す必要があります。

expression-class-program6.py

import pyqbpp as qbpp

x = qbpp.var("x")
y = qbpp.var("y")
f = (x + y - 2) * (x - 2 * y + 3)
f.simplify()
print(f)

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

-6 +x +7*y +x*x -x*y -2*y*y

利用可能な簡約化関数と演算子の詳細については、基本演算子と関数を参照してください。

整数変数

pyqbpp.Expr は整数変数も表現でき、指定された整数範囲の値をとります。内部的には複数のバイナリ変数でエンコードされています。整数変数は qbpp.var() に between= 引数を渡して作成します:

expression-class-program7.py

import pyqbpp as qbpp

x = qbpp.var("x", between=(0, 10))   # [0, 10] の範囲の整数変数
print(x)

基礎となる線形式（2のべき乗で重み付けされたバイナリ変数とオフセット）が出力されます:

x[0] +2*x[1] +4*x[2] +3*x[3]

整数変数はそのまま pyqbpp.Expr なので、式が期待される場所でそのまま使用できます:

y = qbpp.var_int("y", between=(0, 10))
f = qbpp.sqr(x + y - 7)  # そのまま算術に使える

埋め込みの式に加えて、整数変数は min_val、max_val、および基礎となるバイナリ変数のメタデータを保持します。詳細と使用例は 整数変数 を参照してください。

制約式

pyqbpp.Expr は、式に比較制約や範囲演算子を適用した結果として得られる制約式も表現できます。制約式は 2 つの部分を保持します:

• penalty: 制約が満たされるとき 0 となり、そうでないとき正の値をとる Expr

• body: 元の式（解における実際の値を確認する際に便利） 通常は qbpp.constrain() で構築します:

expression-class-program8.py

import pyqbpp as qbpp

x = qbpp.var("x", between=(0, 10))
c1 = qbpp.constrain(x, equal=3)              # penalty = (x - 3)^2
c2 = qbpp.constrain(x, between=(2, 5))       # penalty = 0 (2 <= x <= 5 のとき)
c3 = (x <= 5)                                # qbpp.constrain(x, between=(None, 5)) の省略形
c4 = (x == 3)                                # qbpp.constrain(x, equal=3) の省略形

制約式はそのまま算術式として使え、算術文脈ではその penalty 部分として振る舞います:

f = c1 + c2 + qbpp.sqr(x - 4)  # 制約式と通常の式を自由に組み合わせられる
f.simplify_as_binary()

評価前の式にアクセスするには c.body を使います（例えば解を得たあとに sol(c.body) で実値を確認）。詳細と対応する比較構文の一覧は 比較制約 を参照してください。

式に関する重要な注意事項

Term クラスは Expr よりも単純なデータ構造を持つため、メモリ使用量が少なく、操作のオーバーヘッドも低くなります。ただし、Term オブジェクトは完全な式（複数項の和）を格納できません。

Python では型変換が自動的に行われるため、以下のコードでは t += 3 * x の時点で t が Term から Expr に再束縛されます：

expression-class-program9.py

import pyqbpp as qbpp

x = qbpp.var("x")
y = qbpp.var("y")
t = 2 * x * y          # Term
t += 3 * x             # Expr に rebind（t は Term ではなくなる）
print(t)

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

2*x*y +3*x

Python では Expr を明示的に構築する必要はありません — 算術演算子が必要に応じて int / Var / Term を自動的に Expr に昇格させます。例えば、以下のプログラムは素の int から始めて式をインクリメンタルに構築します。

expression-class-program10.py

import pyqbpp as qbpp

x = qbpp.var("x", shape=4)
f = -1
for i in range(len(x)):
    f += x[i]
print(f)

このプログラムは次のように出力します。

-1 +x[0] +x[1] +x[2] +x[3]