最適化ソルバの一つである Gurobi の使い方について．

はじめに
注意書き
環境構築
- 追記
ライセンスファイルの取得
コンパイル方法について
解きたい問題
プログラム
実行
終わりに

はじめに

これは私が頻繁に最適化ソルバを使うので，方法を忘れないための記事です．多少わかりにくいところ，もしくは使い方を間違っているところがあればぜひ教えてください．

注意書き

本記事を書いた時点で，私のダウンロードしている Gurobi のバージョンは 8.1.1. なので，この記事を参考にしてプログラムを書こうという方は適宜自分のバージョンに置き換えて読んでください．

環境構築

ダウンロード方法はこの記事を参考にすると良いと思います．

Macの場合，先ほどの記事などに従ってダウンロード後，解凍すると

/Library/gurobi811/mac64

というディレクトリができると思います． $GUROBI_HOMEなどの名前をつけておくと便利みたいです．

$ export GUROBI_HOME="/Library/gurobi811/mac64"

さて，C++の環境を構築するために以下を実行します．

$ cd $GUROBI_HOME/src/build
$ sudo make
$ sudo cp gurobi_c++.a $GUROBI_HOME/lib/

これで環境構築は終わりです．

追記

これコピーじゃなくてシンボリックリンクを貼れば十分です，すみません．つまり，最後の行は次の２行で書き換えてください．

$ cd $GUROBI_HOME/lib
$ ln -sf ./../src/build/libgurobi_c++.a libgurobi_c++.a

さらに，ubuntuの場合は次の行を ~/.bashrc に追記しましょう．

export LD_LIBRARY_PATH=$LD_LIBRARY_PATH:$GUROBI_HOME/lib

ちなみにpythonは

$ cd $GUROBI_HOME
$ python setup.py install

で環境構築完了だったと思います．

↓2020/05/02追記

ライセンスファイルの取得

まず，gurobiの公式サイトにアクセスし，ライセンスを取得します．
ライセンスを取得すると，下の方にgrbgetkey XXXXXXXX-XXXX-XXXX-XXXX-XXXXXXXXXXXXを実行してください（XXXXXXXX-XXXX-XXXX-XXXX-XXXXXXXXXXXXは英数字）と書いてあるので実行してみます．しかし，実際コマンドを打つとcommand not foundとなってしまいます．これは次のように対処すればいいです．

$ cd $GUROBI_HOME/bin
$ ./grbgetkey XXXXXXXX-XXXX-XXXX-XXXX-XXXXXXXXXXXX

しばらくすると，ライセンスファイルを置く場所を聞かれるので，置きたい場所を選んでください．これでライセンスファイルの取得は完了です．

コンパイル方法について

外部ライブラリを使う C++のコードはコンパイル時にたくさんのオプションを書かなければなりません．しかし，毎回書くのは大変なので，Makefileを作っておくと良いでしょう．今回の場合は，例えば次のようなMakefileを作れば良いと思います．

CCC = g++ -std=c++14
GUROBI = /Library/gurobi811/mac64
INCLUDE = $(GUROBI)/include
LIBRARY = $(GUROBI)/lib -lgurobi_c++ -lgurobi81

all: exec
  ./exec
exec: main.cpp
  $(CCC) -o exec main.cpp -I$(INCLUDE) -L$(LIBRARY)

これさえ作っておけば，コンパイル→実行は

$ make

だけなので楽チンですね．

解きたい問題

次式で定義される行列 $A \in \mathbb{R}^{2 \times 2}$ ，ベクトル $b \in \mathbb{R}^{2}$

$A = \begin{pmatrix} -1 & 2 \\ 0 & 1 \\ \end{pmatrix}, \quad b = \begin{pmatrix} 0 \\ 6 \end{pmatrix}$

を用いて，次のような最適化問題を考えます．

$\min \left\{ (x_{1} - 3)^2 + (x_{2} - 4)^2 \mid A x \leq b, x_{1} \geq 0, x_{2} \geq 0 \right\}$

この問題の最適値は $5$ で，最適解は

$x = \begin{pmatrix} x_{1} \\ x_{2} \end{pmatrix} = \begin{pmatrix} 4 \\ 2 \end{pmatrix}$

です．これらを求めるプログラムを書いてみようと思います．

プログラム

例えば，次のように書けます．

#include <iostream>
#include <gurobi_c++.h>

int main() {
    // 環境の宣言
    GRBEnv   env   = GRBEnv();
    // モデルの宣言
    GRBModel model = GRBModel( env );
    // 変数の宣言
    GRBVar   x1, x2;

    // 制約式の追加
    // 線形の式 → GRBLinExpr
    // 二次の式 → GRBQuadExpr
    GRBLinExpr  constraint_1 = 0.0; // -x + 2y <= 0 の制約式の左辺を格納する変数
    GRBLinExpr  constraint_2 = 0.0; // x       <= 6 の制約式の左辺を格納する変数
    GRBQuadExpr objective_function;  // 目的関数 x^2 + y^2 の式を格納する変数

    model.set( GRB_IntParam_OutputFlag, 0 ); // コンソールへの出力をなくす
    
    // 変数をモデルに追加
    //                 下界,         上界,  初期値,  変数の型（今回は連続値)
    x1 = model.addVar( 0.0, GRB_INFINITY,   0.0,   GRB_CONTINUOUS );
    x2 = model.addVar( 0.0, GRB_INFINITY,   0.0,   GRB_CONTINUOUS );
    model.update(); // モデルの更新

    // 制約式の追加
    constraint_1 = - x1 + 2*x2;
    model.addConstr( constraint_1 <= 0 );

    constraint_2 = x1;
    model.addConstr( constraint_2 <= 6 );
    model.update(); // モデルの更新

    // 目的関数の設定
    objective_function = (x1 - 3) * (x1 - 3) + (x2 - 4) * (x2 - 4);
    model.setObjective( objective_function, GRB_MINIMIZE );
    model.update(); // モデルの更新

    // ソルバに解いてもらう
    model.optimize();

    // 最適値の出力
    std::cout << "Optimal Value : " << model.get( GRB_DoubleAttr_ObjVal ) << '\n';

    // 最適解の出力
    std::cout << "Optimal Solution\n"
              << "\t x1 = " << x1.get( GRB_DoubleAttr_X ) << '\n'
              << "\t x2 = " << x2.get( GRB_DoubleAttr_X ) << std::endl;

    return 0;
}

解きたい問題が最大化問題である場合，model.setObjective( objective_function, GRB_MAXIMIZE ); と書きます．また，今回は制約が2つ（ $A$ の行数が2）だったので制約をconstraint_1, constraint_2のように別々に宣言しましたが，制約がたくさんある場合は

#include <vector>
size_t number_of_constraints;
std::vector< GRBLinExpr > constraints( number_of_constraints, 0.0 );

のように，std::vector型で宣言すると良いかもしれません．

実行

先ほどのプログラムをmain.cppという名前で保存し，同じディレクトリ内にMakefileも用意します．あとは，makeコマンドで結果が得られます．

$ make
g++ -std=c++14 -o exec main.cpp -I/Library/gurobi811/mac64/include -L/Library/gurobi811/mac64/lib -lgurobi_c++ -lgurobi81
./exec
Academic license - for non-commercial use only
Optimal Value : 5
Optimal Solution
     x1 = 4
     x2 = 2

応用すれば様々な問題が解けるので楽しいですね！

終わりに

最適化ソルバの使い方は公式サイトに書いてあります．しかし，英語の記事を読むのは私にとって大変ですのでもっと日本語の記事が欲しいなあと思っています．．

学習理論の学習

統計的学習理論を学習してるときに思ったこととか

Gurobi の使い方(C++)