多次元の整数、変数および式

多次元変数の定義

QUBO++は、関数qbpp::var()およびqbpp::var_int()を使用して、任意の深さの多次元変数（qbpp::Varの配列）および多次元整数変数（整数変数 qbpp::Expr の配列）をサポートしています。 基本的な使い方は次のとおりです:

• qbpp::var("name",s1,s2,...,sd): 指定されたnameと形状$s1\times s2\times \cdots\times sd$を持つqbpp::Varオブジェクトの配列を作成します。
• l <= qbpp::var_int("name",s1,s2,...,sd) <= u: 指定された範囲と形状$s1\times s2\times \cdots\times sd$を持つ整数変数 qbpp::Expr の配列を作成します。

以下のQUBO++プログラムは、それぞれ次元$2\times 3\times 4$のバイナリ変数と整数変数を作成します。

#include <qbpp/qbpp.hpp>

int main() {
  auto x = qbpp::var("x", 2, 3, 4);
  auto y = 1 <= qbpp::var_int("y", 2, 3, 4) <= 8;
  std::cout << "x : " << x << std::endl;
  std::cout << "y : " << y << std::endl;
}

このプログラムの出力は次のとおりです:

x : {{{x[0][0][0],x[0][0][1],x[0][0][2],x[0][0][3]},{x[0][1][0],x[0][1][1],x[0][1][2],x[0][1][3]},{x[0][2][0],x[0][2][1],x[0][2][2],x[0][2][3]}},{{x[1][0][0],x[1][0][1],x[1][0][2],x[1][0][3]},{x[1][1][0],x[1][1][1],x[1][1][2],x[1][1][3]},{x[1][2][0],x[1][2][1],x[1][2][2],x[1][2][3]}}}
y : {{{1 +y[0][0][0][0] +2*y[0][0][0][1] +4*y[0][0][0][2],1 +y[0][0][1][0] +2*y[0][0][1][1] +4*y[0][0][1][2],1 +y[0][0][2][0] +2*y[0][0][2][1] +4*y[0][0][2][2],1 +y[0][0][3][0] +2*y[0][0][3][1] +4*y[0][0][3][2]},{1 +y[0][1][0][0] +2*y[0][1][0][1] +4*y[0][1][0][2],1 +y[0][1][1][0] +2*y[0][1][1][1] +4*y[0][1][1][2],1 +y[0][1][2][0] +2*y[0][1][2][1] +4*y[0][1][2][2],1 +y[0][1][3][0] +2*y[0][1][3][1] +4*y[0][1][3][2]},{1 +y[0][2][0][0] +2*y[0][2][0][1] +4*y[0][2][0][2],1 +y[0][2][1][0] +2*y[0][2][1][1] +4*y[0][2][1][2],1 +y[0][2][2][0] +2*y[0][2][2][1] +4*y[0][2][2][2],1 +y[0][2][3][0] +2*y[0][2][3][1] +4*y[0][2][3][2]}},{{1 +y[1][0][0][0] +2*y[1][0][0][1] +4*y[1][0][0][2],1 +y[1][0][1][0] +2*y[1][0][1][1] +4*y[1][0][1][2],1 +y[1][0][2][0] +2*y[1][0][2][1] +4*y[1][0][2][2],1 +y[1][0][3][0] +2*y[1][0][3][1] +4*y[1][0][3][2]},{1 +y[1][1][0][0] +2*y[1][1][0][1] +4*y[1][1][0][2],1 +y[1][1][1][0] +2*y[1][1][1][1] +4*y[1][1][1][2],1 +y[1][1][2][0] +2*y[1][1][2][1] +4*y[1][1][2][2],1 +y[1][1][3][0] +2*y[1][1][3][1] +4*y[1][1][3][2]},{1 +y[1][2][0][0] +2*y[1][2][0][1] +4*y[1][2][0][2],1 +y[1][2][1][0] +2*y[1][2][1][1] +4*y[1][2][1][2],1 +y[1][2][2][0] +2*y[1][2][2][1] +4*y[1][2][2][2],1 +y[1][2][3][0] +2*y[1][2][3][1] +4*y[1][2][3][2]}}}

x の型は qbpp::Array<3, qbpp::Var>（qbpp::Var の3次元配列）、y の型は qbpp::Array<3, qbpp::Expr>（整数変数 qbpp::Expr の3次元配列）です。

x内の各qbpp::Varオブジェクトはx[i][j][k]としてアクセスできます。 y内の各整数変数 qbpp::Expr はy[i][j][k]としてアクセスでき、 内部的には以下の3つのバイナリ変数で表現されます:

• y[i][j][k][0]
• y[i][j][k][1]
• y[i][j][k][2]

これらは指定された範囲の整数のバイナリエンコーディングに対応しています。

配列ファクトリ (qbpp::array<T>)

qbpp::array<T> は配列を作成する汎用ファクトリ関数です。要素型 T には qbpp::coeff_t（整数定数）、qbpp::Var、qbpp::Term、qbpp::Expr を指定できます。 初期化子から T を推論できる場合はテンプレート引数を省略できます。

呼び出し形式	戻り値	説明
qbpp::array<coeff_t>(s1, s2, ..., sd)	qbpp::Array<d, qbpp::coeff_t>	形状指定でゼロ初期化された整数配列
qbpp::array<qbpp::Expr>(s1, s2, ..., sd)	qbpp::Array<d, qbpp::Expr>	形状指定でゼロ初期化された式配列（qbpp::expr(s1, s2, ..., sd) と等価）
qbpp::array({v1, v2, ...})	qbpp::Array<1, qbpp::coeff_t>	1次元整数定数配列（T 推論）
qbpp::array({{a,b},{c,d}})	qbpp::Array<2, qbpp::coeff_t>	2次元整数定数配列（T 推論）
qbpp::array<qbpp::Expr>({v1, v2, ...})	qbpp::Array<1, qbpp::Expr>	int 値を Expr に昇格
qbpp::array<qbpp::Expr>({{a,b},{c,d}})	qbpp::Array<2, qbpp::Expr>	2次元 int 値を Expr に昇格

形状のみを指定する形（qbpp::array<T>(s1, s2, ...)）では、次元数からは T を 推論できないためテンプレート引数の明示が必要です。

整数定数配列は変数配列との要素ごとの演算に使用できます。以下のプログラムは、$2\times 2$ の整数定数行列 c とバイナリ変数行列 x の要素ごとの積を合計します:

#include <qbpp/qbpp.hpp>

int main() {
  auto c = qbpp::array({{1, 2}, {3, 4}});
  auto x = qbpp::var("x", 2, 2);
  auto f = qbpp::sum(c * x);
  std::cout << "f = " << f << std::endl;
}

ここで c の型は qbpp::Array<2, qbpp::coeff_t>（2次元の整数定数配列）、x の型は qbpp::Array<2, qbpp::Var> です。 c * x は要素ごとの積を2次元の項の配列（qbpp::Array<2, qbpp::Term>）として返し、qbpp::sum がその全要素を合計して単一の Expr を返します。このプログラムの出力は以下の通りです:

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

個別の範囲を持つ整数変数配列の作成

多次元整数変数配列を定義する場合、l <= qbpp::var_int("name", s1, s2, ...) <= u で作成された全要素は同じ範囲 $[l, u]$ を共有します。 しかし実際の問題では、各要素に異なる範囲が必要な場合が多くあります。

このような場合、まず qbpp::var_int("name", s1, s2, ...) == 0 でプレースホルダ配列を作成し、ループ内で各要素に個別の範囲を割り当てます:

#include <qbpp/qbpp.hpp>

int main() {
  auto max_vals = qbpp::array({3, 7, 15, 5});
  auto x = qbpp::var_int("x", max_vals.size()) == 0;
  for (size_t i = 0; i < max_vals.size(); ++i) {
    x[i] = 0 <= qbpp::var_int() <= max_vals[i];
  }
  for (size_t i = 0; i < max_vals.size(); ++i) {
    std::cout << "x[" << i << "] = " << x[i] << std::endl;
  }
}

このプログラムでは、max_vals の型は qbpp::Array<1, qbpp::coeff_t>（1次元の整数定数配列）です。 qbpp::var_int("x", 4) == 0 がプレースホルダとして定数ゼロの整数変数 qbpp::Expr 4個の配列を作成するので、x の型は qbpp::Array<1, qbpp::Expr> になります。 各要素は 0 <= qbpp::var_int() <= max_vals[i] で個別の範囲に再代入されます。

このテクニックは、各変数の上限が異なる切り出し問題などでよく使われます。

注意 == 0 の構文は min_val = max_val = 0（定数ゼロ）の整数変数を作成するものであり、等号制約を作成するものではありません。 任意の整数定数を使用でき、例えば qbpp::var_int("x", 4) == 5 は定数5のプレースホルダを作成します。

多次元式の定義

QUBO++では、関数qbpp::expr()を使用して任意の深さの多次元式（qbpp::Exprオブジェクト）を定義できます:

• qbpp::expr(s1,s2,...,sd): 形状$s1\times s2\times \cdots\times sd$のqbpp::Exprオブジェクトの多次元配列を作成します。

以下のプログラムは、形状$2\times 3\times 4$のqbpp::Varオブジェクトの3次元配列xと、サイズ$2\times 3$の2次元配列fを定義します。 次に、3重forループを使用して、各f[i][j]にx[i][j][0]、x[i][j][1]、x[i][j][2]、x[i][j][3]の和を蓄積します:

#include <qbpp/qbpp.hpp>

int main() {
  auto x = qbpp::var("x", 2, 3, 4);
  auto f = qbpp::expr(2, 3);
  for (size_t i = 0; i < 2; ++i) {
    for (size_t j = 0; j < 3; ++j) {
      for (size_t k = 0; k < 4; ++k) {
        f[i][j] += x[i][j][k];
      }
    }
  }
  f.simplify_as_binary();
  std::cout << "f = " << f << std::endl;
  for (size_t i = 0; i < 2; ++i) {
    for (size_t j = 0; j < 3; ++j) {
      std::cout << "f[" << i << "][" << j << "] = " << f[i][j] << std::endl;
    }
  }
}

ここで x の型は qbpp::Array<3, qbpp::Var>、f の型は qbpp::Array<2, qbpp::Expr> です。

simplify_as_binary()メンバ関数はqbpp::Exprオブジェクトの多次元配列に対しても適用できます。 このような配列に対して呼び出された場合、各要素に対して個別に（要素ごとに）simplify_as_binary()が適用されます。

このプログラムの出力は次のとおりです:

f = {{x[0][0][0] +x[0][0][1] +x[0][0][2] +x[0][0][3],x[0][1][0] +x[0][1][1] +x[0][1][2] +x[0][1][3],x[0][2][0] +x[0][2][1] +x[0][2][2] +x[0][2][3]},{x[1][0][0] +x[1][0][1] +x[1][0][2] +x[1][0][3],x[1][1][0] +x[1][1][1] +x[1][1][2] +x[1][1][3],x[1][2][0] +x[1][2][1] +x[1][2][2] +x[1][2][3]}}
f[0][0] = x[0][0][0] +x[0][0][1] +x[0][0][2] +x[0][0][3]
f[0][1] = x[0][1][0] +x[0][1][1] +x[0][1][2] +x[0][1][3]
f[0][2] = x[0][2][0] +x[0][2][1] +x[0][2][2] +x[0][2][3]
f[1][0] = x[1][0][0] +x[1][0][1] +x[1][0][2] +x[1][0][3]
f[1][1] = x[1][1][0] +x[1][1][1] +x[1][1][2] +x[1][1][3]
f[1][2] = x[1][2][0] +x[1][2][1] +x[1][2][2] +x[1][2][3]

auto型推論による式配列の作成

qbpp::Exprオブジェクトの配列は、qbpp::expr()を明示的に呼び出さずに作成できます。 関数呼び出しや算術演算が配列形状の結果を返す場合、auto型推論を使用して同じ形状のqbpp::Exprオブジェクトの配列を定義できます。

以下のQUBO++プログラムは、qbpp::Varオブジェクトの配列xと同じ次元のqbpp::Exprオブジェクトの配列fを作成します:

#include <qbpp/qbpp.hpp>

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

このプログラムでは、xは$2 \times 3$のqbpp::Varオブジェクトの配列（型は qbpp::Array<2, qbpp::Var>）として定義されています。 式x + 1は$2 \times 3$のqbpp::Exprオブジェクトの配列を生成し、auto型推論を通じてfの初期化に使用されるので、f の型は qbpp::Array<2, qbpp::Expr> になります。 その後、式x - 2がfに要素ごとに加算されます。

このプログラムの出力は次のとおりです:

f[0][0] = -1 +2*x[0][0]
f[0][1] = -1 +2*x[0][1]
f[0][2] = -1 +2*x[0][2]
f[1][0] = -1 +2*x[1][0]
f[1][1] = -1 +2*x[1][1]
f[1][2] = -1 +2*x[1][2]

配列

QUBO++ は、次元数と要素型（qbpp::Var, qbpp::Expr, qbpp::Term, または整数係数型）をコンパイル時に決定する多次元配列を提供しています。 実際には配列の型を手書きする必要はほとんどありません。ファクトリ関数と auto による型推論が適切な具体化を選んでくれて、要素ごとの +, -, *, 代入などの演算が宣言された要素型と整合しているかをコンパイラが検査します。 配列は operator[] のチェーン（例: x[i][j][k]）による多次元インデックスアクセスと、要素ごとの算術演算を提供します。

配列は以下のファクトリ関数で作成します（Dim = d は次元数）:

• qbpp::var("name", s1, s2, ..., sd) → qbpp::Array<d, qbpp::Var>: 多次元のバイナリ変数の配列。
• qbpp::expr(s1, s2, ..., sd) → qbpp::Array<d, qbpp::Expr>: ゼロ初期化された多次元の式の配列（qbpp::array<qbpp::Expr>(s1, s2, ..., sd) の別名）。
• qbpp::array({v1, v2, ...}) → qbpp::Array<1, qbpp::coeff_t>: 1次元の整数定数の配列（T 推論）。
• qbpp::array<qbpp::coeff_t>(s1, s2, ..., sd) → qbpp::Array<d, qbpp::coeff_t>: ゼロ初期化された多次元の整数配列。qbpp::array<qbpp::Expr>(...) で式配列も作成できます（qbpp::expr(...) と同じ）。
• l <= qbpp::var_int("name", s1, s2, ..., sd) <= u → qbpp::Array<d, qbpp::Expr>: 多次元の整数変数の配列。

注意 — 型を明示的に書く必要がある場合 ローカル変数であれば auto が適切な qbpp::Array<Dim, T> の具体化を推論するので、型を手書きする必要はほとんどありません。 例外は 非 static なクラスのメンバ変数で、C++ は非 static メンバに auto を許さないため、qbpp::Array<2, qbpp::Expr> のような完全な型をメンバ宣言で明示する必要があります。

配列は以下のメンバ関数を提供しています:

• size(): 最外次元のサイズを返します。
• total(): 全要素数を返します。
• ndim(): 次元数（Dim と等しい）を返します。
• shape(d): 次元 d のサイズを返します。
• empty(): 配列が空の場合 true を返します。
• operator[]: 要素（Dim == 1 のとき）またはサブ配列（Dim > 1 のとき）を返します。
• begin() / end(): range-based for ループ用イテレータ。

注意 — 要素型と演算結果 算術演算はスカラー式と同じ規則で要素型を昇格させます：変数の配列に 1 を足すと式の配列になり、変数の配列同士の要素ごとの積は項の配列になります。一方、+=, -=, *= のような複合代入は左辺の要素型を変えません。したがって変数の配列に += で 1 を足すとコンパイルエラーになります — auto f = x + 1; のように新しい式の配列を作って受け取ってください。

さらに、配列は要素ごとの演算のために以下の演算子をサポートしています:

• +: 2つの配列、または配列とスカラーの要素ごとの加算。
• -: 2つの配列、または配列とスカラーの要素ごとの減算。
• *: 2つの配列、または配列とスカラーの要素ごとの乗算。
• 単項 -: 配列内のすべての要素を否定します。
• 単項 ~: 配列内のすべての変数リテラルを否定します。

多次元配列は、形状情報を持つ単一のフラット配列として実装されています。 例えば、以下のコードにおける x は shape (2, 3) の変数の2次元配列です:

  auto x = qbpp::var("x", 2, 3);

上記の要素ごとの演算は、オペランドが同じ形状を持つ場合にのみ多次元配列でサポートされます。

多次元配列は operator[] を使ったインデックスベースの for ループでアクセスできます:

#include <qbpp/qbpp.hpp>

int main() {
  auto x = qbpp::var("x", 2, 3);
  auto f = x + 1;
  f += x - 2;
  f.simplify_as_binary();
  std::cout << "total = " << f.total() << std::endl;
  std::cout << "ndim = " << f.ndim() << std::endl;
  std::cout << "shape = (" << f.shape(0) << ", " << f.shape(1) << ")" << std::endl;
  for (size_t i = 0; i < f.size(); ++i) {
    for (size_t j = 0; j < f[i].size(); ++j) {
      std::cout << "(" << f[i][j] << ")";
    }
    std::cout << std::endl;
  }
}

ここで、f.total()は全要素数、f.ndim()は次元数、f.shape(d)は次元dのサイズを返します。 f[i][j]は行i、列jの要素にアクセスします。

このプログラムの出力は次のとおりです:

(-1 +2*x[0][0])(-1 +2*x[0][1])(-1 +2*x[0][2])
(-1 +2*x[1][0])(-1 +2*x[1][1])(-1 +2*x[1][2])

サブ配列アクセスと操作

多次元配列から行や列などのサブ配列を取得するには、タプルインデックス（Array::operator()）を使います。 任意の軸に沿ったスライスや連結については スライス関数と連結関数 を参照してください。