QUBO++入門:比較演算子(整数計画法)
QUBO++の比較演算子
QUBO++では,以下の2種類の比較演算子をサポートしています.
-
等価演算子 ==
式 == 整数の形式を指定します.この演算子は,条件が成立する場合に最小値0を,成立しない場合に1以上を返す式を生成します. -
範囲比較演算子 <=<=
下限整数 <= 式 <= 上限整数の形式を指定します.同様に,条件が成立する場合は最小値0,成立しない場合は1以上を返す式を生成します.
等価演算子==
式を
この式は,
範囲比較演算子 <=<=
式を
-
の場合 :n = 0 となるため,以下の式を返します.l = u
-
の場合:以下のQUBO式を返します.n = 1
この式は,
-
の場合:スラック変数n \geq 2 を導入し,a となるよう設定します.以下の式を返します.a \in [l, u-1]
スラック変数
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に調整
このように構成されたスラック変数
整数計画問題
範囲比較演算子を用いることで,整数計画問題を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++では,整数変数を用いて
これらの計算結果から,以下の範囲が得られます.
このようにして,
整数計画問題を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;
}
コードの説明
-
整数変数の生成
整数変数x
とy
をそれぞれ と[0,7] の範囲で生成しています.[0,5] -
目的関数の定期
QUBO式objに目的関数を生成しています. -
制約条件の生成
制約条件1と2をそれぞれQUBO式c1
とc2
として生成しています. -
QUBO式の構築
最終的なQUBO式f
は,以下のように構築されています.
-
-obj
は目的関数の最大化を最小化問題に変換するための項です. - 制約条件
c1
とc2
は,条件を満たすことを優先させるために100倍の重みを付けています.
これにより,制約条件を満たした上で,-obj
を最小化する形になります.
- Exhautve Solverを用いた求解
- Exhaustive Solverを用いて解
sol
を求めたあと,その解に対するx
,y
,obj
,x + 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}
はスラック変数を表しています.これらは,c1
とc2
の不等式をQUBO式に変換する際に用いられています. - QUBO問題の最適解は,
,x = 4 で,エネルギー値はy = 3 です.-17 - 整数計画問題の最適解における目的関数の値は
となります.17 - 制約条件1と2の値はそれぞれ
と7 であり,両方とも条件を満たしています.27
おわりに
このように,整数計画問題は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++情報
- QUBO++ツールとABS2 QUBO Solverの詳細情報:QUBO++に関する公式サイトです.ツールの特徴や使用方法,ABS2 QUBO Solverとの連携について詳しく説明されています.
- 【研究成果】組合せ最適化問題を解くためのプログラミング用ツールQUBO++を無償公開します:広島大学からの公式リリース情報です.QUBO++の開発背景や研究成果について記載されています.
- 利用条件:QUBO++は非商用利用や評価研究目的に限り無償で利用可能です.商用利用や定常的な業務での使用を希望する場合は,ライセンス契約が必要となります.