2024年度 情報メディア創成学類 情報メディア実験A [M27]
2024年度 情報科学類 ソフトウェアサイエンス実験A（主専攻実験） [S-13]
「数理最適化：基礎と応用」
(Mathematical Optimization: Theory and Applications)
担当教員：
佐野 良夫 （ E-mail: sano_AT_cs.tsukuba.ac.jp ）
開講時期：
春学期ABC （水曜３・４限、金曜５・６限）
場所：
・実験、質問受付等：オンライン（各自のPC）
・初回内容解説、課題発表会：対面（3F815）
※ 初回（4/24）は、3F815（第三エリア 工学系学系F棟 8階 815）にて、実験の内容等について説明します。
※ 実験テーマの割り当てが決定したら、Microsoft Teams の実験のチームにメンバー追加しておきます。
2024年度は、TA (Teaching Assistant) は２人います。
実験時間中は、Microsoft Teams上でオンライン会議を開いて待機していますので、わからないことがあれば気軽に聞いてください。
また対面で直接質問したい場合もTAは対応できますので、連絡してください。
学生受け入れ人数：
10人（情報メディア創成学類） ＋ 10人（情報科学類）
本実験テーマでの目標：
・数理最適化問題として定式化されるような典型的な問題にはどのようなものがあるかを知る。
・問題のモデル化、定式化の手法を習得する。
・最適化ソルバー(Python+Gurobi/CPLEX) を使いこなし、実際に数理最適化問題を解けるようになる。
・最適化ソルバーの仕組みを理解する。
・数理最適化の応用を試みる。
2024年度 スケジュール（予定）：
（実験概要説明）
4/24(水)
（課題1に取り組む）
4/26(金), 5/1(水),
5/8(水), 5/10(金), 5/15(水), 5/17(金),
5/22(水) 12:15~ 第1回課題発表会
（課題2に取り組む）
5/24(金), 5/29(水), 5/31(金), 6/5(水), 6/7(金),
6/12(水), 6/14(金), 6/19(水), 6/21(金),
6/26(水) 12:15~ 第2回課題発表会
（課題3に取り組む）
6/28(金), 7/3(水), 7/5(金),
7/10(水), 7/12(金), 7/17(水), 7/19(金),
7/24(水) 12:15~ 第3回課題発表会
（最終レポート作成）
7/26(金), 7/31(水)
[8/7(水) 17:00 最終レポート締切]
実験内容：
最適化問題とは
与えられた条件下において最も良いものを選び出す問題であり、
数理最適化問題とは最適化問題を数学的に記述した問題である。
つまり、目的関数とその定義域を数学的に記述し、
目的関数の最大値/最小値を求める問題のことである。
本実験テーマでは、
汎用的な数理モデルの１つである整数計画問題を中心に数理最適化問題についての実験を行う。
より具体的には、以下の内容を扱う。
Ⅰ．最適化数理モデル：問題定式化と最適化ソルバーの利用
【目標】
様々な問題に対してその問題定式化の方法を学び、
最適化ソルバーを用いることによってそれらの問題を解くことができるようになる。
【実験内容】
・最適化ソルバー（
Python
+
Gurobi
/
CPLEX
etc.）
を使って整数計画問題を解く。（cf. テキスト [1], [2]）
・様々な定式化手法を習得し、解きたい問題を適切な数理モデルに定式化できるようにする。（cf. テキスト [2]）
・パズルを整数計画問題として定式化し、GurobiやCPLEXなどの整数計画ソルバーを用いて計算機実験を行う。（レポート課題１）
（パズルの例：
https://www.nikoli.co.jp/ja/puzzles/ ）
【テキスト】
[1]
「
データ分析ライブラリーを用いた最適化モデルの作り方
」
斉藤努（著）
（近代科学社） 2018年
[2]
「
あたらしい数理最適化 Python言語とGurobiで解く
」
久保幹雄・J.P.ペドロソ・村松正和・A.レイス（著）
（近代科学社） 2012年
（
「あたらしい数理最適化 GurobiとPython言語で解く」サポートページ ）
【レポート課題１】
パズルの定式化とそれに関する計算機実験
（注：数独は解説で扱いますので、課題のパズルは数独以外を選ぶこと。）
【課題１の発表・レポートに入れるべき内容】
１．どんなパズル問題を扱うか？
２．パズルのルールなどの紹介
３．パズルの定式化
４．実際に問題を解いた計算機実験の結果
５．まとめと課題
Ⅱ．最適化アルゴリズムの基礎：線形計画・分枝限定法・整数計画
【目標】
汎用的な最適化数理モデルである整数計画問題に対する最適化アルゴリズムについて理解する。
【実験内容】
・線形計画問題およびその解法（単体法）について理解し、実装する。（cf. テキスト [3] 第2章）
・ナップサック問題に対する分枝限定法を理解し、実装する。（cf. テキスト [3] 第3章）
・0-1整数計画問題ソルバーを作成する。（レポート課題２）
・テスト問題の解が正しく出力されるかどうか確認する。
・課題2_テスト問題 (7問)
【テキスト】
[3]
「
Pythonによる数理最適化入門
」
久保幹雄（監修）／並木誠（著）
（朝倉書店） 2018年
【レポート課題２】
0-1整数計画ソルバーの作成と計算機実験
（問題例の解が出力されるかどうかの確認、
あと問題サイズを変えたときの計算時間比較も行う。）
【課題２の発表・レポートに入れるべき内容】
１．実装したアルゴリズムの紹介
２．自分で工夫した部分について
３．テスト問題に対する計算機実験の結果
４．まとめと課題
Ⅲ．最適化理論の応用
【目標】
自ら解くべき問題を発見し、最適化理論を応用することで、問題解決ができるようになる。
【レポート課題３】
自分の興味がある数理最適化に関するトピックに関して、
詳しく調べ、理論の理解、アルゴリズムの実装、計算機実験
を行い結果をまとめよ。
【課題３の発表・レポートに入れるべき内容】
１．どのようなトピックを扱うか
２．理論的部分の紹介
３．自分で工夫した部分について
４．計算機実験の結果
５．まとめと課題
課題発表、成績評価：
レポート課題についての発表（3回）および最終レポートに基づき、成績を評価する。
第1回課題発表会
日時：2024/5/22 (水) 12:15~
場所：3F815（第三エリア 工学系学系F棟 8階 815）
時間：1人10分程度
発表内容：レポート課題１について
（前日までに発表スライド、実験コードを Teams で提出すること。）
第2回課題発表会
日時：2024/6/26 (水) 12:15~
場所：3F815（第三エリア 工学系学系F棟 8階 815）
時間：1人10分程度
発表内容：レポート課題２について
（前日までに発表スライド、実験コードを Teams で提出すること。）
第3回課題発表会
日時：2024/7/24 (水) 12:15~
場所：3F815（第三エリア 工学系学系F棟 8階 815）
時間：1人10分程度
発表内容：レポート課題３について
（前日までに発表スライド、実験コードを Teams で提出すること。）
実験最終レポート
2024/8/7 (水) 17:00 提出締切
（実験最終レポートは Teams で提出すること。）
(Last Update: 2024/04/17)