数理最適化特論／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日）

• Dynamic Programming

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

第11回（12月16日）

• Greedy algorithm

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

Appendix: Approximation algorithm

12th lecture (Jan. 6)

• Second-Order Cone Optimization and Robust Optimization

13th lecture (Jan. 13)

• Quiz05（出題は11th lectureから，こんな感じの問題）

  • 試験時間は15分，持ち込み不可

• Support Vector Machine

  • 参考となる動画

14th lecture (Jan. 20)

• Quiz06（出題は10th lectureから，こんな感じの問題）

  • 試験時間は10分，持ち込み不可

• Blackbox optimization

  • Nelder-Mead法の紹介