分枝限定法における計算過程の可視化 [in Japanese] Visualization of Runtime Behavior of Branch-and-Bound Algorithms [in Japanese]
Search this Article
Author(s)
Abstract
分枝限定法を用いて整数計画問題を解く際に,どのような分枝戦略を選択するかは重要な問題である.分枝戦略の良し悪しは,生成される子問題の数,分枝限定木の深さ,総計算時間などに大きな影響を与える.しかしながら,大規模な数理計画問題では,分枝限定木の生成プロセスにおける出力は大量のログデータとなってしまい,それぞれの分枝戦略がどのように影響を与えているのか直感的な把握が難しい.そこで本研究では,分枝限定木の生長過程を可視化するシステムを提案する.本システムにより,分枝戦略の違いが子問題の生成過程に及ぼす影響を視覚的に捉えることができる.
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.
Journal
-
- IPSJ SIG Notes
-
IPSJ SIG Notes 58, 27-30, 2006-03-16
Information Processing Society of Japan (IPSJ)