こんなに使える (組合せ) 最適化手法 梅谷 俊治 大阪大学 大学院情報科学研究科 情報数理学専攻 科学技術振興機構 2011 年 9 月 7 日 第 10 回情報科学技術フォーラム (FIT2011) はじめに • 最適化手法は計算機の性能向上とアルゴリズムの進歩によっ て,現実世界の様々な問題の解決に有効な手段となりました. • 本講演では最適化分野の概要といくつかの現実問題に対する 最適化手法の取り組みを紹介します. 最短路問題 (2400 万点,5800 万枝) 巡回セールスマン問題 (24978 都市) 多角形詰込み問題 (48 製品) 本発表の概要 • 最適化分野の概要 • 計算困難な組合せ最適化問題 • 現実問題に対するアプローチ 最適化手法による問題解決アプローチ • 最適化は意思決定・問題解決のための一つの手段 • 最適化問題に定式化+最適解の計算+最適解の検証・分析