🕸️

QUBO++入門:比較演算子(整数計画法)

2025/01/20に公開

QUBO++の比較演算子

QUBO++では,以下の2種類の比較演算子をサポートしています.

  • 等価演算子 ==
    式 == 整数の形式を指定します.この演算子は,条件が成立する場合に最小値0を,成立しない場合に1以上を返す式を生成します.
  • 範囲比較演算子 <=<=
    下限整数 <= 式 <= 上限整数の形式を指定します.同様に,条件が成立する場合は最小値0,成立しない場合は1以上を返す式を生成します.

等価演算子==

式をf,整数をbとすると,等価演算子は以下の式を返します.

(f-b)^2

この式は,f = bを満たす場合に最小値0をとり,それ以外では1以上の値をとります.また,f が一次式である場合,この式は二次式となるため,QUBO式となります.

範囲比較演算子 <=<=

式をf,下限整数をl,上限整数をuとします.また,n = u - lと定義します.nの値に応じて,生成される式の形式が変わります.いずれの場合も,範囲比較演算l \leq f \leq uが成立する場合に最小値0をとり,成立しない場合には1以上をとります.同様に,f が一次式である場合,この式は二次式となるため,QUBO式となります.

  • n = 0の場合 : l = uとなるため,以下の式を返します.
(f-u)^2
  • n = 1の場合:以下のQUBO式を返します.
(f-l)(f-u)

この式は,f = lまたはf = uのときに値が0となり,それ以外では1以上となります.

  • n \geq 2の場合:スラック変数aを導入し,a \in [l, u-1]となるよう設定します.以下の式を返します.
(f−a)(f−(a+1))

f[u,l]の範囲に入るとき,この式の値が最小値0となるようにスラック変数aの値を決めることができます.一方,範囲に入らないとき,スラック変数aがどのような値でも,この式の値は1以上となります.

スラック変数aは整数変数を用います.この整数変数を構成する際,係数を2から始めることで,必要な二値変数の個数を削減できます.例えば,[1,10]の整数値を取るスラック変数aについて,二値変数とその係数は次のように決定されます.

a = 1 下限値1
a = 1 + 2*a[0] 上限値3
a = 1 + 2*a[0] +4*a[1] 上限値7
a = 1 + 2*a[0] +4*a[1] + 8*a[2] 上限値15
a = 1 + 2*a[0] +4*a[1] + 3*a[2] 上限値10に調整

このように構成されたスラック変数aによって,範囲[1, 11]内の全ての整数はaまたはa+1で表すことができます.

整数計画問題

範囲比較演算子を用いることで,整数計画問題をQUBO問題として定式化し,解くことができます.例として,次の整数計画問題を取り上げます.

問題設定

  • 最大化:2x+3y
  • 制約条件1:0\leq x+y\leq 7
  • 制約条件2:0\leq 3x+5y \leq 28
  • 制約条件3:0\leq x
  • 制約条件4:0\leq y

QUBO++での整数変数の生成

QUBO++では,整数変数を用いてxyを生成します.この際,各変数に対して上限値を与える必要があります.まず,xyの上限値を決定するために,次の条件を考えます.

\begin{align*} x &\leq \min(7,\frac{28}{3})\\ y &\leq \min(7,\frac{28}{5}) \end{align*}

これらの計算結果から,以下の範囲が得られます.

\begin{align*} 0 &\leq x \leq 7 \\ 0 &\leq y \leq 5 \end{align*}

このようにして,xyの上限値と下限値を設定することができます.

整数計画問題をQUBO++で解く

QUBO++の範囲比較演算子<=<=を用いることで,整数計画問題を解くQUBO式を構築することができます.以下のコードは,上記の整数計画問題をQUBO式に変換し,Exhaustive Solverを用いて解を求める例です.

#include "qbpp.hpp"
#include "qbpp_exhaustive_solver.hpp"

int main() {
  auto x = 0 <= qbpp::var_int("x") <= 7;
  auto y = 0 <= qbpp::var_int("y") <= 5;
  auto obj = 2 * x + 3 * y;
  auto c1 = 0 <= x + y <= 7;
  auto c2 = 0 <= 3 * x + 5 * y <= 28;

  auto f = -obj + 100 * (c1 + c2);
  f.simplify_as_binary();
  std::cout << "f = " << f << std::endl;

  auto solver = qbpp::exhaustive_solver::ExhaustiveSolver(f);
  auto sol = solver.search();
  std::cout << sol << std::endl;
  std::cout << "x = " << sol.get(x) << std::endl;
  std::cout << "y = " << sol.get(y) << std::endl;
  std::cout << "obj = " << sol.get(obj) << std::endl;
  std::cout << "c1 = " << sol.get(x + y) << std::endl;
  std::cout << "c2 = " << sol.get(3 * x + 5 * y) << std::endl;
}

コードの説明

  1. 整数変数の生成
    整数変数xyをそれぞれ[0,7][0,5]の範囲で生成しています.
  2. 目的関数の定期
    QUBO式objに目的関数を生成しています.
  3. 制約条件の生成
    制約条件1と2をそれぞれQUBO式c1c2として生成しています.
  4. QUBO式の構築
    最終的なQUBO式fは,以下のように構築されています.
  • -objは目的関数の最大化を最小化問題に変換するための項です.
  • 制約条件c1c2は,条件を満たすことを優先させるために100倍の重みを付けています.
    これにより,制約条件を満たした上で,-objを最小化する形になります.
  1. Exhautve Solverを用いた求解
  • Exhaustive Solverを用いて解solを求めたあと,その解に対するxyobjx + Y 3 * x + 5 * yの値を表示します.

実行結果

このQUBO++プログラムを実行すると,以下の出力が得られます.

f = 298*x[0] +1596*x[1] +7192*x[2] +997*y[0] +4594*y[1] +4594*y[2] +300*{0}[0] +1000*{0}[1] +300*{1}[0] +1000*{1}[1] +3600*{1}[2] +9100*{1}[3] +2000*x[0]*x[1] +4000*x[0]*x[2] +1600*x[0]*y[0] +3200*x[0]*y[1] +3200*x[0]*y[2] -200*x[0]*{0}[0] -400*x[0]*{0}[1] -600*x[0]*{1}[0] -1200*x[0]*{1}[1] -2400*x[0]*{1}[2] -3900*x[0]*{1}[3] +8000*x[1]*x[2] +3200*x[1]*y[0] +6400*x[1]*y[1] +6400*x[1]*y[2] -400*x[1]*{0}[0] -800*x[1]*{0}[1] -1200*x[1]*{1}[0] -2400*x[1]*{1}[1] -4800*x[1]*{1}[2] -7800*x[1]*{1}[3] +6400*x[2]*y[0] +12800*x[2]*y[1] +12800*x[2]*y[2] -800*x[2]*{0}[0] -1600*x[2]*{0}[1] -2400*x[2]*{1}[0] -4800*x[2]*{1}[1] -9600*x[2]*{1}[2] -15600*x[2]*{1}[3] +5200*y[0]*y[1] +5200*y[0]*y[2] -200*y[0]*{0}[0] -400*y[0]*{0}[1] -1000*y[0]*{1}[0] -2000*y[0]*{1}[1] -4000*y[0]*{1}[2] -6500*y[0]*{1}[3] +10400*y[1]*y[2] -400*y[1]*{0}[0] -800*y[1]*{0}[1] -2000*y[1]*{1}[0] -4000*y[1]*{1}[1] -8000*y[1]*{1}[2] -13000*y[1]*{1}[3] -400*y[2]*{0}[0] -800*y[2]*{0}[1] -2000*y[2]*{1}[0] -4000*y[2]*{1}[1] -8000*y[2]*{1}[2] -13000*y[2]*{1}[3] +800*{0}[0]*{0}[1] +800*{1}[0]*{1}[1] +1600*{1}[0]*{1}[2] +2600*{1}[0]*{1}[3] +3200*{1}[1]*{1}[2] +5200*{1}[1]*{1}[3] +10400*{1}[2]*{1}[3]
-17:{{x[0],0},{x[1],0},{x[2],1},{y[0],1},{y[1],1},{y[2],0},{{0}[0],1},{{0}[1],1},{{1}[0],1},{{1}[1],1},{{1}[2],1},{{1}[3],1}}
x = 4
y = 3
obj = 17
c1 = 7
c2 = 27
  • QUBO式fにおいて,{0}{1}はスラック変数を表しています.これらは,c1c2の不等式をQUBO式に変換する際に用いられています.
  • QUBO問題の最適解は,x = 4y = 3で,エネルギー値は-17です.
  • 整数計画問題の最適解における目的関数の値は17となります.
  • 制約条件1と2の値はそれぞれ727であり,両方とも条件を満たしています.

おわりに

このように,整数計画問題はQUBO++を用いることで,等価なQUBO式を導出し,その解を求めることが可能です.これにより,QUBO++を整数計画問題のソルバーとして活用することができます.QUBO++はシンプルな記法と柔軟な機能を提供しており,幅広い応用範囲を持つことから,整数計画問題の解決において非常に有用なツールとなるでしょう.

まとめ

  • 範囲比較演算子 <= <=:QUBO++では,「下限値 <= 式 <= 上限値」の形式で範囲比較演算を記述できます.この形式を用いると,範囲比較演算を満たすとき最小値0をとる式を生成します.
  auto c1 = 0 <= x + y <= 7;
  auto c2 = 0 <= 3 * x + 5 * y <= 28;

また,式が一次式であれば,生成される式は二次式となるので,QUBO式となります.

  • 整数計画問題のQUBO化:目的関数を最大化する整数計画問題では,目的関数のQUBO式をobj,制約条件のQUBO式をc1,c2とします.制約条件の優先度を表す整数(例: 100)を用いることで,次のようにQUBO式を構築します.
  auto f = -obj + 100 * (c1 + c2);
  • 解に対する式の値の計算:QUBO問題の解が得られた後,その解に対する変数の値や式の値を得るには,get()関数を使用します.

QUBO++情報

広島大学コンピューティングラボ
設定によりコメント欄が無効化されています