組合せ最適化特論のシラバス情報

科目名称
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回:ガイダンス
1. Guidance

第2回:組合せ最適化の一般的定義と応用
2. Applications and general definition of combinatorial optimization

第3回:ナップサック問題
3. Knapsack problem

第4回:巡回セールスマン問題
4. Traveling salesman problem

第5回:1機械スケジューリング問題と最大充足可能性問題
5. Single machine scheduling problem and maximum satisfiability

第6回:一般割当問題とグラフ彩色問題
6. Generalized assignment problem and graph coloring problem

第7回:計算効率の評価
7. Analysis of computational complexity

第8回:近似解法の戦略(欲張り法)
8. Greedy algorithm

第9回:近似解法の戦略(局所探索法)
9. Local search

第10回:メタ戦略の基礎
10. Basic knowledge of meta-heuristics

第11回:メタ戦略の実現(多スタート局所探索法,GRASP,反復局所探索法)
11. Multi-start local search, GRASP, iterated local search

第12回:メタ戦略の実現(遺伝アルゴリズム,アント法,誘導局所探索法)
12. Genetic algorithm, ant system, guided local search

第13回:メタ戦略の実現(アニーリング法,閾値受理法)
13. Simulated annealing, threshold accepting

第14回:メタ戦略の実現(タブー探索法)
14. Tabu search

第15回:総括
15. Conclusion

教職課程
Teacher-training course
実務経験
Practical experience
-
教育用ソフトウェア
Educational software
-
備考
Remarks
991JD06
CLOSE