マス・フォア・インダストリ研究所

セミナー



リスト 全て(掲示受付分)(1730) 今日・明日のセミナー(0)

整数計画ソルバ,および,並列分枝限定法ソルバの性能評価について


開催時期 2020-02-05 11:00~2020-02-05 12:00

場所 九州大学 伊都キャンパス ウエスト1号館 4階 IMIコンファレンスルーム (W1-D-414)

受講対象  

講師 品野 勇治 (ZIB研究員・IMI訪問教授)

概要:
最新の汎用整数計画ソルバは,最も複雑なソフトウェアの一つである.計算複雑性理論の観点からは,解く問題はNP困難であるにも関わらず,現実的な時間内で実用的な問題が扱えるようになってきている.線形計画ソルバを利用した分枝カット法で問題は解かれるが,それぞれのアルゴリズム構成要素はヒューリスティックな実装であり,それぞれが多くのパラメタを持つ.このため,新たなアルゴリズムの追加や,あるヒューリスティックのパラメタの変更が,全体の性能へ与える影響を正確に把握することも困難である.加えて,ソルバの性能評価方法も確立されているわけではなく,どのような評価方法を用いても,解く問題のデータセットによって評価は変わる.このような状態にも関わらず,整数計画ソルバは,実感として性能が向上していると受け入れられている.本講演では,整数計画ソルバ開発の現状を紹介するとともに,その性能評価について議論する.また,並列分枝限定法ソルバの性能評価についても議論する.