分枝限定法における分枝戦略選択のための計算過程の可視化

Visualization of runtime behavior of branch-and-bound algorithms

宮村 浩子  ; 品野 勇治*; 宮代 隆平*; 斎藤 隆文*

Miyamura, Hiroko; Shinano, Yuji*; Miyashiro, Ryuhei*; Saito, Takafumi*

分枝限定法を用いて整数計画問題を解く際に、どのような分枝戦略を選択するかは重要な問題である。分枝戦略の良し悪しは、生成される子問題の数,分枝限定木の深さ,総計算時間などに大きな影響を与える。しかしながら、大規模な数理計画問題では、分枝限定木の生成過程における出力は大量のログデータとなってしまい、それぞれの分枝戦略がどのように影響を与えているのか直感的な把握が難しい。そこで本研究では、分枝限定木の生長過程を可視化するシステムを提案する。本システムにより、分枝戦略の違いが子問題の生成過程に及ぼす影響を視覚的に捉えることができる。

In branch-and-bound algorithms for integer programming, runtime behavior of the algorithms depends much on branching strategy. However, from a huge computation log of a large program, it is difficult to explore a key factor for effective branching. To analyze which factor of branching strategy is essential, we develop a system for visualization of growing process of a large branch-and-bound tree. The proposed system provides intuitive understanding how branching strategy affects branch-and-bound process.