【授業の目的】
一般にはNP困難な整数計画問題であっても、最適解や近似精度のよい解が効率的に求められる場合がある。こうした状況に普遍的な数理的構造と最適化技法についての理解を深めることを目的とする。
【授業の到達目標】
効率的に解ける整数計画問題に共通する解空間の構造について理解し、そうしたクラスに属する代表的な整数計画問題に対する効率的な算法を身につけることができる。
【授業概要（キーワード）】
整数計画問題、組合せ最適化、パッキングとカバリングの理論
【学生主体型授業（アクティブラーニング）について】
A-1．ミニッツペーパー、リフレクションペーパー等によって、自分の考えや意見をまとめ、文章を記述し提出する機会がある。：1～25％
C-1．自分の意見をまとめて発表する機会がある。：1～25％
D-1．演習、実習、実験等を行う機会がある。：1～25％
A-2．小レポート等により、事前学習（下調べ、調査等含む）が必要な知識の上に思考力を問う形での文章を記述する機会がある。：1～25％
C-2．事前学習（下調べ、調査等含む）をした上で、プレゼンテーションを行い、互いに質疑応答や議論を行う機会がある。：1～25％
D-2．事前学習（下調べ、調査等含む）で習得した知識等を踏まえて演習、実習、実験等を行う機会がある。：1～25％
D-3．習得した知識を活用する中で、学生自身がテーマや目的などを主体的に定めて課題探究型の演習、実習、実験等を行う機会がある。：1～25％
【科目の位置付け】
理工学研究科博士後期課程（理学系）のカリキュラム・ポリシー「専門分野における深化した知識の修得を目的に、各専攻において体系的な講義と演習科目を開講する」に関連する。
【SDGs（持続可能な開発目標）】
04.質の高い教育をみんなに
09.産業と技術革新の基盤をつくろう
【授業計画】
・授業の方法
講義形式で行う。
・日程
第1回目 整数計画法概論
第2回目 ネットワークフローの理論
第3回目 マッチング理論とマッチング多面体
第4～5回目 マトロイド理論
第6～8回目 理想グラフの理論
第9～10回目 多品種フローと辺素パス問題
第11～12回目 ブロッキング多面体とアンチブロッキング多面体
第13～15回目 パッキングとカバリングの理論
【学習の方法・準備学修に必要な学修時間の目安】
・受講のあり方
講義内容の理解に努める。
・授業時間外学習（予習・復習）のアドバイス
１）準備学修に必要な学修時間の目安は2時間/週です。
２）自分なりに証明をまとめる。
３）小さな例に対してアルゴリズムの動きを確認する。
【成績の評価】
・基準
各回の項目における基礎的な事項について適切に説明できることを合格の基準とします。
・方法
レポート点１００点
【テキスト・参考書】
テキスト： なし
参考書：B. Korte and J. Vygen 著「Combinatorial Optimization -Theory and Algorithm-」（Springer）
【その他】
・オフィス・アワー
まず、webclssなどを利用し、メールによるコンタクトを取って下さい。
随時オンラインにより、対応致します。
|