数理最適化特論／mathematical optimization

• 2019年度 秋学期 水曜 4時限（15:15〜16:45）
• 2号館 404号講義室（暫定的措置，再び変更の可能性あり）
• 登録コードMSIS7210

1st lecture (Oct. 2)

• Guidance

2nd lecture (Oct. 9)

• What is mathematical optimization?
  • Excel solver example
  • Python (PuLP) example（Google colaboratory version）
  • NEOS Solvers

• Symbols
• Terms

3rd lecture (Oct. 16)

• Linear optimization and simplex method (filled in version)
  • 途中で5分休憩しても良かったかもしれません．

4th lecture (Oct. 23)

• Linear optimization and dual (filled in version)

5th lecture (Oct. 30)

• Integer optimization
  • 最大安定集合問題をPuLPで解いてみる
  • 頂点彩色問題をPuLPで解いてみる

6th lecture (Nov. 6)

• quiz01（出題範囲は3rd lectureと4th lectureのexercise）
  • ちなみに昨年のquiz01
• Branch and bound, NP-completeness
  • 今回はInteger optimizationのDirected graph and shortest s-t-path problemから説明します．
  • ナップサック問題に対する分枝限定法のコード例

7th lecture (Nov. 13)

• Quiz02（出題範囲は5th lectureのexercise，出題例）
  • Quiz02終了後に指摘を受けて気がついたのですが，出題にミスが有りました．よってQuiz02は無効としたいと思います．受験者の皆さんごめんなさい．
• 今回はbranch and boundの「一般のナップサック問題に対する分枝限定法」と「TSPに対する分枝限定法」から説明します．

• Assignment 1

8th lecture (Nov. 20)

• Totally unimodular matrix and minimum cost flow
  • NetworkXによる最小費用流
  • 最小費用流を用いた航空スケジューリング

9th lecture (Nov. 27)

• Maximum flow and minimum cut

10th lecture (Dec. 4)

• Quiz03（出題は8th lectureの12ページのExercise，定義と定理は予め問題用紙に書いておきます）
  • ちなみに昨年のQuiz
• Dynamic Programming
  • ナップサック問題に対する動的計画法

11th lecture (Dec. 11)

• Quiz04（出題は9th lectureのExerciseと同等の問題とします．）
  • 試験時間は15分，持ち込み不可
  • ちなみに昨年のquiz←t=6はt=4の誤りです．
• Greedy algorithm
  • 最小全域木とKruskalのアルゴリズムとunion find treeのコード例

Appendix: Approximation algorithm

講義では扱わないけれど講義資料はあるので，付録として載せておきます．

12th lecture (Dec. 18)

• Second-Order Cone Optimization and Robust Optimization

Assignment 2

13th lecture (Jan. 8)

• Quiz05（出題は11th lectureから，こんな感じの問題）
  • 試験時間は15分，持ち込み不可
• Support Vector Machine
  • 参考となる動画

14th lecture (Jan. 15)

• Quiz06（出題は10th lectureから，こんな感じの問題）
  • 試験時間は10分，持ち込み不可
• Blackbox optimization
  • Nelder-Mead法の紹介