Hi-QUBO

整数線形計画法 (ILP)

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

\[\begin{aligned} \text{最大化:} && 2x_0 +5x_1+5x_2\\ \text{制約条件:} && x_0 + 3 x_1 + x_2 &\leq 12 \\ && x_0 + 2x_2 &\leq 5\\ && x_1 + x_2 &\leq 4; \end{aligned}\]

QUBO++プログラム

以下のQUBO++プログラムは、この整数線形計画問題をQUBO式として定式化し、Easy Solverを用いて解きます：

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

int main() {
  auto x = 0 <= qbpp::var_int("x", 3) <= 5;
  auto objective = 2 * x[0] + 5 * x[1] + 5 * x[2];
  auto c1 = 0 <= x[0] + 3 * x[1] + x[2] <= 12;
  auto c2 = 0 <= x[0] + 2 * x[2] <= 5;
  auto c3 = 0 <= x[1] + x[2] <= 4;

  auto f = -objective + 100 * (c1 + c2 + c3);
  f.simplify_as_binary();
  auto solver = qbpp::easy_solver::EasySolver(f);
  solver.time_limit(1.0);
  auto sol = solver.search();
  std::cout << "x0 = " << sol(x[0]) << ", x1 = " << sol(x[1])
            << ", x2 = " << sol(x[2]) << std::endl;
  std::cout << "objective = " << sol(objective) << std::endl;
  std::cout << "*c1 = " << sol(*c1) << ", *c2 = " << sol(*c2)
            << ", *c3 = " << sol(*c3) << std::endl;
}

このプログラムでは、 x は3つのオブジェクトからなるベクトルであり、 qbpp::VarInt オブジェクトのベクトルであり、各オブジェクトは整数値 $[0, 5]$ の範囲を取る。 目的関数と3つの制約は objective, c1, c2、および c3でそれぞれ表される。 これらは単一のQUBO式 fに統合され、ペナルティ定数 100 は制約を強制するために用いられる。

Easy Solver は f を求め、それを solとして返す。 得られた解と objective, *c1, *c2、および *c3 は以下の通り出力される：

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

目的関数24で得られた解は全ての制約を満たしていることが確認できる。

最終更新日: 2026.01.08