Pythonによる最適化　第2回

オクトーバースカイ社にメルマガを依頼されたのでその草稿．第1回はクライアントの了承待ちです．

前回はPythonのモジュールPandasを紹介した．Pandasはデータ解析ライブラリであり，Excelで処理できない大規模データも扱うことができる．筆者よく使う他のライブラリ（モジュール）には以下のものがある．

1. matplotlib   http://matplotlib.org/
グラフ描画モジュール．これに含まれるpylab インターフェイスは，商用のMATLAB と同じような機能を持つ．

2. networkX    http://networkx.github.io/
グラフ・ネットワーク関連のモジュール．

3.  SciPy        http://www.scipy.org/
様々な科学技術計算のための実装を含むモジュール．

今回は，networkX を紹介するとともに，数理最適化ソルバーGurobiの融合について考えていこう．

networkXは大規模なネットワークの描画や解析に特化したモジュールである．筆者はネットワークの描画機能を用いることが多いが，ネットワーク関連のアルゴリズムも最近増えてきており，最適化にも用いることができる．

ちょっと前提になる知識について解説しよう．最適化問題は，多項式時間で解ける簡単な問題のクラス（Pと呼ばれる）と難しい問題のクラス（NP-困難と呼ばれる）に分けられる．networkXで解けるのは主にクラスPに含まれるネットワーク型の問題群であり，最短路問題，最小木問題，最小費用流問題，マッチング問題などである．一方，GurobiはNP-困難である混合整数計画問題を解くことができる．最小費用流問題は線形計画問題として定式化できるので，Gurobiを用いても解けるが，networkXではネットワーク構造を利用した専用の解法を用いているので多少高速である．

実際の大規模数理最適化問題をそのまま定式化しても解けない場合でも，問題の構造を利用すると解けるようになることがままある．過去，研究者の対象はそのような問題であり，ラグランジュ分解法，ダンツィーク・ウォルフの分解法，ベンダーズの分解法など様々など方法が適用されてきた．これらの分解法と名付けられたテクニックは，大規模で解けない問題を「解ける」構造をもつ小さな問題群に分解するものである．ここで，分解された子問題は比較的容易に解けることが重要である．解ける問題の代表例がnetworkXに搭載されているネットワーク型の問題である．したがって，大規模問題の構造を分析し，ネットワーク型の子問題をもつなら，networkXで，そうでない部分はGurobiで解くようにし，全体を分解法の基本原理で統合すれば良い．

ダンツィーク・ウォルフの分解法は列生成法とも呼ばれ，大規模な実際問題を解決する際に役に立つ．たとえば，船舶やトラックのスケジューリング問題において，列生成法を適用すると，以下の問題が主問題になる．

主問題：
最小化：選択されたルート（列）の費用の合計を最小化
条件：各顧客（仕事，荷物）が少なくとも１つのルート（列）で処理される

ここで子問題は，船舶（トラック）ごとに顧客を巡回するルート（列）を生成する問題になる．これはパスを列挙する問題になり，networkXを用いることによって解くことができる．主問題は大規模な線形計画問題になるのが，Gurobiなら容易に解くことができる．追加するルート（列）がなくなった時点で，整数条件を付加して再求解する必要があるが，この手のタイプの問題（集合分割問題）は双対ギャップが小さいことが多いので，Gurobiを用いれば，良好な近似解を短時間で求めることができる．