最適化問題入門　 錐最適化・整数最適化・ネットワークモデルの組合せによる Pythonによる問題解決シリーズ

サマリー

Pythonは、簡単に学べること、読みやすいコードを書けること、広範囲にわたるアプリケーションに使えることなどの、多くの優れた特徴を持つ汎用プログラミング言語となる。Pythonは、1991年にGuido van Rossumによって開発されている。

Pythonは、比較的新しい言語であるため、オブジェクト指向プログラミング、手続き型プログラミング、関数型プログラミング等の様々な効果的なプログラミング手法を利用することができる。また、多くのライブラリやフレームワークが用意されているため、Webアプリケーション、デスクトップアプリケーション、科学技術計算、機械学習、人工知能などの分野に広く使われている。さらに、クロスプラットフォームであり、Windows、Mac、Linuxなどの多くのオペレーティングシステムで動作するという特徴を持つ。Pythonは、インタープリタ言語であるため、コンパイルの必要がなく、REPL的な仕組みを持つため、開発サイクルが早くなる。

ここでは「最適化問題入門　-錐最適化・整数最適化・ネットワークモデルの組合せによる-Pythonによる問題解決シリーズ」を用いてpythonを用いた最適化手法について述べている。

今回は読書メモについて述べる。

最適化問題入門　 錐最適化・整数最適化・ネットワークモデルの組合せによる Pythonによる問題解決シリーズ

最適化とは、無数の選択肢の中から、目的にかなうものを選び出すことをいう。これは、ビジネス・工学・理学など、様々な分野で用いられる。

最適化では、数式を用いて最適な選択ができる。そして、その計算のためのソフトウェアも整備されている。ここでは、数式を用いて表現した最適化問題を、Pythonを用いて解く方法について述べる。

初めて出会った問題を数式でうまく表現するには、複数の典型的な問題を組み合わせることが有効となる。そのためには、典型的な問題と、それらの答えを求める方法を知っておくことが必要になる。

最適化問題には、現在の技術で解ける問題とそうでない問題がある。ここでは解ける問題として、錐線形最適化問題を中心に捉えた。錐線形最適化問題は、線形最適化問題(線形計画問題)を一般化したものとなる。線形最適化問題は最もよく用いられる最適化問題の一つであり、ソフトウェアも整備されている。その一般化である錐線形最適化問題を解くには、より多くの計算が必要となるが、最近ではかなり大規模な問題でも解けるようになっている。

整数の中から数値を選ぶような最適化問題は、組み合わせ的な難しさをもつ、ところが、ソフトウェア実装上の様々な工夫により、(理論的な保証は依然としてないものの)かなりのケースで答えが得られるようになってきている。そこで、ここでは、整数変数を含んだ錐線形最適化問題も、解ける問題として取り上げている。

また、解こうとする対象による分類として、5つの組み合わせ最適化問題を取り上げている。いずれも、様々な実務問題をモデル化する際に、便利に用いられるものとなる。これらの問題に対しては、一つの問題には複数の見方や解き方があることを示すために、複数のモデル化や解き方を示している。

またここでは、一つの同じ問題を複数の異なるパッケージで解くことも行われている。と期待問題を解くことが目的であれば、特定の手法/アルゴリズム/パッケージに拘る理由はない、様々なアプローチの中から、その場に最も適したものを使って目的を成し遂げる方が良い。

具体的な内容は以下のようになる。

第1章　Pythonで最適化を行うための環境構築
　　1.1 Pythonのインストール
　　1.2 パッケージのインストール
　　1.3 実行環境

第2章　数理最適化問題の分類方法
　　2.1 数式のかたちによる分類
　　　　　2.1.1 線形最適化問題
　　　　　　　　式
　　　　　　　　C∈ℝnはn次元の実ベクトル
　　　　　　　　x∈ℝnはn次元の実ベクトル
　　　　　　　　A∈ℝmxnはmxn次元の実行列
　　　　　　　　b∈ℝmはm次元の実ベクトル
　　　　　　　　x≥0は、xの各要素xiが非負であることを示す
　　　　　　　　線形最適化問題の解法
　　　　　　　　単体法(simplex method)
　　　　　　　　内点法(interior-point method)
　　　　　2.1.2 錐線形最適化問題
　　　　　2.1.3 混合整数最適化問題
　　2.2 解こうとする対象による分類
　　　　　2.2.1 集合分割問題
　　　　　2.2.2 ナップサック問題
　　　　　2.2.3 ネットワーク最適化問題
　　　　　2.2.4 巡回セールスマン問題
　　　　　2.2.5 配送計画問題

第3章　Pythonパッケージによる数理最適化問題のモデリング
　　3.1 線形最適化問題
　　　　　3.1.1 様々なモデリングインターフェへす
　　　　　3.1.2 PuLPの使い方
　　　　　3.1.3 Pyomoの使い方
　　3.2 錐線形最適化問題
　　　　　PICOSの使い方
　　3.3 ネットワーク最適化問題
　　　　　NetworkXの使い方
　　3.4 混合整数最適化問題
　　　　　PICOSの使い方

第4章　数式のかたちで分けられる最適化問題
　　4.1 線形最適化問題の解き方
　　　　　4.1.1 栄養問題
　　　　　4.1.2 列生成および切除平面
　　4.2 二次錐最適化問題
　　4.2.1 回転付き二次錐最適化問題
　　　　　4.2.2 ロバスト線形最適化問題
　　4.3 半正定値最適化問題の解き方
　　　　　4.3.1 最大カット問題に対する緩和
　　　　　4.3.2 多項式最適化
　　4.4 混合整数最適化問題の解き方
　　　　　4.4.1 緩和問題と凸包
　　　　　4.4.2 施設配置問題
　　　　　4.4.3 Perspectiveを用いた定式化

第5章　解こうとする対象による分類
　　5.1 集合分割問題の解き方
　　　　　5.1.1 0-1整数線形最適化問題としての定式化
　　　　　5.1.2 PuLPによるモデル化
　　5.2 ナップサック問題の解き方
　　　　　5.2.1 0-1整数線形最適化問題としての定式化
　　　　　5.2.2 分岐限定法
　　　　　5.2.3 動的計画法
　　5.3 ネットワーク最適化問題の解き方
　　　　　5.3.1 最短路問題の解き方
　　　　　5.3.2 最大流問題の解き方
　　　　　5.3.3 時間付き最短路問題の解き方
　　　　　5.3.4 OpenStreetMapによる道路データの利用
　　5.4 巡回セールスマン問題の解き方
　　　　　5.4.1 0-1整数線形最適化問題としての定式化
　　　　　5.4.2 PuLPとNetworkXによるモデル化
　　5.5 配送問題の解き方
　　　　　5.5.1 集合分割問題としての定式化
　　　　　5.5.2 PuLPによる列生成法の実装