非線形関数

Hi-QUBO では，絶対値 qbpp::abs()・ReLU qbpp::relu()・ 最大値 qbpp::max()・最小値 qbpp::min() を式の中で直接使えます． これらの関数を含む式は，Hi-QUBO にバンドルされているソルバーが 関数値を直接扱って効率よく探索を行います． 補助変数やペナルティ多項式を手動で設計する必要はありません． ネイティブ整数変数と組み合わせて使うこともできます．

絶対値: abs

qbpp::abs(f) は \(|f|\)，qbpp::abs(f, 2) は \(|f|^2\) を表します （指数は 1 か 2）．次のプログラムは \(|x + y - 13| + |x - y - 3|\) を最小化します:

basic-operators-and-functions-program1.cpp
#include <qbpp/qbpp.hpp>

int main() {
  auto x = qbpp::var("x");
  auto y = qbpp::var("y");
  auto f = 6 * -(x + 1) * (y - 1);
  auto g = f / 3;

  std::cout << "f = " << f << std::endl;
  std::cout << "g = " << g << std::endl;
}

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

x = 8, y = 5
f = 0

ReLU: relu

qbpp::relu(f) は \(\max(0, f)\)，qbpp::relu(f, 2) は \(\max(0, f)^2\) を表し，しきい値の超過分だけにペナルティを かけたいときに便利です．次のプログラムは，利益 \(4x + 7y\) を 最大化しつつ，作業量 \(2x + 3y\) が 36 を超えた分に 2 乗ペナルティを かけ，さらにネイティブ制約 \(x + y \le 12\) を 課しています:

basic-operators-and-functions-program2.cpp
#include <qbpp/qbpp.hpp>

int main() {
  auto x = qbpp::var("x");
  auto y = qbpp::var("y");
  auto f = 6 * x + 4;

  f += 3 * y;
  std::cout << "f = " << f << std::endl;

  f -= 12;
  std::cout << "f = " << f << std::endl;

  f *= 2 * y;
  std::cout << "f = " << f << std::endl;

  f /= 2;
  std::cout << "f = " << f << std::endl;
}

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

x = 0, y = 12
profit = 84

最大値と最小値: max / min

qbpp::max(f, g)・qbpp::min(f, g) は 2 つの式の最大値・最小値を 表します．次のプログラムは，4 個のジョブを 2 台のマシンに割り当て， 負荷の大きい方（メイクスパン）を最小化します:

basic-operators-and-functions-program3.cpp
#include <qbpp/qbpp.hpp>

int main() {
  auto x = qbpp::var("x");
  auto f = x + 1;

  std::cout << "f = " << qbpp::sqr(f) << std::endl;
  std::cout << "f = " << f << std::endl;

  f.sqr();
  std::cout << "f = " << f << std::endl;
}

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

makespan = 10

対応と制限

  • バンドルされているソルバー（EasySolver・ ABS3 Solver・Exhaustive Solver）は abs・relu（指数 1, 2）・max・min のすべてに対応します．

  • GurobiSolver と ScipSolver（Quadratic 方式）は abs・relu（指数 1, 2）に対応します．線形化方式の MIP ソルバー （SCIP Linearize・HiGHS・CBC・GLPK）は指数 1 のみ対応します．

  • max・min は relu の恒等式に展開されるため，MIP ソルバーでも 凸方向 — \(w \cdot \max\) の最小化と min の最大化（最小化目的の中の \(-w \cdot \min\)）— は解けます．非凸方向は明示的なエラーになります．

  • 非線形関数の係数には任意の定数を使えます．負の係数は関数値を 最大化する向きに働きます（バンドルソルバー専用 — MIP ソルバーでは 正の係数のみ使えます）．また，非線形関数を含む式は expand_cons()・reduce() には対応していません．

  • 解 sol に対する式の値 f(sol) は，ソルバーが返すエネルギーと 常に一致します．

cons() との関係

ネイティブ制約の qbpp::cons() も，値の上では非線形関数の 仲間です．等式制約の値は

\[ \operatorname{cons}(f = k) = \operatorname{abs}(f - k,\, 2) \]

と同じで，範囲制約の値は

\[ \operatorname{cons}(l \le f \le u) = \operatorname{relu}(l - f,\, 2) + \operatorname{relu}(f - u,\, 2) \]

と同じです（違反するのは高々片側なので，2 つの relu が同時に正になる ことはありません）．

違いは意味論です．cons() は式を制約として宣言し，違反本数 （Viol）の集計や実行可能性・target_energy の判定に参加します． abs()・relu() は意味論を持たない純粋な目的関数の項で， 制約としては扱われません．「満たすべき条件」には cons() を， 「値そのものをコストにしたい量」には abs()・relu() を使ってください．

PyQBPP では，絶対値 qbpp.abs()・ReLU qbpp.relu()・ 最大値 qbpp.max()・最小値 qbpp.min() を式の中で直接使えます． これらの関数を含む式は，Hi-QUBO にバンドルされているソルバーが 関数値を直接扱って効率よく探索を行います． 補助変数やペナルティ多項式を手動で設計する必要はありません． ネイティブ整数変数と組み合わせて使うこともできます．

絶対値: abs

qbpp.abs(f) は \(|f|\)，qbpp.abs(f, 2) は \(|f|^2\) を表します （指数は 1 か 2）．次のプログラムは \(|x + y - 13| + |x - y - 3|\) を最小化します:

basic-operators-and-functions-program1.py
import pyqbpp as qbpp

x = qbpp.var("x")
y = qbpp.var("y")
f = 6 * -(x + 1) * (y - 1)
g = f / 3

print("f =", f)
print("g =", g)

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

x = 8, y = 5
f = 0

ReLU: relu

qbpp.relu(f) は \(\max(0, f)\)，qbpp.relu(f, 2) は \(\max(0, f)^2\) を表し，しきい値の超過分だけにペナルティを かけたいときに便利です．次のプログラムは，利益 \(4x + 7y\) を 最大化しつつ，作業量 \(2x + 3y\) が 36 を超えた分に 2 乗ペナルティを かけ，さらにネイティブ制約 \(x + y \le 12\) を 課しています:

basic-operators-and-functions-program2.py
import pyqbpp as qbpp

x = qbpp.var("x")
y = qbpp.var("y")
f = 6 * x + 4

f += 3 * y
print("f =", f)

f -= 12
print("f =", f)

f *= 2 * y
print("f =", f)

f /= 2
print("f =", f)

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

x = 0, y = 12
profit = 84

最大値と最小値: max / min

qbpp.max(f, g)・qbpp.min(f, g) は 2 つの式の最大値・最小値を 表します．次のプログラムは，4 個のジョブを 2 台のマシンに割り当て， 負荷の大きい方（メイクスパン）を最小化します:

basic-operators-and-functions-program3.py
import pyqbpp as qbpp

x = qbpp.var("x")
f = x + 1

print("f =", qbpp.sqr(f))
print("f =", f)

f.sqr()
print("f =", f)

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

makespan = 10

対応と制限

  • バンドルされているソルバー（EasySolver・ ABS3 Solver・Exhaustive Solver）は abs・relu（指数 1, 2）・max・min のすべてに対応します．

  • MIP ソルバーでは，GurobiSolver が abs・relu（指数 1, 2）と max・min の凸方向（w·max の最小化・min の最大化）に対応します （係数は正のみ）．他の MIP ラッパーは非線形関数に対応していません．

  • 非線形関数の係数には任意の定数を使えます．負の係数は関数値を 最大化する向きに働きます．また，非線形関数を含む式は expand_cons()・reduce() には対応していません．

  • 解 sol に対する式の値 f(sol) は，ソルバーが返すエネルギーと 常に一致します．

cons() との関係

ネイティブ制約の qbpp.cons() も，値の上では非線形関数の 仲間です．等式制約の値は

\[ \operatorname{cons}(f = k) = \operatorname{abs}(f - k,\, 2) \]

と同じで，範囲制約の値は

\[ \operatorname{cons}(l \le f \le u) = \operatorname{relu}(l - f,\, 2) + \operatorname{relu}(f - u,\, 2) \]

と同じです（違反するのは高々片側なので，2 つの relu が同時に正になる ことはありません）．

違いは意味論です．cons() は式を制約として宣言し，違反本数 （Viol）の集計や実行可能性・target_energy の判定に参加します． abs()・relu() は意味論を持たない純粋な目的関数の項で， 制約としては扱われません．「満たすべき条件」には cons() を， 「値そのものをコストにしたい量」には abs()・relu() を使ってください．