実際の最適化問題を瞬時に解く方法

比較的簡単な実際の数理最適化問題ならpandasとgurobi (or mypulp)で瞬時に解くことがでいる。私流の方法を紹介する。

ほとんどの実際問題のデータはExcelで渡される。このままxlwingsなどで読むことも可能だが、csv経由が早い。csvファイルに保存するときにutf-8とエンコーディングを指定すれば、pandasのread_csvで簡単に読める。

古いOfficeだとutf-8の指定ができないこともある。その際には、encodingk引数を"shift-jis"に設定すれば良い。この辺りは、英語圏の人たちは気にしないので、翻訳されたpandas本だけでは足りない．かといってPython2系ような悪夢は覚える必要はない．Pythonn３では全部utf-8で扱うことにして，周辺（Excelなど）をそれにあわせれば良いのだ．

また読み込んだデータを確認したら，小さな問題例を作っておく．以下では，まずは小さい問題でモデルを作成し，うまく動いたことを確認してから，本番問題例を入れる．しばしばはじめから本番問題例で開発する人たちを見かけるが，これが開発のスピードを遅らせる要因の1つであると考えられる．ここまでのコードはこんな感じだ．

import pandas as pd
df = pd.read_csv("ファイル名.csv")
small = df.iloc[0:10,:]
small.head()

pandasのデータフレームで前処理をしたら、そのままvaluesでNumPyの配列に落としてしまうのが簡単だ。ベクトルや行列は最適化モデルで使うcとかAなどの変数に保管しておく。しばしば、あとで見たときにわかりやすいためと言って長い名前を使う人もいるが、モデルを定式化したときの記号そのままの方がわかりやすいし、タイピングも速い。簡単なモデルの場合には簡略化された記号、複雑なモデルのときには分かりやすい名前と区別して使えば良い。ついでにデータの行数と列数も覚えやすい記号（mとかnに）保管しておく．コードはこんな感じだ．

A = df.values
m = len(df)
n = len(df.columns)
print("m=",m,"n=",n)

次に、準備しておいた小さな問題例を用いて，Gurobiもしくは私が作ったmypulp (gurobipyと同い文法でpulp経由で無料ソルバーを呼び出して使える）でモデル化する。modelをテキストファイルに変換してモデルがあっているかどうかをきちんと確認しておく。小さな問題例にしたのはそのためだ。いきなり大きなものを入れるとこの部分の確認が面倒になるし、時間もかかる。できれば、最適化の結果も綺麗に出力できるようなプログラムも書いておく。コードの一部はこんな感じになる．

model = Model()
x = {}
for i in range(m):
   for j in range(n):
       x[i,j] = model.addVar(name=f"x({i},{j})", vtype="B")
 
for i in range(m):
   model.addConstr( quicksum( x[i,j] for j in range(n)) == 1 )  
   
for j in range(n):
   model.addConstr( quicksum( A[i][j]* x[i,j] for i in range(m)) == 右辺 )

model.setObjective( 目的関数, GRB.MAXIMIZE)

このとき結果はデータフレームに入れて、to_csv()でcsvファイルに保管できるようにしておく。ただし出力されたテキストファイルはutf-8であるので、そのままExcelで読むと文字化けする。BOM付きに変換すればutf-8のままExcelが解釈してくれるので、ノートパッドなどの簡易エディタで読み込んで、保存すれば大丈夫だ。

一番厄介なのは（紙ベースで）定式化を記述する部分であるが、ここはアートだ。また本番問題例で時間がかかりすぎるときに、計算時間を短縮するための工夫もアートに近い。そのうち本にまとめてみようかと思う。