数理最適化特論／mathematical optimization

• 2021年度 秋学期 月曜 3時限（13:30〜15:10）

• 授業形態: 第5回までは完全オンライン，第6回からは基本対面

• 登録コードMSIS7210

第1回（9月27日）

• 数理最適化とは？

  • Excel solverの例はMoodleで公開中

  • 整数線形最適化モジュールPuLPの簡単な紹介

  • NEOS Solvers （ワイン生産計画問題のLPファイル）

  • LPファイルの詳しい説明（宮代隆平，整数計画ソルバー入門． オペレーションズ・リサーチ，57-4 (2012)，pp. 183-189. ）

第2回（10月4日）

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

• Symbols

第3回（10月11日）

• 線形最適化問題と双対問題（解答例なし，解答例あり）

第4回（10月18日）

• 前回の続き

第5回（10月25日）

• 整数最適化問題

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

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

第6回（11月8日）

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

第7回（11月15日）

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

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

第8回（11月22日）

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

  • NetworkXによる最小費用流

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

第9回（11月29日）

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

  • 最大流問題

  • 最大流問題に対する増加道解法

  • 最大流・最小カット定理

  • 最大流と最小カットの演習問題

  • 最大2部マッチング問題への応用

    • 無向グラフの誘導部分グラフ

    • 無向2部グラフ

    • 最大2部マッチング問題

  • 画像分割問題への応用

    • より高度な内容の記事（加藤直樹. 画像処理における組合せ最適化問題. オペレーションズ・リサーチ, 1995, 40.7: 363-369.）

• Google colabによるコード例

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

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

第10回（12月6日）

• 動的計画法（解答例なし，解答例あり）動的計画法に関するお話は割愛します．

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

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

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

第11回（12月13日）

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

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

第12回（12月20日）

• 近似アルゴリズム

第13回（12月22日）

• Second-Order Cone Optimization and Robust Optimization

第14回（1月17日）

• Support Vector Machine

  • 参考となる動画

付録

• Blackbox optimization

  • Nelder-Mead法の紹介