Instance15 解析ツール

 ログ解析用ソフトを制作しました。ログを読み込んでBranchTreeを作ります。

"""

ブランチログから Branch Tree を DOT 形式で出力するスクリプト

対象行:

  <cpu>(cpu sec)  Selecting Child Node id=0: Br:De:d N:n D:day S:shift Dir:dir Obj:obj [Gain:g]

  Adding Node thr=0 Br:De:d N:n D:day S:shift Dir:dir Obj:obj [Gain:g]

木の組み立て規則:

  - Selecting (De:0) が ROOT ノード。

  - Adding Node は「直前に Selecting されたノード」の子として登録（未探索ノード）。

  - Selecting は、同じ (De,N,D,S,Dir) で Adding 済みのノードがあればそれを探索済みにする

    （バックトラック時もこれで正しい親につながる）。

    無ければ新規ノードを作り、直前に Selecting されたノード（深さ De-1）の子にする。

    深さが合わない場合は、深さ De-1 で最後に Selecting されたノードを親にする。

使い方:

  python branch_tree_to_dot.py instance15_log_simplified.txt

  python branch_tree_to_dot.py log.txt -o tree.dot --render svg --rankdir LR

  python branch_tree_to_dot.py log.txt --max-depth 20     # 深さ20以下のみ表示

"""

Selecting以下を読み込んでBranchTreeをDOT形式で出力します。

全部をDrawする画像化は無理なので、Depthを制限して表示しています。

これで、何が嬉しいかというと、BranchTreeの様子を視覚的に確認できる、のでボトルネックを把握しやすくなる、ということになります。

Instance15に関しては、厳密解の証明のためには、現開発中のソルバでも一週間ほどかかります。これをなんとか短くする方法を思案するのに、有効なツールです。

解収束の様子は、下図になります。

Instance15は、昨年、菅原システムズによって厳密解が示されるまで、十余年に渡って厳密解が知られていなかったインスタンスになります。それでも、3分程でLB-UBGapが1%程度の実用解に達していることが分かります。