組合せ最適化特論

Advanced Combinatorial Optimization

991JD06

14MAAPM514

胡　艶楠

Yannan HU

2024年度後期

2024, second semester　

金曜4限

Friday, 4th period

理学研究科　応用数学専攻

Department of Applied Mathematics, Graduate School of Science

2.0単位

講義

Lecture

-

① [対面]対面授業/ [On-site] On-site class

最適化理論の基礎と応用を学ぶ．最適化の対象は，ネットワーク，電力，生産，スケジューリング，ルーティングと枚挙にいとまがなく，最適化理論はこのようなさまざまな対象の効率化を可能にする．本講義では，最適化の代表的な問題であるナップサック問題，巡回セールスマン問題，スケジューリング問題，割当問題，最大充足可能性問題などを紹介する．また，それらの問題に対する近似解法の基本戦略やメタ戦略で用いられる様々なアイデアを説明する．
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.

本講義では，最適化における基礎的な問題を解決するアルゴリズムを修得することを目的とする.
The Objective is to understand representative methods for the optimization problems.

実際の問題を数理的に定式化する能力，および，定式化に基づいて，効率的なアルゴリズムを設計する能力を身につける．
We aim to gain the ability to formulate practical problems and design efficient algorithms to solve the problems.

リンク先の [評価項目と科目の対応一覧]から確認できます（学部対象）。
履修登録の際に参照ください。
​You can check this from “Correspondence table between grading items and subjects” by following the link(for departments).
https://www.tus.ac.jp/fd/ict_tusrubric/​​​

アルゴリズム設計の基礎知識があることが望ましい.
Basic knowledge of algorithm design such as the analysis of complexity is expected.

ディベート・ディスカッション　Debate/Discussion／グループワーク　Group work／プレゼンテーション　Presentation／反転授業　Flipped classroom／実験　Experiments

-

前回の内容のノートを見返して復習し，やり残した部分を完成しておく．クラスメイト 同士でディスカッションをしておく．
It is important to make sure that contents in earlier lectures are understood and discuss with classmates.

グループに分かれて演習問題に取り組み，プレゼンテーションしてもらう．
組合せ最適化問題に対するプログラミングコンペティションを行うこともある．
演習課題，プレゼンテーションとコンペティションの結果により成績を総合的に評価する．
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. We also may hold a programming competition on combinatorial optimization. The grades are determined by the completeness of the presentation and results of the competition.

・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

N

-

教科書および一部の参考書は、MyKiTS (教科書販売サイト) から検索・購入可能です。
​https://mirai.kinokuniya.co.jp/tokyorika/​​​

It is possible to search for and purchase textbooks and certain reference materials at MyKiTS (online textbook store).
​​https://mirai.kinokuniya.co.jp/tokyorika/

B. Korte and J. Vygen, Combinatorial Optimization: Theory and Algorithms, Springer

第１回：ガイダンス
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

-

-

-

Y

-