2024-03-29T08:53:28Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:000331662023-04-27T10:00:04Z01164:02735:02748:02753
分枝限定法における計算過程の可視化Visualization of Runtime Behavior of Branch-and-Bound Algorithmsjpnhttp://id.nii.ac.jp/1001/00033166/Technical Reporthttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=33166&item_no=1&attribute_id=1&file_no=1Copyright (c) 2006 by the Information Processing Society of Japan東京農工大学東京農工大学東京農工大学東京農工大学東京農工大学宮村(中村), 浩子宮代, 隆平中山, 知樹品野, 勇治斎藤, 隆文分枝限定法を用いて整数計画問題を解く際に,どのような分枝戦略を選択するかは重要な問題である.分枝戦略の良し悪しは,生成される子問題の数,分枝限定木の深さ,総計算時間などに大きな影響を与える.しかしながら,大規模な数理計画問題では,分枝限定木の生成プロセスにおける出力は大量のログデータとなってしまい,それぞれの分枝戦略がどのように影響を与えているのか直感的な把握が難しい.そこで本研究では,分枝限定木の生長過程を可視化するシステムを提案する.本システムにより,分枝戦略の違いが子問題の生成過程に及ぼす影響を視覚的に捉えることができる.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.AN10505667情報処理学会研究報告数理モデル化と問題解決(MPS)200629(2006-MPS-058)27302006-03-162009-06-30