同一の問題を数理計画問題として解こうとしたときに、それを実現する数理モデルは、一意ではありません。採用する数理モデルによって、求解性能が大きく変わってくることも多々あります。

本コースでは、プログラミングを通して様々な数理モデルおよびアプローチを試すことで、 求解性能を向上させながらアプリケーションを構築していく開発の流れをご紹介します。また、巡回セールスマン問題（Traveling Salesman Problem ：TSP）を例に、代表的な数理モデルもいくつかご紹介します。それらの定式化を実際に最適化プログラムに落とし込み、その求解性能の違いを観察していきます。また、切除平面法を用いたアルゴリズム的な解法もご紹介します。その実現のためにGurobiのコールバック関数の機能を活用します。

上記の内容を数理最適化ソルバーGurobiおよびオブジェクト指向型スクリプト言語Pythonを用いてプログラム化していく流れを、演習を交えながら体験できるコースです。

また、TSPを用いるため、TSPのモデリングを読み解くための数理的な知識およびGurobi Pythonによるモデル作成の基礎的な知識をお持ちであることも前提としています。

本コースには、以下の内容が含まれます。

TSPの代表的な定式化

• Dantzig-Fulkerson-Johnsonの定式化

• Miller-Tucker-Zemlinの定式化

• Single-commodity flow定式化

各定式化の実装：TSPを解くための複数の定式化のプログラム実装

• 各定式化の求解プログラムコーディング

• 各定式化の求解性能の比較

発展的な内容：TSPを解くためのより発展的なアプローチ

• 式の強化によるモデル改良

• ヒューリスティクスによる暫定解改善

• 切除平面法によるDantzig-Fulkerson-Johnsonの定式化の実現

Gurobiのコールバック関数

• 最適化途中における暫定解の取得

• 最適化途中における解のフィードバック

• コールバック関数を用いた切除平面法

注意事項

• トレーニング用途限定の単一マシン向けライセンスをご用意いたします。

• 本トレーニングの内容には、計算サーバーの構成では利用できないAPIが含まれるため、単一マシンでGurobiを実行できる環境でのご参加を推奨します。

• トレーニングはWindows OSを前提としております。製品サポート範囲であれば他のOSにてご参加いただく事も可能ですが、環境によって異なる起動方法・操作・設定・画面に関しましては、当日は説明いたしかねます。

• Python言語による演習が含まれます。GurobiのPythonAPIをお手元の実行環境にインストールしたPCにてご参加ください。

• PythonへのGurobiインストールについてはGurobiをPythonへインストールするには？をご覧ください。