範囲制約と整数線形計画問題の解法

範囲制約のための多項式表現

$f$ を二進変数の多項式表現とする。 範囲制約は $l\leq f\leq u$ の形で表され、$l<u$ である。 我々の目標は、範囲制約が満たされる場合にのみ最小値 0 を取る多項式表現を設計することである。

重要なアイデアは、範囲 $[l,u]$ の値を取る補助的な整数変数 $a$ を導入することである。 次の式を考えてみよう：

この式 $g$ は、$f=a$ の場合にのみ最小値 0 を取る。 $a$ が $[l,u]$ の任意の整数値を取れるため、式 $g$ が 0 を達成するのは、$f$ 自体が同じ範囲内の整数値を取る場合に限られる。

この補助変数技法を用いて、QUBO++は範囲制約を実装する。 $f$が線形式である場合、$g$はQUBO式となる。 $f$が3次以上の多項式である場合、$g$はHUBO式となる。

注記 QUBO++は内部的に軽量な改良を施しており、これにより範囲制約をわずかに少ない数の二値変数で符号化できる。 詳細は比較演算子で説明されている

整数線形計画問題の解法

整数線形計画問題のインスタンスは、目的関数と複数の線形制約で構成される。 例えば、以下の整数線形計画問題は2つの変数、1つの目的関数、2つの制約を持つ：

この問題の最適解は $x=4$, $y=5$ で、目的関数値は $40$ となる。

以下のQUBO++プログラムはEasy Solverを用いてこの最適解を求めます：

#include "qbpp.hpp"
#include "qbpp_easy_solver.hpp"

int main() {
  auto x = 0 <= qbpp::var_int("x") <= 10;
  auto y = 0 <= qbpp::var_int("y") <= 10;
  auto f = 5 * x + 4 * y;
  auto c1 = 0 <= 2 * x + 3 * y <= 24;
  auto c2 = 0 <= 7 * x + 5 * y <= 54;
  auto g = -f + 100 * (c1 + c2);
  g.simplify_as_binary();
  auto solver = qbpp::easy_solver::EasySolver(g);
  solver.time_limit(1.0);
  auto sol = solver.search();
  std::cout << "x = " << sol(x) << ", y = " << sol(y) << std::endl;
  std::cout << "f = " << sol(f) << std::endl;
  std::cout << "c1 = " << sol(c1) << ", c2 = " << sol(c2) << std::endl;
  std::cout << "*c1 = " << sol(*c1) << ", *c2 = " << sol(*c2) << std::endl;
}

このQUBO++プログラムにおいて、

• f は目的関数を表し、
• c1 およびc2は範囲制約を表し、
• g これらを単一の最適化式に統合します。

目的関数は最大化であるため、目的関数は -fと表される。 制約条件 c1 および c2 は、高い優先度で満たされるよう重み100でペナルティが課される。

Easy Solverインスタンスが作成され gが作成され、1.0秒の時間制限で探索が実行される。 最適解を取得後 solを得た後、プログラムは x, y, f, c1, c2, *c1, および *c2.

プログラムは以下を出力する:

x = 4, y = 5
f = 40
c1 = 0, c2 = 0
*c1 = 23, *c2 = 53

ここで、

• c1 は制約条件の式 0 <= 2 x + 3 y <= 24を表す式であり、
• *c1 は線形式を表します 2 x + 3 y.

ソルバーが最適解を正しく見つけ出していることを確認できます。