離散最適化

開講元

数理・計算科学コース

担当教員

澄田 範奈 / 山下 真 / 横井 優

授業形態

講義 (対面型)

メディア利用科目

-

曜日・時限
(講義室)

月3-4 (W9-323(W932)) / 木3-4 (W9-323(W932))

クラス

-

科目コード

MCS.M421

単位数

200

開講時期

2024年度

開講クォーター

2Q

シラバス更新日

2025年3月14日

使用言語

英語

シラバス

授業の目的（ねらい）、概要

離散最適化問題を効率良く解くには，問題のもつ構造の解明が非常に重要である．本講義では，マトロイドと呼ばれる基本的な数理構造に関する理論を解説する．「マトロイド」とは「行列のようなもの」という意味であり，マトロイドはベクトルの一次独立性を抽象化した概念である．講義ではマトロイドの定義から始め，マトロイドの性質を解説し，マトロイド上の基本的な離散最適化問題とそのアルゴリズムを紹介する．また，マトロイドの多面体的性質や劣モジュラ関数といった，関連する概念を紹介する．

本講義のねらいは，離散最適化問題におけるマトロイドの重要性を認識してもらうことである．マトロイドは，解きやすい離散最適化問題の多くに関係しているとも言われるほどに重要である．問題がどういう構造をもつときに解きやすいかという点を知ることは，離散最適化問題を解く上で大きな助けになるはずである．

到達目標

本講義の目標は以下である．
1. マトロイドに関する基本的な概念と離散最適化における重要性を説明できる．
2. マトロイド構造をもつ基本的な離散最適化問題を認識することができる．
3. マトロイド構造をもつ基本的な離散最適化問題のアルゴリズムを説明できる．

キーワード

離散最適化，組合せ最適化，マトロイド，劣モジュラ関数，グラフアルゴリズム，多面体

学生が身につける力

• 専門力
• 教養力
• コミュニケーション力
• 展開力 (探究力又は設定力)
• 展開力 (実践力又は解決力)

授業の進め方

毎回ひとつのトピックに絞って解説する．

授業計画・課題

準備学修(事前学修・復習)等についての指示

学修効果を上げるため，教科書や配布資料等の該当箇所を参照し，「毎授業」授業内容に関する 予習と復習（課題含む）をそれぞれ概ね100分を目安に行うこと。

教科書

教科書は指定しない．以下の参考書を基に作成した講義資料を使用する．

参考書、講義資料等

Alexander Schrijver: Combinatorial Optimization - Polyhedra and Efficiency, Springer, 2003.
伊理正夫，藤重 悟，大山達夫：グラフ・ネットワーク・マトロイド，産業図書，1986年．

成績評価の方法及び基準

期末レポートにより評価する．詳細は初回に説明する．

関連する科目

• MCS.T322 ： 組合せアルゴリズム
• MCS.T302 ： 数理最適化

履修の条件・注意事項

数理最適化（MCS.T302）および組合せアルゴリズム（MCS.T322）を履修済み，あるいは同等の知識（組合せ最適化の基礎知識）があること．