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

IPSJ Web Site

Bibliographic Information

Other Title
  • フン シ ゲンテイホウ ニ オケル フン シ センリャク センタク ノ タメ ノ ケイサン カテイ ノ カシカ
  • Visualization of Runtime Behavior of Branch-and-bound Algorithms

Search this article

Abstract

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

In branch-and-bound algorithms for integer programming, runtime behavior of the algorithms depends much on its branching strategy. However, from a huge computation log of a large program, it is difficult to explore key factors 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

Related Projects

See more

Keywords

Details 詳細情報について

Report a problem

Back to top