理工学部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 | 2023 |
| 授業コード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]
This class deals with practical solution to combinatorial optimization problems.
[Learning objectives]
Learn how to model combinatorial optimization problems as mathematical optimization problems, and how to solve them by computer.
[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:
assignment (40%), class contribution (30%), advanced assignment (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]：ナップサック問題（理論）
ナップサック問題の計算複雑度と，整数計画問題としての定式化
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]：ジョブショップスケジューリング（実装）
NP困難問題としてのジョブショップスケジューリング問題を，混合整数計画問題として定式化して解く
14[対面/face to face]：PERT，最長経路問題（実装）
PERT問題を最長経路問題の一つとして表現して解く
授業時間外の学習（準備学習・復習・宿題等）Work to be done outside of class (preparation, etc.)
・本授業の準備・復習等の授業時間外学習は、4時間を標準とする．
・理論パート，実装パートともに，大テーマ終了時に提出課題が課せられるので，指定された期限までに提出する．
テキスト（教科書）Textbooks
指定せず，教材を授業支援システム経由で配布する．
参考書References
必要に応じて紹介する．
成績評価の方法と基準Grading criteria
理論パート50%，実装パート50%の配分で，それぞれのパートは以下で評価する
理論パート：
提出課題 40% (20点)，平常点 30% (15点)，発展課題 30% (15点)
実装パート：
提出課題 40% (20点)，平常点 30% (15点)，発展課題 30% (15点)
学生の意見等からの気づきChanges following student comments
担当教員交代初年度のため，なし．
学生が準備すべき機器他Equipment student needs to prepare
・極力貸与ノートPCを持参すること．実装パートの週は必須である．
・MATLABが動作することを事前に確認しておくこと．初めて使用する者は，ライセンス認証が必要である．
その他の重要事項Others
・２年次秋学期科目「シミュレーション」を履修済であることが望ましい．