組み合わせ最適化特論

• 2024年度 春学期 夏期集中

• 対面授業

Lecture 01

• 線形最適化と数理最適化

• ナップサック問題

• 地図の彩色問題

Lecture 02

• Excelソルバーによる線形最適化の例

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

• Neos solvers（LPファイルのサンプル）

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

Lecture 03

• 線形最適化問題

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

用語

Lecture 04

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

Lecture 05

• 整数最適化問題の困難姓

• 最大安定集合問題

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

• 頂点彩色問題

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

Lecture 06

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

• 分枝限定法

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

Lecture 07

• TSPと整数最適化

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

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

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

Lecture 08

• ウェーバー問題

  • Excelソルバーによる最適化

• 二次錐最適化とロバスト最適化

Lecture 09

• Support Vector Machine

  • 参考となる動画

Lecture 10

• 更新講習

• ブラックボックス最適化

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

• 最大流と最小カット

• 貪欲解法とマトロイド

Lecture 11

• 近似解法

レポート課題

• 詳細はそれぞれの講義中に随時指示する．