バージョン管理された人

subversionで管理されてます

Gurobi+C++

Gurobi C++ 最適化 C++14

やりたいこと

最適化問題

\displaystyle \min_{\boldsymbol{x} \in \mathbb{R}^n}\{\boldsymbol{c}^T \boldsymbol{x} : A \boldsymbol{x} = \boldsymbol{b}, \boldsymbol{x}^T \boldsymbol{x} \geq d, \boldsymbol{x} \geq \boldsymbol{0}\}

をGurobiに解かせる。 ホスト言語はC++14。 なお、ここでは

  • A \in \mathbb{R}^{5 \times 10}
  • \boldsymbol{b}, \boldsymbol{c} \in \mathbb{R}^{10}

であることに注意。

やり方

まずはgurobi_c++.hと、(例のために)vector、randomをインクルード。

#include <gurobi_c++.h>
#include <vector>
#include <random> // インタンスを乱数で用意するため

そしてGRBEnvとGRBModelを用意。

auto env = new GRBEnv{};
auto model = new GRBModel{*env};

そして変数追加。

auto x = std::vector<GRBVar>{};

for (auto i = 0; i < 10; i++) {
  x.push_back(
    model->addVar(
      0,             // 下限
      GRB_INFINITY,  // 上限
      1,             // 初期値
      GRB_CONTINUOUS // 変数のタイプ
    )
  );
}

タイプには表のものを指定できる。

範囲 使用する定数
連続 GRB_CONTINUOUS
バイナリ GRB_BINARY
整数 GRB_INTEGER

終わったらモデルを更新。

model->update();

必要な制約を追加していく。

auto seed_gen1 = std::random_device{};
auto mt1 = std::mt19937{seed_gen1()};
auto a_dist = std::uniform_real_distribution<>{-10000, 10000};
auto b_dist = std::uniform_real_distribution<>{-1000, 1000};
auto d_dist = std::uniform_real_distribution<>{100, 10000};

for (auto i = 0; i < 5; i++) {
  GRBQuadExpr constr = 0.0;
  for (auto& ex : x) {
    constr += a_dist(mt1) * ex;
  }
  model->addConstr(constr == b_dist(mt1)); // 線形制約追加
}

GRBQuadExpr constr = 0.0;
for (auto& ex: x) {
  constr += ex * ex;
}
model->addConstr(constr >= d_dist(mt1));

制約を追加したらモデルを更新。

model->update();

最後に目的関数を作成してセット。

GRBQuadExpr objective = 0.0;
auto seed_gen2 = std::random_device{};
auto mt2 = std::mt19937{seed_gen2};
auto c_dist = std::unifrom_real_distribution<>{-1000, 1000};

for (auto* ex : x) {
  objective += c_dist(mt2) * ex;
}
model->setObjective(objective, GRB_MINIMIZE)

ここでは最小化問題を扱っているので、GRB_MINIMIZEを指定しているが、最大化したければ、GRB_MAXIMIZE`を指定する。 最後に更新。

model->update();

そして最後に解く。

model->optimize();

解いた後に

解いたあとに最適解が得られているのかどうなのかは

model->get(GRB_IntAttr_Status);

の返り値でわかる。最適解が出ていればGRB_OPTIMALが返る。

目的関数値が欲しけば、

model->get(GRB_DoubleAttr_ObjVal);

とすればよい。

最後にアロケートしたメモリを解放。

delete mode;
delete env;

model->envの順番でなければ例外が飛ぶ。

コンパイル

GUROBI_HOMEを設定しておいていることを仮定している。 Mac+Gurobi 8.0.1なら/Library/gurobi801/mac64。 もし、設定していないなら(bash系列であれば)

$ export GUROBI_HOME=/Library/gurobi801/mac64

とかしておくこと。 コンパイル自体は次のコマンドでできる(ファイル名はmain.ccにしている)。

$ clang -std=c++14 -Wall -pedantic -L"$GUROBI_HOME/lib" -I"$GUROBI_HOME/include" -lgurobi80 -lgurobi_c++ main.cc

Tips