はじめに
この記事では, Gurobi Optimizer が出力するログファイルの集計に便利な gurobi-logtools の紹介をします.
gurobi-logtools とは
Gurobi Optimizer (以下 Gurobi) は線形計画問題や整数計画問題などを解く数理最適化ソルバーで, 性能が高いソルバーの一つとして知られています. gurobi-logtools は Gurobi の開発元が提供する Python のパッケージ で, gurobi-logtools を用いると Gurobi が出力したログファイルを簡単に解析できるようになります.
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 の公式のページを見てください.
今回の実行例では分枝限定法の実行過程の情報を取得しました. 実行結果全体の概要を知りたい場合は summary() メソッドを用いて,
summary = results.summary()
とすると, 一回の実行結果全体をまとめたデータフレームが取得できます. ちなみに summary の中身をプリントすると
というような感じになっています. このデータフレームの各列では, 実行結果やソルバーの設定に関するパラメータも格納されています.
今回は一つのログファイルだけを読み込んだため summary は 1 行のデータフレームとなっていますが, 複数のログファイルを読み込んだときはそのファイル数分の行からなるデータフレームになります. 複数ファイルをまとめて集計したい場合は, summary() メソッドを用いるとよいと便利だと思われます.
おわりに
この記事では gurobi-logtools の使い方として, 実行例の一つを示しました. 今回は限られた使い方しか紹介しておらず, gurobi-logtools はそれ以外にも様々な機能を提供しています. 機能の詳細を知り合い場合は, パッケージの Readme や, Gurobi の解説動画などを参照するとよいでしょう.