第 250 回 PTT のお知らせ

日時: 1999年 6月17日(木) 18:30 から
場所: 東京農工大学 工学部 情報コミュニケーション工学科 7号棟 1階 1E 室 




話者： 品野 勇治 (農工大・情報コミュニケーション工学科)




題目： 汎用並列分枝限定法ツールPUBBによる組合せ最適化問題の厳密解法




概要：

分枝限定法は,組合せ最適化問題に対する代表的な厳密解法である.この解
法は列挙法であり,与えられた問題をいくつかの子問題に分割して解いていく.
列挙過程では,各子問題において解くべき問題の構造を利用した評価計算を行
い,不要な列挙を避けることで計算時間を短縮している.分枝限定法における各
子問題での評価計算は,ほぼ独立して行えるため,並列処理に適している.また,
分枝限定法は汎用的な計算原理であり,特定の問題に依存しない.  そこで,汎
用の並列分枝限定法ツールPUBB(Parallelization Utility for
Branch-and-Bound algorithms)を開発した. PUBB は PVM を利用して,並列分
枝限定法を実現する.

 

分枝限定法は汎用ではあるが,特定の問題に対する解法の並列化を考える立
場からは,以下を考慮する必要がある.



    
  
  1.  評価計算に多くの時間を費やすことで,最終的に生成される子問題数を
       少なくする解法
  
  2.  短時間の評価計算により,最終的に生成される子問題数を多くした方が,
       全体としての計算時間が短くなる解法




本発表では,PUBBを紹介するとともに,(1)(2)の解法に対してPUBBを適用し
た結果について報告する.









第 250 回 PTTメモ





日時: 


場所: 


題目:


話者: 



出席者: 
山内斉,
鈴木貢,
中山泰一,
新藤雅也,
佐藤信弘,
佐藤喬,
兵藤和樹(電通大),
田村智洋,
金子敬一,
毛利公一,
斎藤隆文,
草部博輝,
水野徹平,
澤田圭,
鈴木透,
瀬川大勝(農工大),
宮代隆平(東大),
下國治(川崎市)        




質疑応答:



会場ではPC4台により,並列分枝限定法によって生成される探索木をリアル
タイムに表示するデモが行われた.