組合せ最適化特論のシラバス情報
| 科目名称 Course title(Japanese) |
組合せ最適化特論 | 科目番号 Course number |
14MAAPM514 | |
|---|---|---|---|---|
| 科目名称（英語） Course title(English) |
Advanced Combinatorial Optimization | |||
| 授業名称 Class name |
組合せ最適化特論 | |||
| 教員名 | 胡 艶楠 |
|---|---|
| Instructor | Yannan HU |
| 開講年度学期 | 2022年度 後期 |
|---|---|
| Year/Semester | 2022， Second Semester |
| 曜日時限 | 火曜2限 |
|---|---|
| Class hours | Tuesday, 2nd Period |
| 開講学科 Department |
理学研究科 応用数学専攻 Graduate School of Science, Department of Applied Mathematics |
|---|---|
| 外国語のみの科目 （使用言語） Course in only foreign languages (languages) |
- |
| 単位 Course credit |
2.0 | 授業の主な実施形態 Main class format |
ハイフレックス型授業/Hybrid-Flexible format |
|---|
| 概要 Descriptions |
最適化理論の基礎と応用を学ぶ．最適化の対象は，ネットワーク，電力，生産，スケジューリング，ルーティングと枚挙にいとまがなく，最適化理論はこのようなさまざまな対象の効率化を可能にする．本講義では，最適化の代表的な問題であるナップサック問題，巡回セールスマン問題，スケジューリング問題，割当問題，最大充足可能性問題などを紹介する．また，それらの問題に対する近似解法の基本戦略やメタ戦略で用いられる様々なアイデアを説明する． We will learn about the basic knowledge of combinatorial optimization including network, production, scheduling, routing problems. In this lecture, we introduce representative combinatorial optimization problems such as knapsack, traveling salesman, scheduling, assignment problems. We also study strategies of approximation algorithms and ideas of metaheuristics for those problems. |
|---|---|
| 目的 Objectives |
本講義では，最適化における基礎的な問題を解決するアルゴリズムを修得することを目的とする. The Objective is to understand representative methods for the optimization problems. |
| 到達目標 Outcomes |
実際の問題を数理的に定式化する能力，および，定式化に基づいて，効率的なアルゴリズムを設計する能力を身につける． We aim to gain the ability to formulate practical problems and design efficient algorithms to solve the problems. |
| 履修上の注意 Course notes prerequisites |
アルゴリズム設計の基礎知識があることが望ましい. Basic knowledge of algorithm design such as the analysis of complexity is expected. |
| アクティブ・ラーニング科目 Teaching type（Active Learning） |
|||
|---|---|---|---|
| 課題に対する作文 Essay |
- | 小テストの実施 Quiz type test |
- |
| ディベート・ディスカッション Debate/Discussion |
あり | グループワーク Group work |
あり |
| プレゼンテーション Presentation |
あり | 反転授業 Flipped classroom |
あり |
| その他（自由記述） Other（Describe） |
- | ||
| 準備学習・復習 Preparation and review |
前回の内容のノートを見返して復習し，やり残した部分を完成しておく．クラスメイト 同士でディスカッションをしておく． It is important to make sure that contents in earlier lectures are understood and discuss with classmates. |
|---|---|
| 成績評価方法 Performance grading policy |
グループに分かれて演習問題に取り組み，プレゼンテーションしてもらう．演習課題とプレゼンテーションにより成績を総合的に評価する． We adopt a group manner to present projects given in the lecture. We first divide the students in groups and each group takes care of one project and present to teach others. The grades are determined by the completeness of the presentation and performance in the class. |
| 学修成果の評価 Evaluation of academic achievement |
・S：到達目標を十分に達成し、極めて優秀な成果を収めている ・A：到達目標を十分に達成している ・B：到達目標を達成している ・C：到達目標を最低限達成している ・D：到達目標を達成していない ・-：学修成果の評価を判断する要件を欠格している ・S：Achieved outcomes, excellent result ・A：Achieved outcomes, good result ・B：Achieved outcomes ・C：Minimally achieved outcomes ・D：Did not achieve outcomes ・-：Failed to meet even the minimal requirements for evaluation |
| 教科書 Textbooks/Readings |
・教科書を使用する場合は、MyKiTS(教科書販売サイト)から検索・購入可能ですので以下のURLにアクセスしてください。 https://gomykits.kinokuniya.co.jp/tokyorika/ ・Search and purchase the necessary textbooks from MyKiTS (textbook sales site) with the link below. https://gomykits.kinokuniya.co.jp/tokyorika/ |
| 参考書・その他資料 Reference and other materials |
B. Korte and J. Vygen, Combinatorial Optimization: Theory and Algorithms, Springer |
| 授業計画 Class plan |
第１回：ガイダンス 1. Guidance 第２回：組合せ最適化の一般的定義と応用 2. Applications and general definition of combinatorial optimization 第３回：ナップサック問題 3. Knapsack problem 第４回：巡回セールスマン問題 4. Traveling salesman problem 第５回：1機械スケジューリング問題と最大充足可能性問題 5. Single machine scheduling problem and maximum satisfiability 第６回：一般割当問題とグラフ彩色問題 6. Generalized assignment problem and graph coloring problem 第７回：計算効率の評価 7. Analysis of computational complexity 第８回：近似解法の戦略（欲張り法） 8. Greedy algorithm 第９回：近似解法の戦略（局所探索法） 9. Local search 第１０回：メタ戦略の基礎 10. Basic knowledge of meta-heuristics 第１１回：メタ戦略の実現（多スタート局所探索法，GRASP，反復局所探索法） 11. Multi-start local search, GRASP, iterated local search 第１２回：メタ戦略の実現（遺伝アルゴリズム，アント法，誘導局所探索法） 12. Genetic algorithm, ant system, guided local search 第１３回：メタ戦略の実現（アニーリング法，閾値受理法） 13. Simulated annealing, threshold accepting 第１４回：メタ戦略の実現（タブー探索法） 14. Tabu search 第１５回：総括 15. Conclusion |
|---|
| 教職課程 Teacher-training course |
|
|---|---|
| 実務経験 Practical experience |
- |
| 教育用ソフトウェア Educational software |
- |
| 備考 Remarks |
|---|
| 991JD06 |
