非線形関数

QUBO++ では，絶対値 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|$ を最小化します:

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

int main() {
  auto x = 0 <= qbpp::int_var("x") <= 10;
  auto y = 0 <= qbpp::int_var("y") <= 10;
  auto f = qbpp::abs(x + y - 13) + qbpp::abs(x - y - 3);
  f.simplify_as_binary();
  auto solver = qbpp::ExhaustiveSolver(f);
  auto sol = solver.search();
  std::cout << "x = " << sol(x) << ", y = " << sol(y) << std::endl;
  std::cout << "f = " << sol.energy() << 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$ を課しています:

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

int main() {
  auto x = 0 <= qbpp::int_var("x") <= 20;
  auto y = 0 <= qbpp::int_var("y") <= 20;
  auto profit = 4 * x + 7 * y;
  auto overtime = qbpp::relu(2 * x + 3 * y - 36, 2);
  auto f = -profit + overtime + 100 * qbpp::cons(x + y <= 12);
  f.simplify_as_binary();
  auto solver = qbpp::ExhaustiveSolver(f);
  auto sol = solver.search();
  std::cout << "x = " << sol(x) << ", y = " << sol(y) << std::endl;
  std::cout << "profit = " << sol(profit) << std::endl;
}

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

x = 0, y = 12
profit = 84

最大値と最小値: max / min

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

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

int main() {
  auto a = qbpp::var("a", 4);
  int p[] = {5, 3, 7, 4};
  qbpp::Expr load1, load2;
  for (int i = 0; i < 4; ++i) {
    load1 += p[i] * a(i);
    load2 += p[i] * (1 - a(i));
  }
  auto f = qbpp::max(load1, load2);
  f.simplify_as_binary();
  auto solver = qbpp::ExhaustiveSolver(f);
  auto sol = solver.search();
  std::cout << "makespan = " << sol.energy() << 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() を使ってください．