Gurobi Optimizer の使用方法

QUBO++ は、Gurobi Optimizer を使用して QUBO 式を解くことができます。 Gurobi Optimizer を使用するには、有効な Gurobi ライセンスが必要です。

Gurobi Optimizer を使用した問題の解決には、以下の 3 つのステップがあります。

Gurobiモデルオブジェクトを作成します（例：qbpp::grb::QuboModel）。
Gurobiモデルオブジェクトのメンバ関数を呼び出してソルバーオプションを設定する。
メンバー関数 optimize()を呼び出して解を検索します。これにより解（ qbpp::Sol オブジェクト）を返します。

Gurobiモデルオブジェクトの作成

Gurobi Optimizerを使用するには、式(qbpp::grb::QuboModelqbpp::Expr）を用いて以下のように構築します：

qbpp::grb::QuboModel(const qbpp::Expr& f)

ここで、 f は解くべき式である。

Gurobi オプションの設定

作成済みのGurobiモデルオブジェクトに対して、以下のメンバ関数を使用してソルバーオプションを指定できます：

set(key, val): key で指定された Gurobi パラメータを val に設定します。 key と val は両方とも文字列でなければなりません。
time_limit(time_limit): 秒単位の時間制限を設定します。内部的には、以下の関数を呼び出します: set("TimeLimit", std::to_string(time_limit)).

利用可能なパラメータの完全なリストについては、以下のGurobiドキュメントを参照してください： https://docs.gurobi.com/projects/optimizer/en/current/reference/parameters.html

解の探索

Gurobi Optimizer は、Gurobi モデルオブジェクトのメンバoptimize()関数を呼び出して解を検索します。関数 optimize() 関数は解オブジェクトを返します。これは qbpp::Solの派生クラスです。メンバ関数は、最適化中に得られたbound()最良の境界を返します。

サンプルプログラム

以下のプログラムは、Gurobi Optimizer を使用して分割問題の解を検索します：

#include "qbpp.hpp"
#include "qbpp_grb.hpp"

int main() {
  std::vector<uint32_t> w = {64, 27, 47, 74, 12, 83, 63, 40};
  auto x = qbpp::var("x", w.size());
  auto p = qbpp::expr();
  auto q = qbpp::expr();
  for (size_t i = 0; i < w.size(); ++i) {
    p += w[i] * x[i];
    q += w[i] * (1 - x[i]);
  }
  auto f = qbpp::sqr(p - q);
  f.simplify_as_binary();
  auto model = qbpp::grb::QuboModel(f);
  model.time_limit(10.0);
  auto sol = model.optimize();
  std::cout << "Solution: " << sol << std::endl;
  std::cout << "Bound = " << sol.bound() << std::endl;
  std::cout << "f(sol) = " << f(sol) << std::endl;
  std::cout << "p(sol) = " << p(sol) << std::endl;
  std::cout << "q(sol) = " << q(sol) << std::endl;
  std::cout << "P :";
  for (size_t i = 0; i < w.size(); ++i) {
    if (x[i](sol) == 1) {
      std::cout << " " << w[i];
    }
  }
  std::cout << std::endl;
  std::cout << "Q :";
  for (size_t i = 0; i < w.size(); ++i) {
    if (x[i](sol) == 0) {
      std::cout << " " << w[i];
    }
  }
  std::cout << std::endl;
}

まず、このプログラムは式 fを表現するGurobiモデルを作成します。時間制限を10.0秒に設定し、その後 optimize() が呼び出されます。得られた解は sol.

このプログラムは以下の出力を生成します:

Solution: 0:{{x[0],1},{x[1],1},{x[2],0},{x[3],1},{x[4],0},{x[5],0},{x[6],0},{x[7],1}}
Bound = 0
f(sol) = 0
p(sol) = 205
q(sol) = 205
P : 64 27 74 40
Q : 47 12 83 63

解の値と境界値が同じエネルギー0を持つため得られた解は最適解であることが保証されます。

最終更新日: 2026.01.12