理工学部Faculty of Science and Engineering
PRI300XF（情報学基礎 / Principles of informatics 300）組合せ最適化Combinatorial Optimization
髙澤 兼二郎、五島 洋行Kenjiro TAKAZAWA, Hiroyuki GOTO
授業コードなどClass code etc
| 学部・研究科Faculty/Graduate school | 理工学部Faculty of Science and Engineering |
| 添付ファイル名Attached documents | |
| 年度Year | 2024 |
| 授業コードClass code | H6545 |
| 旧授業コードPrevious Class code | |
| 旧科目名Previous Class title | |
| 開講時期Term | 春学期授業/Spring |
| 曜日・時限Day/Period | 金2/Fri.2 |
| 科目種別Class Type | |
| キャンパスCampus | 小金井 |
| 教室名称Classroom name | 小西館‐W003PC |
| 配当年次Grade | 3年 |
| 単位数Credit(s) | |
| 備考（履修条件等）Notes | |
| 他学部公開科目Open Program | |
| 他学部公開（履修条件等）Open Program (Notes) | |
| グローバル・オープン科目Global Open Program | |
| 成績優秀者の他学部科目履修制度対象Interdepartmental class taking system for Academic Achievers | |
| 成績優秀者の他学部科目履修（履修条件等）Interdepartmental class taking system for Academic Achievers (Notes) | |
| 実務経験のある教員による授業科目Class taught by instructors with practical experience | |
| SDGsCPSDGs CP | |
| アーバンデザインCPUrban Design CP | |
| ダイバーシティCPDiversity CP | |
| 未来教室CPLearning for the Future CP | |
| カーボンニュートラルCPCarbon Neutral CP | |
| 千代田コンソ単位互換提供（他大学向け）Chiyoda Campus Consortium | |
| カテゴリー＜理工学部＞Category |
経営システム工学科 学科専門科目 |
すべて開くShow all
すべて閉じるHide All
Outline (in English)
[Course outline]
In mathematical analyses, optimization problems are roughly divided into continuous and discrete optimization contexts. This class is concerned with the latter type, particularly focusing on a type called "combinatorial optimization".
In the theoretical part, the basis of complexity theory and approaches to solving hard problems are presented.
In the implementation part, problems familiar in everyday life such as packing, SUDOKU puzzle, and scheduling, are taken up to solve these using a general-purpose solver.
[Learning objectives]
Upon completion, students should be able to:
1. analyze the complexity of problems.
2. formulate problems mathematically.
3. describe problems for general-purpose solvers.
4. solve large-scale problems with a general-purpose solver.
[Learning activities outside of classroom]
1. Students should spend four hours for preparation and review.
2. An assignment will be given on completion of each topic.
[Grading criteria]
The final grading will be conducted based on:
Theoretical part: assignment (70%), class contribution (30%)
Implementation part: assignment (70%), class contribution (30%)
授業で使用する言語Default language used in class
日本語 / Japanese
授業の概要と目的（何を学ぶか）Outline and objectives
数理最適化問題は大きく，連続最適化と離散最適化とに大別されるが，本授業では後者の一種である組合せ最適化を扱う．パッキングやパズル，スケジューリング問題など日常生活に近い組合せ最適化問題を例にとり，解法のアプローチを理論と実装の両面から学ぶ．
理論パートでは，上記の問題を通じて，計算複雑度の解析や，計算困難な問題に対する，数理最適化問題としての定式化などの求解アプローチについて学ぶ．
実装パートでは，汎用ソルバーを用いて上記の最適化問題を解く方法を学ぶ．
到達目標Goal
組合せ最適化に関する諸問題に関して，下記のことが行える．
・効率的に解ける問題か，NP困難な問題かを分析できる
・数理最適化問題として定式化できる
・汎用ソルバー向けに問題を記述し，ソルバーに最適化問題を解かせることができる
・大規模な最適化問題が，汎用ソルバーを用いて解ける
この授業を履修することで学部等のディプロマポリシーに示されたどの能力を習得することができるか（該当授業科目と学位授与方針に明示された学習成果との関連）Which item of the diploma policy will be obtained by taking this class?
ディプロマポリシーのうち、「DP1」と「DP2」と「DP4」に関連
授業で使用する言語Default language used in class
日本語 / Japanese
授業の進め方と方法Method(s)（学期の途中で変更になる場合には、別途提示します。 /If the Method(s) is changed, we will announce the details of any changes. ）
理論パート７週と，実装パート７週とで構成する．
理論パートでは，問題の計算複雑度や定式化などについて講義する．大テーマ終了毎に提出課題を課す．
実装パートでは，最適化ソルバーSCIP，および数値解析環境MATLABを用いながら最適化問題を解く．大テーマ終了毎に提出課題を課す．
アクティブラーニング（グループディスカッション、ディベート等）の実施Active learning in class (Group discussion, Debate.etc.)
なし / No
フィールドワーク（学外での実習等）の実施Fieldwork in class
なし / No
授業計画Schedule
授業形態/methods of teaching：対面/face to face
※各回の授業形態は予定です。教員の指示に従ってください。
1[対面/face to face]：イントロダクション
本科目の導入，および講義の進め方の説明
2[対面/face to face]：ナップサック問題（理論）
NP困難性の証明法，整数計画問題としての定式化，動的計画法について学ぶ
3, 4[対面/face to face]：数独パズル（理論）
制約充足問題としての定式化を学ぶ
5[対面/face to face]：ジョブショップスケジューリング（理論）
混合整数計画問題としての定式化を学ぶ
6, 7[対面/face to face]：PERT，最長経路問題（理論）
PERT の最長経路問題による表現，混合整数計画問題としての定式化を学ぶ
8[対面/face to face]：汎用ソルバー
汎用ソルバーSCIPの使用法を学ぶ
9[対面/face to face]：ナップサック問題（実装）
大規模なナップサック問題を整数計画問題として定式化して解く
10, 11[対面/face to face]：数独パズル（実装）
数独パズルを制約充足問題として定式化して解く
12, 13[対面/face to face]：ジョブショップスケジューリング（実装）
ジョブショップスケジューリング問題を，混合整数計画問題として定式化して解く
14[対面/face to face]：PERT，最長経路問題（実装）
PERT問題を最長経路問題の一つとして定式化して解く
授業時間外の学習（準備学習・復習・宿題等）Work to be done outside of class (preparation, etc.)
・本授業の準備・復習等の授業時間外学習は、4時間を標準とする．
・理論パート，実装パートともに，大テーマ終了時に提出課題が課せられるので，指定された期限までに提出する．
テキスト（教科書）Textbooks
指定せず，教材を授業支援システム経由で配布する．
参考書References
必要に応じて紹介する．
成績評価の方法と基準Grading criteria
理論パート50%，実装パート50%の配分で，それぞれのパートは以下で評価する
理論パート：
提出課題 70% (35点)，平常点 30% (15点)
実装パート：
提出課題 70% (35点)，平常点 30% (15点)
学生の意見等からの気づきChanges following student comments
特になし．
学生が準備すべき機器他Equipment student needs to prepare
・極力貸与ノートPCを持参すること．実装パートの週は必須である．
・MATLABが動作する環境を事前に整えておくこと．初めて使用する者は，ライセンス認証が必要である．
その他の重要事項Others
・２年次秋学期科目「シミュレーション」を履修済であることが望ましい．未履修の者は事前に配布する教材を学習しておくことを強く推奨する．