シラバス参照
|
シラバス参照
|
| 講義概要/Course Information |
| 科目基礎情報/General Information |
| 授業科目名 /Course title (Japanese) |
離散最適化基礎論 | ||
|---|---|---|---|
| 英文授業科目名 /Course title (English) |
Foundation of Discrete Optimization | ||
| 科目番号 /Code |
|||
| 開講年度 /Academic year |
2022年度 | 開講年次 /Year offered |
全学年 |
| 開講学期 /Semester(s) offered |
後学期 | 開講コース・課程 /Faculty offering the course |
博士前期課程 |
| 授業の方法 /Teaching method |
講義 | 単位数 /Credits |
2 |
| 科目区分 /Category |
大学院専門教育科目 - 専門科目Ⅰ | ||
| 開講類・専攻 /Cluster/Department |
情報・ネットワーク工学専攻 | ||
| 担当教員名 /Lecturer(s) |
岡本 吉央 | ||
| 居室 /Office |
西4-206 | ||
| 公開E-mail |
okamotoy followed by @uec.ac.jp | ||
| 授業関連Webページ /Course website |
http://dopal.cs.uec.ac.jp/okamotoy/lect/2022/ip/ | ||
| 更新日 /Last update |
2022/09/26 20:12:14 | 更新状況 /Update status |
公開中 /now open to public |
| 講義情報/Course Description |
| 主題および 達成目標（2,000文字以内） /Themes and goals（up to 2,000 letters） |
離散最適化における1つのトピックを集中的に学ぶ．今年度は「整数計画法」を題材とする．整数計画法は離散最適化における重要な手法であり，それを解くためのソフトウェア開発はここ数十年で大きな進展を見せている．この講義では，その基礎に関して，概念と手法を理解し，例に対して応用が可能となることを達成目標とする． The course provides intensive discussion on a single topic of discrete optimization. The topic of this academic year is "Integer Programming." Integer programming provides a comprehensive methodology for discrete optimization, and past few years have experienced a fruitful software development for integer programming. The learning objective is to understand the concepts and methods, and to apply them to examples. |
|---|---|
| 前もって履修 しておくべき科目（1,000文字以内） /Prerequisites（up to 1,000 letters） |
離散数学，線形代数学第一 Discrete Mathematics，Linear Algebra I |
| 前もって履修しておくこ とが望ましい科目（1,000文字以内） /Recommended prerequisites and preparation（up to 1,000 letters） |
オペレーションズ・リサーチ基礎，数理計画法，アルゴリズム論第一，アルゴリズム論第二，グラフとネットワーク Introduction to Operations Research, Mathematical Programming, Algorithms I, Algorithms II, Graphs and Networks |
| 教科書等（1,000文字以内） /Course textbooks and materials（up to 1,000 letters） |
教科書： なし．講義資料を毎回用意するので，講義webページより各自入手すること． 参考書，参考文献： M. Conforti, G. Cornuejols, G. Zambelli. Integer Programming. Springer, 2014. その他の参考文献は講義中に挙げる． Textbook: None. The course materials will be provided through the course webpage. Supplementary Book: M. Conforti, G. Cornuejols, G. Zambelli. Integer Programming. Springer, 2014. The related materials will be referred to in the class. |
| 授業内容と その進め方（2,000文字以内） /Course outline and weekly schedule（up to 2,000 letters） |
授業計画： 1. 整数計画法と線形計画法 2. 線形計画法の復習 (1)：線形不等式系と凸多面集合 3. 線形計画法の復習 (2)：単体法と双対定理 4. 線形計画緩和 5. 整数計画モデリング (1)：組合せ最適化問題 6. 整数計画モデリング (2)：より複雑な問題 7. 整数計画モデリング (3)：離接計画 8. 前半のまとめ 9. 分枝限定法 10. 切除平面法 11. 妥当不等式の追加 12. 列生成法 13. ラグランジュ緩和 (1)：原理 14. ラグランジュ緩和 (2)：最適ラグランジュ緩和 15. 後半のまとめ 進め方： 教室で講義を行うが，リアルタイムでZoom中継も行う．録画した講義を後で見直せるようにする．「遠隔授業に関する情報」に記載されているGoogle Classroomに参加すること． Plan: 1. Integer programming and linear programming 2. Recap of linear programming (1): Systems of linear inequalities and convex polyhedra 3. Recap of linear programming (2): Simplex methods and duality theorems 4. Linear programming relaxation 5. Integer program modeling (1): Combinatorial optimization problems 6. Integer program modeling (2): More complex problems 7. Integer program modeling (3): Disjunctive programming 8. Review of the first half 9. Branch-and-bound method 10. Cutting plane method 11. Valid inequalities 12. Column generation method 13. Lagrange relaxation (1): Principle 14. Lagrange relaxation (2): Optimal Lagrange relaxation 15. Review of the second half Format: Lectures will be delivered at a lecture room, but at the same time broadcast via Zoom. Lecture videos will be made public. Students are supposed to join Google Classroom described in "Distance learning information". |
| 実務経験を活かした 授業内容 (実務経験内容も含む) /Course content utilizing practical experience |
|
| 授業時間外の学習 （予習・復習等）（1,000文字以内） /Preparation and review outside class（up to 1,000 letters） |
講義動画を用いて復習を行う Recap by lecture videos |
| 成績評価方法 および評価基準 （最低達成基準を含む） （1,000文字以内） /Evaluation and grading （up to 1,000 letters） |
成績評価方法：1回の期末試験によって評価を行う予定であるが，社会情勢に応じて，評価方法を変更する可能性もある． 評価基準： 基本的な概念を理解し，解析手法と例に対する応用ができること． Evaluation: One final exam (with possibility of change due to pandemic) Evaluation criteria: Understanding of basic concepts, and ability of application of methods to examples |
| オフィスアワー： 授業相談（1,000文字以内） /Office hours（up to 1,000 letters） |
メールにて相談． Appointment by email |
| 学生へのメッセージ（1,000文字以内） /Message for students（up to 1,000 letters） |
整数計画法は離散最適化における重要なトピックであり，それについてまとめて学ぶ機会はあまり多くない．本講義では，できる限り系統だった説明を心掛け，最適化を専門としない学生が基本原理を理解できるようにして，最適化を自身の研究の中で利用したいと願う学生に役立つ内容としたい． |
| その他 /Others |
他専攻，他研究科の学生も歓迎する． Students from other departments are welcome to join. |
| キーワード /Keywords |
整数計画法，線形計画法，凸多面集合，妥当不等式，端点，端線，面，ファセット，基底解，被約費用，双対定理，相補性定理，線形計画緩和，組合せ最適化，離接計画，分枝限定法，切除平面法，列生成法，ラグランジュ緩和，劣勾配法 |