数理最適化特論／mathematical optimization

• 2020年度 秋学期 水曜 4時限（15:15〜16:45）

• オンライン授業

• 登録コードMSIS7210

第1回（9月30日）

• 数理最適化とは？

  • Excel solver example

  • Python (PuLP) example（Google colaboratory version）

  • NEOS Solvers

• Symbols

• Terms

第2回（10月7日）

• • 線形最適化問題と単体法（解答例なし，解答例あり）

第3回（10月14日）

• 線形最適化問題と双対問題（解答例なし，解答例あり）（←更新しました．）

第4回（10月21日）

• 前回の続き

第5回（10月28日）

• 整数最適化問題（今回の演習問題には解答例なしのみです）

  • 最大安定集合問題をPuLPで解いてみる

  • 頂点彩色問題をPuLPで解いてみる

第6回（11月11日）

• 前回の続き

第7回（11月18日）

• 整数最適化問題のNP-困難性

• 整数最適化問題に対する分枝限定法

  • ナップサック問題に対する分枝限定法のコード例

第8回（11月25日）

• 完全ユニモジュラ行列と最小費用流問題

  • NetworkXによる最小費用流

  • 最小費用流を用いた航空スケジューリング

第9回（12月2日）

• 最大流問題と最小カット定理

  • NetworkXを用いた最大流問題の解説

  • NetworkXを使わずに最大流問題を解くコード例

第10回（12月9日）

• 動的計画法（解答例なし，解答例あり）

  • ナップサック問題に対する動的計画法

  • 単始点最短路問題とダイクストラ法のコード例

  • 全点間最短路とFloyd-Warshall法

第11回（12月16日）

• 貪欲アルゴリズムとマトロイド

  • 最小全域木とKruskalのアルゴリズムとunion find treeのコード例

第12回（1月6日）

• 近似アルゴリズム

第13回（1月13日）

• Second-Order Cone Optimization and Robust Optimization

第14回（1月20日）

• Support Vector Machine

  • 参考となる動画

• Blackbox optimization（付録扱い）

  • Nelder-Mead法の紹介