MMDS大阪大学 数理・データ科学教育研究センター
Center for Mathematical Modeling and Data Science,Osaka University

整数計画ソルバ開発とその性能評価について

品野 勇治 (Zuse Institute Berlin)

大阪大学 数理・データ科学セミナー 数理モデルセミナーシリーズ 第18回

整数計画ソルバ開発とその性能評価について

品野 勇治 (Zuse Institute Berlin)

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

DOWNLOAD PDFposter(569.50KB)
講師: 品野 勇治 (Zuse Institute Berlin)
テーマ: 大阪大学 数理・データ科学セミナー 数理モデルセミナーシリーズ 第18回
日時: 2018年12月25日(火) 15:30-17:00
場所: 基礎工学研究科J棟1階セミナー室
参加費: 無料
アクセス: 会場までのアクセスは下記URLをご参照ください。
http://www.es.osaka-u.ac.jp/ja/access.html
お問い合せ: 本ウェブサイトの「お問い合せ」のページをご参照ください。