Pythonによる最適化　第1回

筆者は，最適化に関連した実際の問題の解決を依頼されることがままある．ここでは，なるべく短時間に実装し，問題解決をするためのテクニックについて，例を通して解説する．使うのは，Python言語とPythonのデータ解析・可視化モジュール群と最適化ソルバーである．

例として学生を寮の部屋に割り振る問題を考える，この問題は学生と部屋のマッチング問題であるが，同じ部屋に割り当てられた学生同士の相性を考慮することにする．これは二次割り当て問題の一種になるので，かなりやっかいな問題である．
 
データはExcelファイルで与えられる場合が多い．まず，Excelファイルのデータをcsv（カンマ区切りのテキストファイル）で保存する．PythonではExcelファイルから直接データを読み込むモジュールもあるが，安全のためにはcsvが良い．保存したデータは，部屋にすでに割り当てられている学生を表すデータ(roomfix.csv)と学生同士の相性を表すデータ(distance.csv)である．

これをPythonで読み込んでデータ構造を組み立てる必要がある．筆者はデータ解析モジュールPandasを用いることが多い．Pandasは R言語（S言語の無料版）や高価なデータ解析専用システムと同じようなことを，より高速にPython内でするためのモジュールである．いわゆる最近流行のビッグデータの解析などはPandasを使えば容易に（無料で）できるのだ．

データの読み込みは以下のわずか3行である．

import pandas as pd
d   =  pd.read_csv("distance.csv")
fix  =  pd.read_csv("roomfix.csv")

最初の行でpandasモジュールをpdという名前で読み込み，以下の2行でcsvファイルを読み込みd,fixという2つのデータフレームを作成している．ここでデータフレームはExcelのシートのようなものである．まずは，データの概要を統計値やプロットによる可視化で確認し，欠損値の有無を確認した．これらは各々1行のコマンドでできる．その後で，最適化のためのデータ構造を組み立てる．より大規模なプロジェクトの場合にはクラスを作ったりするが，ここでは簡単のため2次元配列として処理し，学生や部屋も0から始まる整数値で表すことにした．

D  = d.values    #distance matrix
Fix= fix.values  #fixed students; Fix[room][student]=1 if student was assigned to room
numRooms      = len(fix)
numStudents    = len(d)
numFixStudents = len(Fix[0])

まず，データフレーム(d,fix)オブジェクトに対するvaluesメソッドで，2次元配列(D,Fix)を抽出している．その後で，部屋数，学生数，部屋が固定されている学生数を設定している．

続いてモデル化に必要な「集合」を定義する．ここでは，すべて番号で処理するので，Pythonのrange関数を用いて，以下のように整数のリストを生成する．

Room    = range(numRooms)      
Student = range(numStudents)   
FixStudent  = range(numFixStudents)       
FreeStudent = range(numFixStudents,numStudents)

これでソルバーにかける準備が整った．定式化は文章で書くと以下の通りである．

最小化：同じ部屋に割り当てられた学生同士の距離の合計
条件：部屋に含まれる学生数の上下限
　　　学生は必ず何れかの部屋に割り当てる

専用のアルゴリズムを作成するのではなく，ソルバーにかけることで，付加条件にも容易に対応できる．実際に，留学生は同じ部屋にあまり集めたくないという条件も後から出てきたがが，追加分の実装は打ち合わせ中に数分でできた．

今回は簡単な事例を紹介したが，大規模なプロジェクトでも手順は同じである．Pythonは柔軟な言語であり，様々なモジュールが無料で公開されているので，すべてが同一の言語内で処理できる．GurobiはPythonを標準のモデリング環境としており，モデル化も比較的容易である．詳細は拙著「あたらしい数理最適化」（近代科学社）を参照されたい．