ネイティブ整数変数

整数変数と連立方程式の求解では，複数のバイナリ変数を組み合わせて 整数を表現する方法を説明しました．Hi-QUBO はこれに加えて， 整数値をそのまま保持するネイティブ整数変数をサポートしています． qbpp::int_var() で宣言した変数はバイナリ変数に展開されず， Hi-QUBO にバンドルされているソルバー （EasySolver・ABS3 Solver・Exhaustive Solver）が 整数値を直接扱って効率よく探索を行います．

宣言と基本的な使い方

ネイティブ整数変数は，整数変数（var_int）と同じ書き方で， 名前と値の範囲（下限・上限）を範囲演算子で指定して宣言します． 範囲の指定は必須です．宣言した変数は通常の変数と同じように式の中で使えます:

integer-variables-and-linear-systems-program1.cpp

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

int main() {
  auto x = 0 <= qbpp::int_var("x") <= 10;
  auto f = x * x - 4 * x;
  f.simplify_as_binary();
  auto solver = qbpp::ExhaustiveSolver(f);
  auto sol = solver.search();
  std::cout << "x = " << sol(x) << std::endl;
  std::cout << "f = " << sol.energy() << std::endl;
}

プログラムの出力は以下の通りです:

x = 2
f = -4

x * x のような冪に，バイナリ変数の規則（\(x \cdot x = x\)）は適用されず， 整数の二乗としてそのまま扱われる点に注意してください．

連立方程式を解く例

次のプログラムは，連立方程式 \(x + 2y = 700\)，\(x - y = 100\) を 2 乗誤差の最小化として解きます:

integer-variables-and-linear-systems-program2.cpp

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

int main() {
  auto x = 0 <= qbpp::int_var("x") <= 1000;
  auto y = -1000 <= qbpp::int_var("y") <= 1000;
  auto f = qbpp::sqr(x + 2 * y - 700) + qbpp::sqr(x - y - 100);
  f.simplify_as_binary();
  auto solver = qbpp::EasySolver(f);
  auto sol = solver.search({{"time_limit", 1.0}});
  std::cout << "x = " << sol(x) << ", y = " << sol(y) << std::endl;
  std::cout << "f = " << sol.energy() << std::endl;
}

プログラムの出力は以下の通りです:

x = 300, y = 200
f = 0

整数変数の配列

int_var() に次元を渡すと，ネイティブ整数変数の配列が作れます． 要素には s[i] でアクセスし，qbpp::sum() で総和の式が作れます:

integer-variables-and-linear-systems-program3.cpp

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

int main() {
  auto s = 0 <= qbpp::int_var("s", 3) <= 9;
  auto t = qbpp::sum(s);
  auto f = qbpp::sqr(t - 6) + qbpp::sqr(s[0] - s[1] + 1) +
           qbpp::sqr(s[1] - s[2] + 1);
  f.simplify_as_binary();
  auto solver = qbpp::ExhaustiveSolver(f);
  auto sol = solver.search();
  std::cout << "s = " << sol(s[0]) << ", " << sol(s[1]) << ", " << sol(s[2])
            << std::endl;
  std::cout << "f = " << sol.energy() << std::endl;
}

プログラムの出力は以下の通りです:

s = 1, 2, 3
f = 0

要素ごとに範囲が異なる配列

配列形の宣言は，全要素が同じ範囲を共有します．範囲の下限・上限に 配列を指定すると，要素ごとに個別の範囲を持つネイティブ整数変数の 配列が作られます．下限と上限が等しい要素は，その値に固定された 定数になります:

integer-variables-and-linear-systems-program4.cpp

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

int main() {
  const auto lower = qbpp::array({1, 0, 2});
  const auto upper = qbpp::array({4, 3, 2});
  auto v = lower <= qbpp::int_var("v", 3) <= upper;
  auto f = qbpp::sqr(qbpp::sum(v) - 6) + v[0];
  f.simplify_as_binary();
  auto solver = qbpp::ExhaustiveSolver(f);
  auto sol = solver.search();
  std::cout << "v = " << sol(v[0]) << ", " << sol(v[1]) << ", " << sol(v[2])
            << std::endl;
  std::cout << "f = " << sol.energy() << std::endl;
}

プログラムの出力は以下の通りです（v[2] は下限＝上限なので 定数 2 に固定されます）:

v = 1, 3, 2
f = 1

片側だけ配列にすることもできます（例: 0 <= qbpp::int_var("w", 3) <= upper は下限 0 を全要素で共有します）．

また，切り出しの var_int と同じ プレースホルダの書き方も使えます．qbpp::int_var("x", 3) == 0 は 全要素が定数 0 の可変配列を作り，各要素にネイティブ整数変数を ひとつずつ代入できます:

integer-variables-and-linear-systems-program5.cpp

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

int main() {
  const auto cap = qbpp::array({3, 1, 2});
  auto x = qbpp::int_var("x", 3) == 0;
  for (size_t j = 0; j < cap.size(); j++) {
    x[j] = 0 <= qbpp::int_var() <= cap[j];
  }
  auto f = qbpp::sqr(qbpp::sum(x) - 5) - x[0] - x[1];
  f.simplify_as_binary();
  auto solver = qbpp::ExhaustiveSolver(f);
  auto sol = solver.search();
  std::cout << "x = " << sol(x[0]) << ", " << sol(x[1]) << ", " << sol(x[2])
            << std::endl;
  std::cout << "f = " << sol.energy() << std::endl;
}

プログラムの出力は以下の通りです:

x = 3, 1, 1
f = -4

代入しなかった要素は定数（ここでは 0）のまま式に残ります． 定数には 0 以外の値も指定できます．

制約との併用

ネイティブ制約の qbpp::cons() は， ネイティブ整数変数を含む式にもそのまま使えます:

integer-variables-and-linear-systems-program6.cpp

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

int main() {
  auto x = 0 <= qbpp::int_var("x") <= 5;
  auto y = 0 <= qbpp::int_var("y") <= 5;
  auto f = -(2 * x + 3 * y) + 50 * qbpp::cons(x + y == 8);
  f.simplify_as_binary();
  auto solver = qbpp::ExhaustiveSolver(f);
  auto sol = solver.search();
  std::cout << "x = " << sol(x) << ", y = " << sol(y) << std::endl;
}

プログラムの出力は以下の通りです:

x = 3, y = 5

外部ソルバーとの連携

GurobiSolver などの MIP ソルバーは整数変数をそのまま 扱えるため，ネイティブ整数変数は整数の列として直接渡されます （バイナリ変数には展開されません）．qbpp::GurobiSolver solver(f); は 二次の目的関数（MIQP）まで対応します．目的関数が線形で制約を qbpp::cons() で書いたモデルは，qbpp::ScipSolver solver(f, qbpp::ilp); のように ILP オプションを付ければ 5 種の MIP ソルバーすべてで解けます．

一方，バイナリ変数専用の外部 QUBO ソルバーに渡す場合は， qbpp::binarize() で従来のバイナリエンコーディングに 変換してください:

integer-variables-and-linear-systems-program7.cpp

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

int main() {
  auto x = 0 <= qbpp::int_var("x") <= 10;
  auto f = x * x - 4 * x;
  auto g = qbpp::binarize(f);
  g.simplify_as_binary();
  auto solver = qbpp::ExhaustiveSolver(g);
  auto sol = solver.search();
  std::cout << "minimum = " << sol.energy() << std::endl;
}

プログラムの出力は以下の通りです:

minimum = -4

使い分けの指針

• 個数・時刻・在庫量など数量を表す変数には，ネイティブ整数変数が適しています．

• 外部のバイナリ専用ソルバーに渡すモデルは， バイナリエンコーディングの整数変数（var_int）を使うか， qbpp::binarize() で変換してください．

• 「どれを選ぶか」というラベル（訪問順序・色など）には， ネイティブ整数変数よりも one-hot 表現 （置換行列・One-hot 制約）が適しています．

なお，ライセンスの変数数の上限では，ネイティブ整数変数 1 個は， その範囲（上限 − 下限）を \(r\) とすると，次の個数のバイナリ変数分として カウントされます:

\[ \lceil \log_2 (r+1) \rceil \]

詳細はライセンス管理を参照してください．

整数変数と連立方程式の求解では，複数のバイナリ変数を組み合わせて 整数を表現する方法を説明しました．PyQBPP はこれに加えて， 整数値をそのまま保持するネイティブ整数変数をサポートしています． qbpp.var() の integer= キーワードで宣言した変数はバイナリ変数に展開されず， Hi-QUBO にバンドルされているソルバー （EasySolver・ABS3 Solver・Exhaustive Solver）が 整数値を直接扱って効率よく探索を行います．

宣言と基本的な使い方

ネイティブ整数変数は，integer=(下限, 上限) を指定して宣言します． 範囲の指定は必須です．宣言した変数は通常の変数と同じように式の中で使えます:

integer-variables-and-linear-systems-program1.py

import pyqbpp as qbpp

x = qbpp.var("x", integer=(0, 10))
f = x * x - 4 * x
f.simplify_as_binary()
solver = qbpp.ExhaustiveSolver(f)
sol = solver.search()
print(f"x = {sol(x)}")
print(f"f = {sol.energy}")

プログラムの出力は以下の通りです:

x = 2
f = -4

x * x のような冪に，バイナリ変数の規則（\(x \cdot x = x\)）は適用されず， 整数の二乗としてそのまま扱われる点に注意してください．

連立方程式を解く例

次のプログラムは，連立方程式 \(x + 2y = 700\)，\(x - y = 100\) を 2 乗誤差の最小化として解きます:

integer-variables-and-linear-systems-program2.py

import pyqbpp as qbpp

x = qbpp.var("x", integer=(0, 1000))
y = qbpp.var("y", integer=(-1000, 1000))
f = qbpp.sqr(x + 2 * y - 700) + qbpp.sqr(x - y - 100)
f.simplify_as_binary()
solver = qbpp.EasySolver(f)
sol = solver.search(time_limit=1.0)
print(f"x = {sol(x)}, y = {sol(y)}")
print(f"f = {sol.energy}")

プログラムの出力は以下の通りです:

x = 300, y = 200
f = 0

整数変数の配列

qbpp.var() に次元と integer= を同時に指定すると， ネイティブ整数変数の配列が作れます．要素には s[i] でアクセスし， s.sum() で総和の式が作れます:

integer-variables-and-linear-systems-program3.py

import pyqbpp as qbpp

s = qbpp.var("s", 3, integer=(0, 9))
t = s.sum()
f = qbpp.sqr(t - 6) + qbpp.sqr(s[0] - s[1] + 1) + qbpp.sqr(s[1] - s[2] + 1)
f.simplify_as_binary()
solver = qbpp.ExhaustiveSolver(f)
sol = solver.search()
print(f"s = {sol(s[0])}, {sol(s[1])}, {sol(s[2])}")
print(f"f = {sol.energy}")

プログラムの出力は以下の通りです:

s = 1, 2, 3
f = 0

要素ごとに範囲が異なる配列

integer= の下限・上限には，スカラーの代わりにリストも指定できます． リストを指定すると，要素ごとに個別の範囲を持つネイティブ整数変数の 配列が作られます（スカラー側の値は全要素で共有されます）． 下限と上限が等しい要素は，その値に固定された定数になります:

integer-variables-and-linear-systems-program4.py

import pyqbpp as qbpp

max_vals = [3, 7, 15, 5]
x = qbpp.var("x", shape=len(max_vals), integer=(0, max_vals))
f = qbpp.sqr(qbpp.sum(x) - 26) - x[0] - x[1] - x[2]
f.simplify_as_binary()
solver = qbpp.ExhaustiveSolver(f)
sol = solver.search()
print(f"x = {sol(x[0])}, {sol(x[1])}, {sol(x[2])}, {sol(x[3])}")
print(f"f = {sol.energy}")

プログラムの出力は以下の通りです:

x = 3, 7, 15, 1
f = -25

制約との併用

ネイティブ制約の qbpp.cons() は， ネイティブ整数変数を含む式にもそのまま使えます:

integer-variables-and-linear-systems-program5.py

import pyqbpp as qbpp

x = qbpp.var("x", integer=(0, 5))
y = qbpp.var("y", integer=(0, 5))
f = -(2 * x + 3 * y) + 50 * qbpp.cons(x + y == 8)
f.simplify_as_binary()
solver = qbpp.ExhaustiveSolver(f)
sol = solver.search()
print(f"x = {sol(x)}, y = {sol(y)}")

プログラムの出力は以下の通りです:

x = 3, y = 5

外部ソルバーとの連携

MIP ソルバーは整数変数をそのまま扱えるため，ネイティブ整数変数は 整数の列として直接渡されます（バイナリ変数には展開されません）． qbpp.GurobiSolver(f) は二次の目的関数（MIQP）まで対応します． 目的関数が線形で制約を qbpp.cons() で書いたモデルは， qbpp.ScipSolver(f, ilp=True) のように ilp=True を付ければ 5 種の MIP ソルバーすべてで解けます．

一方，バイナリ変数専用の外部 QUBO ソルバーに渡す場合は， qbpp.binarize() で従来のバイナリエンコーディングに 変換してください:

integer-variables-and-linear-systems-program6.py

import pyqbpp as qbpp

x = qbpp.var("x", integer=(0, 10))
f = x * x - 4 * x
g = qbpp.binarize(f)
g.simplify_as_binary()
solver = qbpp.ExhaustiveSolver(g)
sol = solver.search()
print(f"minimum = {sol.energy}")

プログラムの出力は以下の通りです:

minimum = -4

使い分けの指針

• 個数・時刻・在庫量など数量を表す変数には，ネイティブ整数変数が適しています．

• 外部のバイナリ専用ソルバーに渡すモデルは， バイナリエンコーディングの整数変数（between=）を使うか， qbpp.binarize() で変換してください．

• 「どれを選ぶか」というラベル（訪問順序・色など）には， ネイティブ整数変数よりも one-hot 表現 （置換行列・One-hot 制約）が適しています．

なお，ライセンスの変数数の上限では，ネイティブ整数変数 1 個は， その範囲（上限 − 下限）を \(r\) とすると，次の個数のバイナリ変数分として カウントされます:

\[ \lceil \log_2 (r+1) \rceil \]