整数計画ソルバ開発とその性能評価について
品野 勇治 (Zuse Institute Berlin)
大阪大学 数理・データ科学セミナー 数理モデルセミナーシリーズ 第18回
整数計画ソルバ開発とその性能評価について
品野 勇治 (Zuse Institute Berlin)
最新の汎用整数計画ソルバは，最も複雑なソフトウェアの一つである．計算複雑性理論の観点からは，解く問題はNP困難であるにも関わらず，現実的な時間内で実用的な問題が扱えるようになってきている．線形計画ソルバを利用した分枝カット法で問題は解かれるが，それぞれのアルゴリズム構成要素はヒューリスティックな実装であり，それぞれが多くのパラメタを持つ．このため，新たなアルゴリズムの追加や，あるヒューリスティックのパラメタの変更が，全体の性能へ与える影響を正確に把握することも困難である．加えて，ソルバの性能評価方法も確立されているわけではなく，どのような評価方法を用いても，解く問題のデータセットによって評価は変わる．このような状態にも関わらず，整数計画ソルバは，実感として性能が向上していると受け入れられている．本講演では，整数計画ソルバ開発の現状を紹介するとともに，その性能評価について議論する．
DOWNLOAD PDFposter(569.50KB)| 講師： | 品野 勇治 (Zuse Institute Berlin) |
|---|---|
| テーマ： | 大阪大学 数理・データ科学セミナー 数理モデルセミナーシリーズ 第18回 |
| 日時： | 2018年12月25日(火) 15:30-17:00 |
| 場所： | 基礎工学研究科Ｊ棟１階セミナー室 |
| 参加費： | 無料 |
| 参加方法： | |
| アクセス： | 会場までのアクセスは下記URLをご参照ください。 http://www.es.osaka-u.ac.jp/ja/access.html |
| お問い合せ： | 本ウェブサイトの「お問い合せ」のページをご参照ください。 |