整数線形計画法（ILP）¶

**整数線形計画法（ILP）**は,Hi-QUBOを用いてQUBO式に変換できます. 例として,以下のILPを考えます:

\[\begin{split} \begin{aligned} \text{Maximize:} && 2x_0 +5x_1+5x_2\\ \text{Subject to:} && x_0 + 3 x_1 + x_2 &\leq 12 \\ && x_0 + 2x_2 &\leq 5\\ && x_1 + x_2 &\leq 4; \end{aligned} \end{split}\]

Hi-QUBOプログラム

以下のHi-QUBOプログラムは,このILPをQUBO式として定式化し,Easy Solver を使って解きます:

range-constraints-and-ilp-program1.cpp¶

#include <qbpp/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::EasySolver(g);
  auto sol = solver.search({{"time_limit", 1.0}});
  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.body(sol) = " << c1.body(sol) << ", c2.body(sol) = " << c2.body(sol) << std::endl;
}

このプログラムでは,x は3つの整数変数のベクトルであり,それぞれ \([0, 5]\) の範囲の整数値をとります. 目的関数と3つの制約は,それぞれ objective,c1,c2,c3 で表されます. これらはペナルティ定数 100 を用いて制約を強制する1つのQUBO式 f にまとめられます.

Easy Solver は f の低エネルギー解を探索し,sol として返します. 得られた解と objective,および各制約の body（c1.body(sol),c2.body(sol),c3.body(sol)）の値は以下のように出力されます:

x0 = 2, x1 = 3, x2 = 1
objective = 24
c1.body(sol) = 12, c2.body(sol) = 4, c3.body(sol) = 4

目的関数値24の解が得られ,すべての制約が満たされていることが確認できます.

整数線形計画法（ILP） は,PyQBPPを使用してQUBO式に変換できます. 例として,以下のILPを考えます:

\[\begin{split} \begin{aligned} \text{Maximize:} && 2x_0 +5x_1+5x_2\\ \text{Subject to:} && x_0 + 3 x_1 + x_2 &\leq 12 \\ && x_0 + 2x_2 &\leq 5\\ && x_1 + x_2 &\leq 4; \end{aligned} \end{split}\]

PyQBPPプログラム

以下のPyQBPPプログラムは,このILPをQUBO式として定式化し,Easy Solver を使って解きます:

range-constraints-and-ilp-program1.py¶

import pyqbpp as qbpp

x = qbpp.var("x", between=(0, 10))
y = qbpp.var("y", between=(0, 10))
f = 5 * x + 4 * y
c1 = qbpp.constrain(2 * x + 3 * y, between=(0, 24))
c2 = qbpp.constrain(7 * x + 5 * y, between=(0, 54))
g = -f + 100 * (c1 + c2)
g.simplify_as_binary()

solver = qbpp.EasySolver(g)
sol = solver.search(time_limit=1.0)

print(f"x = {sol(x)}, y = {sol(y)}")
print(f"f = {sol(f)}")
print(f"c1 = {sol(c1)}, c2 = {sol(c2)}")
print(f"2x+3y = {sol(c1.body)}, 7x+5y = {sol(c2.body)}")

Easy Solver は f の低エネルギー解を探索し,sol として返します. 得られた解と objective,c1.body,c2.body,c3.body の値は以下のように出力されます:

x0 = 2, x1 = 3, x2 = 1
objective = 24
c1 = 12, c2 = 4, c3 = 4

目的関数値24の解が得られ,すべての制約が満たされていることが確認できます.