はじめに

この記事では, Gurobi Optimizer が出力するログファイルの集計に便利な gurobi-logtools の紹介をします.

gurobi-logtools とは

Gurobi Optimizer (以下 Gurobi) は線形計画問題や整数計画問題などを解く数理最適化ソルバーで, 性能が高いソルバーの一つとして知られています. gurobi-logtools は Gurobi の開発元が提供する Python のパッケージで, gurobi-logtools を用いると Gurobi が出力したログファイルを簡単に解析できるようになります.

https://github.com/Gurobi/gurobi-logtools

Gurobi を用いて最適化問題を解くと, 最適化計算の過程をまとめたログとして以下のようなログファイルが出力されます:

Gurobi 8.1.1 (win64) logging started 08/06/20 10:18:44

   Prev: gurobi.log  Default: 
Changed value of parameter NumericFocus to 3
   Prev: 0  Min: 0  Max: 3  Default: 0
Changed value of parameter TIME_LIMIT to 3600.0
   Prev: 1e+100  Min: 0.0  Max: 1e+100  Default: 1e+100
Optimize a model with 66 rows, 157 columns and 312 nonzeros
Model has 31 quadratic constraints
Variable types: 126 continuous, 31 integer (31 binary)
Coefficient statistics:
  Matrix range     [2e-03, 1e+00]
  QMatrix range    [1e+00, 1e+00]
  Objective range  [3e-01, 1e+01]
  Bounds range     [5e-01, 1e+00]
  RHS range        [5e-01, 1e+01]
Presolve time: 0.00s
Presolved: 66 rows, 157 columns, 310 nonzeros
Variable types: 126 continuous, 31 integer (31 binary)

Root relaxation: objective -1.006647e+00, 12 iterations, 0.00 seconds

    Nodes    |    Current Node    |     Objective Bounds      |     Work
 Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time

     0     0   -0.74612    0    2          -   -0.74612      -     -    0s
     0     2    0.38890    0    2          -    0.38890      -     -    0s
  2852   908    5.05303   12    -          -    3.92220      -  18.4    5s
  3299  1051    5.26371   12    -          -    4.06971      -  19.1   10s
  3651  1154    5.30049   12    -          -    4.13508      -  19.5   15s
* 3916  1184              14       5.0450732    4.15820  17.6%  19.6   19s
* 3927   838              14       4.7177473    4.15820  11.9%  19.6   19s
  3970   823    4.58074   12    2    4.71775    4.16111  11.8%  19.6   20s
  4547   776    4.31394    1    -    4.71775    4.31394  8.56%  21.7   25s
  5014   793    4.64626   17    -    4.71775    4.31429  8.55%  22.8   30s
  5478   832    4.68725   16    -    4.71775    4.31439  8.55%  23.6   35s
  6022   928    4.69043   17    -    4.71775    4.31443  8.55%  24.3   40s
  6427   984    4.69057   17    -    4.71775    4.31446  8.55%  24.8   45s
  6770  1037    4.69250   17    -    4.71775    4.31447  8.55%  25.2   50s
* 6828    10               1       4.3144657    4.31447  0.00%  25.3   50s

Cutting planes:
  Lazy constraints: 1388

Explored 6887 nodes (174387 simplex iterations) in 50.96 seconds
Thread count was 8 (of 8 available processors)

Solution count 3: 4.31447 4.71775 5.04507 

Optimal solution found (tolerance 1.00e-04)
Warning: max constraint violation (3.8026e-06) exceeds tolerance
Best objective 4.314465707439e+00, best bound 4.314465707439e+00, gap 0.0000%

こちらのログファイルはテキスト形式で出力され, このファイルから Gurobi における最適化計算の過程に関する様々な情報を得ることができます. 個別の問題例に対する計算結果を知りたい場合はこのファイルを一つ一つ見ればよいのですが, 計算結果を集計する, 複数のログファイルを比較するといった場合, このようなテキストファイルは少々扱いづらいです.

ここで gurobi-logtools はログファイルの parser を提供していて, テキストファイルにまとまっている情報を pandas のデータフレーム形式に変換します. これによりログの集計作業を pandas で簡単に行うことができるようになります. また gurobi-logtools では Plotly を用いたグラフ作図機能も提供しているため, 複数のログファイルの計算結果を視覚的に比較することなども簡単にできるようになります.

gurobi-logtools を用いた上下界の推移の可視化

ここでは gurobi-logtools を用いた実装例として, 分枝限定法における上下界の推移を可視化するプログラムを紹介します. gurobi-logtools のインストール方法は公式のページの readme に記載があるので, そちらを参考にしてください.

以下, gurobi-logtools のデモ用のログファイル 912-Cuts0-Heuristics0-glass4-0.log を対象として, gurobi-logtools の実装例を示します.

使用したログファイル: https://github.com/Gurobi/gurobi-logtools/blob/master/data/912-Cuts0-Heuristics0-glass4-0.log

import gurobi_logtools as glt
import matplotlib.pyplot as plt

results = glt.parse("912-Cuts0-Heuristics0-glass4-0.log")
node_log = results.progress("nodelog")

plt.figure(figsize=(18, 4))
plt.plot(node_log["Time"], node_log["Incumbent"], label="Incumbent", marker='o')
plt.plot(node_log["Time"], node_log["BestBd"], label="BestBd", marker='x')

plt.xlabel("Runtime")
plt.ylabel("Objective function value")
plt.legend()
plt.show()

こちらを実行すると以下のようなグラフが出力されます:

このグラフは横軸が実行時間を表し, 縦軸が目的関数値を表します. Incumbent は各時刻における最適値の上界 (暫定最適解の目的関数値) を表し, Bestbd は最適値の下界を表します. 時間を経ると最適値の上界と下界が近づき, それらが十分近くなった段階で暫定最適解の最適性が確認されたことになり計算が終了しています.

もうすこし詳しく

上で述べたプログラムでは

results = glt.parse("912-Cuts0-Heuristics0-glass4-0.log")

という部分でログファイルの parse を行っています. gurobi-logtools の parse() という関数が parse を実行する関数であり, 引数としてログファイルのファイル名を指定すると対象のファイルを parse した結果をまとめたインスタンスが出力されます. なお, parse() の引数にファイル名をまとめたリストを指定すると, 複数のログファイルを一度に parse することができます.

次の行

node_log = results.progress("nodelog")

では, ログファイルの中に含まれる情報のうち, 分枝限定法の過程に関する情報をデータフレーム形式で取得しています.

node_log はデータフレーム形式のオブジェクトであり, その中身を出力してみると,

といった具合になります. このデータフレームでは分枝限定法における各種指標の推移をまとめていて, Time が経過時間, Incumbent, BestBd がそれぞれ最適値に関する上界と下界を表しています.

それ以外の列が何を表しているかを知りたい場合は Gurobi の公式のページを見てください.

https://www.gurobi.com/documentation/current/refman/mip_logging.html

今回の実行例では分枝限定法の実行過程の情報を取得しました. 実行結果全体の概要を知りたい場合は summary() メソッドを用いて,

summary = results.summary()

とすると, 一回の実行結果全体をまとめたデータフレームが取得できます. ちなみに summary の中身をプリントすると

というような感じになっています. このデータフレームの各列では, 実行結果やソルバーの設定に関するパラメータも格納されています.

今回は一つのログファイルだけを読み込んだため summary は 1 行のデータフレームとなっていますが, 複数のログファイルを読み込んだときはそのファイル数分の行からなるデータフレームになります. 複数ファイルをまとめて集計したい場合は, summary() メソッドを用いるとよいと便利だと思われます.

おわりに

この記事では gurobi-logtools の使い方として, 実行例の一つを示しました. 今回は限られた使い方しか紹介しておらず, gurobi-logtools はそれ以外にも様々な機能を提供しています. 機能の詳細を知り合い場合は, パッケージの Readme や, Gurobi の解説動画などを参照するとよいでしょう.

パッケージのリポジトリ: https://github.com/Gurobi/gurobi-logtools
解説動画: https://www.youtube.com/watch?v=wbg4Zr_A1s8