非線形関数

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

絶対値: abs

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

import pyqbpp as qbpp

x = qbpp.var("x", integer=(0, 10))
y = qbpp.var("y", integer=(0, 10))
f = qbpp.abs(x + y - 13) + qbpp.abs(x - y - 3)
f.simplify_as_binary()
solver = qbpp.ExhaustiveSolver(f)
sol = solver.search()
print(f"x = {sol(x)}, y = {sol(y)}")
print(f"f = {sol.energy}")

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

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$ を課しています:

import pyqbpp as qbpp

x = qbpp.var("x", integer=(0, 20))
y = qbpp.var("y", integer=(0, 20))
profit = 4 * x + 7 * y
overtime = qbpp.relu(2 * x + 3 * y - 36, 2)
f = -profit + overtime + 100 * qbpp.cons(x + y <= 12)
f.simplify_as_binary()
solver = qbpp.ExhaustiveSolver(f)
sol = solver.search()
print(f"x = {sol(x)}, y = {sol(y)}")
print(f"profit = {sol(profit)}")

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

x = 0, y = 12
profit = 84

最大値と最小値: max / min

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

import pyqbpp as qbpp

a = qbpp.var("a", 4)
p = [5, 3, 7, 4]
load1 = qbpp.Expr(0)
load2 = qbpp.Expr(0)
for i in range(4):
    load1 += p[i] * a[i]
    load2 += p[i] * (1 - a[i])
f = qbpp.max(load1, load2)
f.simplify_as_binary()
solver = qbpp.ExhaustiveSolver(f)
sol = solver.search()
print(f"makespan = {sol.energy}")

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

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() を使ってください．