並木 誠
あたらしい数理最適化: Python言語とGurobiで解く
久保 幹雄, ジョア・ペドロ・ペドロソ, 村松 正和, アブドル・レイス 著
近代科学社, 2012年
12月。卒論、修論の追い込みの時期である。評者も「数理最適化とその応用研究」という看板を掲げ、学生の指導にあたっている。理論よりは食いつきもいいので、学生にはより実践的なテーマを与えることが多い。すると学生はしばしば、解かねばならない具体的な数理最適化問題に直面する。線形計画問題を筆頭に、整数計画、最施設配置問題、グラフ最適化問題など様々である。さてソルバーは何にしようか。エクセル、GLPK、lpsolve、Mathematica等、数理最適化問題を扱えるソフトウェアは、多々あるが、すべてを教えなければならないか。しかも、それぞれの数理モデルとしての表現は、少しずつ違っているので、最適化エンジンだけ用意すればいいという訳ではなく、入出力などインターフェイスの部分は独自にプログラミングが必要なんてこともある。こんな状況で、本書が扱っている Gurobi + Python という環境は強力な助っ人である。Pythonという言語は、著書中に「お気楽」言語とあるように、比較的敷居が低いプログラミング言語で、初心者に優しい。加えて Gurobi という汎用の数理最適化ソフトウェアがアカデミックライセンスで、ほぼ無制限に利用できるようだ。有償ソフトウェアのお試しの場合、変数や制約式の数に制限があったりするので、ありがたい話である。 このような環境は、何らかの具体的な数理最適化問題を解かねばならない実務家にも役に立つはずである。
本書は、プログラミング言語 Pythonをベースにした汎用数理最適化ソルバー Gurobi（以下Gurobi/Python）を使って最適化問題を解くための実践の書である。実践の書であるので、読んだだけでは面白みがない。Gurobi/Pythonを導入したパソコンを前にして、本書の段取りに従い、実際に最適化問題を解いてみるとよい。実践の書だからといって、単なるマニュアル本でもない。現実問題を解決する場合、数理モデル化、最適解を求めること、現実の問題にフィードバック、からなるサイクルを遂行しなければならない。最適解を求める部分は、既存のソフトウェアに任せ、ブラックボックス化することも可能であるが、知っておくとこれら一連の作業に非常に有益な知識がたくさんある。本書ではそれらが、「モデリングのコツ」や「欄外ゼミナール」などと称して随所にちりばめてある。著者らの長年の研究活動から得られた貴重な知識も入っており、これを読んだだけでも得した気分になる。
本書の構成は以下の通りである。まず第１章では、代表的な数理最適化問題をGurobi/Pythonではどのように解くのかということを概説している。この第１章は通読すべきであろう。Gurobi/Pythonで用意されているデータ構造（オブジェクト）を用いたモデル化、線形最適化問題における双対の概念、実行可能解（条件を満たす解）が存在しないモデルに対する対処法などを、簡潔に説明してある。また、この章で取り上げられている例題は、例えば、整数計画問題の鶴、亀、蛸算など、非常に親しみやすいものとなっており、数理最適化の初学者でも、一通りの作法が習得できるよう考慮されている。
第2章〜10章では、施設配置問題、グラフ最適化問題、スケジューリング問題などの、より実践的な最適化問題が取り上げられている。それぞれの問題には、モデル化の方法もいくつか存在し、解くためのアルゴリズムも定式化によって変わってくる。様々な定式化の方法やアルゴリズムを熟知した著者らが、Gurobi/Pythonの持つ様々な機能を最大限に生かした解法がこれでもかというくらい披露されている。この部分は全部読む必要はない、いやおいそれと読めないかもしれない。興味がある問題を見つけ、その章を時間をかけて学習すればよい。そのための下準備は、第１章を通読することによって出来ている。
最後に付録として、Python一般の概説、Gurobi/Pythonの概説、制約最適化ソルバーSCOP概説、スケジューリング最適化ソルバーOptSeq概説が書かれている。特に最後の２つは、Gurobi/Pythonでは扱いにくい問題に特化したPythonベースのソルバーに関する説明である。なんとも至れり尽くせりである。
もし読者が、解かなければならない数理最適化問題を持っており、どうしたらいいか解らない場合は、まず本書に相談してみよう。似たような、あるいはそのものズバリの問題があるかもしれない。かく言う評者は、大学院生とともに、本書とにらめっこし、とある最適化問題を解こうとGurobi/Pythonにどっぷり浸かっている。
なみき まこと
東邦大学理学部情報科学科 准教授
[Article: J1307B]
(Published Date: 2014/02/11)