数理最適化特論／mathematical optimization

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

• 授業形態: 対面授業

• 登録コードMSIS7210

第1回（9月30日） 

• 数理最適化とは？

  • Excel solverによるWeber問題の最適化例

  • 線形最適化問題をGurobiで解いてみる

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

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

第2回（10月7日）

• 数理最適化問題に関する基本的な用語

• 線形最適化問題

• 線形最適化問題に対する単体法の基本，演習問題の解答例

第3回（10月14日）

• 線形最適化問題の双対問題，演習問題の解答例

第4回（10月21日）

• 前回の続き

第5回（10月28日）

• 無向グラフと有向グラフの定義

• 整数最適化問題

  • 整数最適化問題とナップサック問題

  • 最大安定集合問題

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

  • 頂点彩色問題

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

  • 最短s-t-路問題

    • • 部分グラフ，パス，閉路

  • Bool代数と最大充足問題とNP-困難性

第6回（11月11日）

• 前回の続き

第7回（11月18日）

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

  • ナップサック問題に対する分枝限定法（約24分の動画）

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

  • TSPに対する分枝限定法

    • Traveling salesman problem (Web page)

第8回（11月25日）

• TSPと整数最適化，演習問題の解答例

  • Exponential formulation（Google colabによるコード例）

  • Potential formulation (by Miller, Tucker and Zemlin)（Google colabによるコード例）

  • Flow formulation（Google colabによるコード例）

第9回（12月2日）

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

  • NetworkXによる最小費用流

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

第10回（12月9日）

• Second-Order Cone Optimization and Robust Optimization

第11回（12月16日）

• Support Vector Machine

  • 演習問題

  • 参考となる動画

第12回（12月23日）

• 近似アルゴリズム

  • ナップサック問題に対する近似解法

  • 頂点被覆問題に対する主双対近似解法

第13回（1月6日）

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

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

第14回（1月20日）

• Blackbox optimization

  • Nelder-Mead法の紹介

付録

• 最大流と最小カット

  • 最大流問題問題

  • 最大流問題に対する増加道アルゴリズム

    • NetworkXを用いた最大流問題の解説（Google colabによるコード例）

    • NetworkXを使わずに最大流問題を解くコード例（Google colabによるコード例）

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

  • 最大流の整数性とその応用

    • 最大流問題の演習問題（付録）

  • 画像分割問題への応用

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