同じ最適化問題であっても、その問題を表現する数理モデルは一意ではありません。採用 する数理モデルによって数学的な性質が異なり、求解性能に大きな差が生じることがあり ます。また、数理モデルの工夫に加え、初期解の設定やヒューリスティクスの活用などに よって、求解性能を改善できる場合もあります。
本コースでは、巡回セールスマン問題(Traveling Salesman Problem:TSP)を題材とし て、複数の数理モデルの実装と求解性能の比較、さらに求解性能を改善するための様々な アプローチを、プログラミング演習を通して学びます。
まず、TSPの代表的な3つの定式化をPythonとGurobiを用いて実装し、それぞれの求解性 能を比較します。さらに、数理モデルの強化やヒューリスティクスの活用による求解性能の改善、コールバック関数を用いた暫定解の改善や切除平面法の実装にも取り組みます。
これらの演習を通じて、数理モデルの構築から求解性能の評価、モデルや解法の改良に至 る一連のプロセスを体験できます。題材はTSPですが、他の数理最適化問題にも応用可能 な考え方や技術を扱います。
受講にあたっての前提知識
本コースは、GurobiプログラミングIIコースの内容を前提としておりませんが、数理最適化とGurobi Python APIの基礎的な知識をお持ちの方を対象としています。
数理最適化モデルの目的関数や制約式を理解できること
TSPの定式化を読み解くための基礎的な数理知識があること
Pythonの基本的な文法と、Gurobi Python APIを用いたモデル構築・求解を理解していること
主な内容
TSPの代表的な定式化と実装
・Dantzig–Fulkerson–Johnson(DFJ)の定式化
・Miller–Tucker–Zemlin(MTZ)の定式化
・Single-Commodity Flow(SCF)定式化
・各定式化のPythonによる実装と求解性能の比較求解性能を改善するためのアプローチ
・緩和問題の強化による数理モデルの改良
・ヒューリスティクスによる初期解の生成と設定
・最適化途中で得られる暫定解に対するヒューリスティクスの適用Gurobiのコールバック関数の活用
・コールバック関数の基本的な仕組みと利用方法
・最適化途中における暫定解・緩和解の取得
・ヒューリスティクスによって改善した解のソルバーへのフィードバック切除平面法によるTSPの求解
・部分巡回路除去制約を動的に追加する切除平面法最適化と制約追加を繰り返すアルゴリズムの実装
・コールバック関数とLazy Constraintを利用した切除平面法の実装
注意事項
トレーニング用途限定の単一マシン向けライセンスをご用意いたします。
本トレーニングの内容には、計算サーバーの構成では利用できないAPIが含まれるため、単一マシンでGurobiを実行できる環境でのご参加を推奨します。
トレーニングはWindows OSを前提としております。製品サポート範囲であれば他のOSにてご参加いただく事も可能ですが、環境によって異なる起動方法・操作・設定・画面に関しましては、当日は説明いたしかねます。
Python言語による演習が含まれます。GurobiのPythonAPIをお手元の実行環境にインストールしたPCにてご参加ください。
PythonへのGurobiインストールについてはGurobiをPythonへインストールするには？をご覧ください。
■ キャンセルポリシー
有料トレーニングのキャンセルは、弊社キャンセルポリシーに従い、以下の通りキャンセル料が発生いたしますのでご注意ください。
■ キャンセル料
連絡なしの不参加：受講料の100%
トレーニング3日前～当日：受講料の100％
トレーニング14日前～4日前：受講料の50％
*上記の日数は、弊社の営業日がカウント対象です。
*キャンセルに伴い返金が発生する場合は、お振り込み手数料は、お客様のご負担になります。
■ 各トレーニングについて
終了した各トレーニングの次期開催日等に関しては、弊社までお問い合わせください。
