Gurobi / Python で最適化

• Gurobi は Mac OS X デフォルトの Python しかサポートしない(参考)．まずは Python のバージョンを確認：

  $ which python                  # Python へのパスが
  /usr/bin/python                 # /usr/bin/python となっていることを確認 
  $ python --version              # Python のバージョンが
  Python 2.7.2                    # 2.7.2 になっていることを確認
  

• もし homebrew などで別のバージョンの python を入れてしまっている場合は Gurobi が正常に機能しないので unlink (一時停止) か uninstall (消去)しておく．
  • unlink (一時停止)する場合:

    $ brew unlink python            # /usr/loca/bin/python を一時的に使わなくする
    

  • unlinstall (消去)する場合

    $ brew uninstall python            # /usr/loca/bin/python を完全に消去する
    

以下の情報は http://www.gurobi.com/products/licensing-and-pricing/academic-licensing に基づい ている．

新しいパッケージをダウンロード→インストールし，ライセンスファイルを /Library/gurobixxx/ に移動(もしくはコピー)する．ライセンスの更新は不要．

http://joernhees.de/blog/2013/06/08/mac-os-x-10-8-scientific-python-with-homebrew/ に紹介されているパッケージを入れる．ただし，このサイトでは python の最新版を homebrew でインストールすることを前提としてるが，それだと Gurobi が動かない．

そこで，ここでは，Mac OS X デフォルトの Python 用の pip をインストールし， それを使ってパッケージを追加する方法を述べる．

また，pip でインストールできる(i.e. Python関係)パッケージは極力 pip を用いる こととした．

1. pip のインストール pip は Python 用のパッケージインストーラである．homebrew 版 python には pip も含まれるが，Mac OS X デフォルト版にはそれが無いのでインストールする．

   sudo easy_install pip
   

2. homebrew のリポジトリに homebrew/science と samueljohn/python を追加する：

   brew tap homebrew/science # a lot of cool formulae for scientific tools
   brew tap samueljohn/python
   brew update && brew upgrade
   

   samueljohn/python 内の numpy, scipy は近いうちに homebrew/science に移動 するそうなので注意(参照)．

   2013/10/07 現在，pip install scipy とすると swig が無い，と言われてエラー になるので samueljohn/python を利用する方針に修正．

3. 順番に色々入れていく：

   # 仮想環境構築
   sudo pip install virtualenv nose     # virtualenv は Python の仮想環境を構築するもの．nose は Python の単体テストを簡単にできるように拡張したもの
   
   # インタラクティブ・モードの強化
   brew install qt pyqt            # Qt は GUIツールキット．pyqt はその Python バインディング
   brew install zmq                # ZeroMQ は軽さがウリのMQ(message queuing, アプリケーション間データ交換方式の1つ)
   sudo pip install ipython[zmq,qtconsole,notebook,test] # iPython は Python のインタラクティブ・モードを進化させたもの
   
   # デバッグ出力
   sudo pip install q                   # q はお手軽なデバッグ出力用のパッケージ
   
   # 科学技術計算用(Numpy, Scipy)
   # pip install scipy が通らなくなったので，homebrew からインストールするようにした
   brew install numpy               # NumPy は Python で科学計算を行うための基本パッケージ
   brew install scipy --with-openblas              # SciPy は科学・工学用モジュール群
   # 数式処理，グラフのプロット
   sudo pip install sympy               # SymPy はシンボリックな数式処理のためのライブラリ
   sudo pip install matplotlib          # matplotlib は Python で2Dグラフをプロットするためのライブラリ
   
   # ネットワーク分析
   sudo pip install networkx           # NetworkX はネットワーク分析用パッケージ
   sudo pip install graphillion        # Graphillion は「数え上げお姉さん」を救うパッケージ
   
   # 画像処理
   sudo pip install pillow              # Pillow は Python の画像処理ライブラリ
   brew install imagemagick graphviz # imagemagick は画像の操作・表示のためのソフトウェア．graphviz はグラフ描画ソフトウェア．
   brew install cairo --without-x    # cairo はベクトルベースのフリーの2Dグラフィックスライブラリ
   brew install py2cairo             # cairo 用の python 2.x バインディング
   
   # データ解析，自然言語処理
   sudo pip install pandas nltk         # pandas はデータ解析ライブラリ，nltk は自然言語処理ツールキット，
   

4. Homebrew でインストールした Python モジュールへのパスを通す 組み込み Python 下の pip でインストールしたライブラリと homebrew からインストー ルした Python ライブラリを混在させる場合には，環境変数 PYTHONPATH に homebrew 下の site-packages へのパスを追記する必要がある．
   • ~/.bash_profile に 以下を追加する：

     export PYTHONPATH="/usr/local/lib/python2.7/site-packages:$PYTHONPATH"
     

   • ターミナルで以下を実行する

     $ source ~/.bash_profile
     

ターミナルから以下を入力：

python

Python が起動し，プロンプトが >>> に変わる．以下，順に入力していく：

>>> import gurobipy as grb                                      # Gurobi 用パッケージを grb という名前でimport
>>> m = grb.read('/Library/gurobi560/mac64/examples/data/coins.lp') # デフォルトのインタラクティブ・モデルではファイル名のTAB補完は効かない
Read LP format model from file /Library/gurobi560/mac64/examples/data/coins.lp # 読み込みファイル名，
Reading time = 0.00 seconds     # 読み込みにかかった時間などが表示される
(null): 4 rows, 9 columns, 16 nonzeros
>>> m.optimize()                                                # 最適化メソッドを呼び出す
Optimize a model with 4 rows, 9 columns and 16 nonzeros             # 最適化された結果が表示される
Found heuristic solution: objective -0
Presolve removed 1 rows and 5 columns
Presolve time: 0.00s
Presolved: 3 rows, 4 columns, 9 nonzeros
Variable types: 0 continuous, 4 integer (0 binary)

Root relaxation: objective 1.134615e+02, 4 iterations, 0.00 seconds

    Nodes    |    Current Node    |     Objective Bounds      |     Work
 Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time

     0     0  113.46154    0    1   -0.00000  113.46154     -      -    0s
H    0     0                     113.4500000  113.46154  0.01%     -    0s

Explored 0 nodes (4 simplex iterations) in 0.00 seconds
Thread count was 8 (of 8 available processors)

Optimal solution found (tolerance 1.00e-04)
Best objective 1.134500000000e+02, best bound 1.134500000000e+02, gap 0.0%
>>> for v in m.getVars():   # 「:」を入力した後改行すると，次のプロンプトが ... になる
...:     print v.varName, v.X   # print の前には TAB を押してインデントが必要
...:                         # 何も入力しないで改行すると for ブロックを抜られる

すると以下が表示されるはず:

Pennies 0.0
Nickels -0.0
Dimes 2.0
Quarters 53.0
Dollars 100.0
Cu 999.8
Ni 46.9
Zi 50.0
Mn 30.0

Python のインタラクティブ・モードを終了するにはCtrl-D を入力．

>>>                                 # ここで Ctrl-D とすると
$                                   # Python モードが終了し，もとのターミナルのプロンプトに戻る

次のようなネットワークを対象として起点(a)から終点(d)まで 単位の製品を輸送 する最小費用流を求める問題を考える(ただし，各リンクの は輸送費用， は容量を表す)．

インタラクティブ・モードで逐一コマンドを入力するのは面倒．そういう場合は，以下の ようなスクリプト・ファイルに記述して呼び出せばいい．

#! /usr/bin/python
# *-* encoding: utf-8 *-*

# リンク集合
links = [('a','b'), ('a','c'), ('b', 'c'), ('b','d'),('c','d')]
# ノード集合
nodes = ['a', 'b', 'c', 'd']
orig = 'a'                      # 起点
dest = 'd'                      # 終点

# 各リンクの輸送費用
cost = dict(zip(links,[2,8,3,8,4]))
# 各リンクの容量
capacity = dict(zip(links, [10, 10, 3, 9, 8]))
# 起点から終点までの総輸送量
total_volume = 17

# Gurobi パッケージを grb という名前で import 
import gurobipy as grb
# print "%s:\t%8.4f" % (x[i, j].VarName, x[i, j].X)
m = grb.Model()
# 未知変数を x という辞書型変数に格納
x = {}
# addVar() という関数を用いてモデルに変数を追加する
for (i,j) in links:
    x[i, j] = m.addVar(vtype=grb.GRB.CONTINUOUS, name="x_{%s,%s}" % (i, j))
m.update()                  # モデルに変数が追加されたことを反映させる

# 目的関数を設定し，最小化を行うことを明示する
m.setObjective(grb.quicksum(x[i, j]*cost[i, j] for (i, j) in links))# 目的関数
m.setAttr("ModelSense", grb.GRB.MINIMIZE)

# 各ノードでのフロー保存則を追加する
b = {}                          # フロー保存則の右辺の定数を設定する
for n in nodes:
    if n == orig:
        b[n] = - total_volume
    elif n == dest:
        b[n] = total_volume
    else:
        b[n] = 0
    # ノードごとのフロー保存則
    # 行馬に「\」をつけると1つの行を複数行にまたがって記述できる
    m.addConstr(grb.quicksum(x[i, j] for (i, j) in links if j == n)\
                - grb.quicksum(x[i, j] for (i, j) in links if i == n) \
                == b[n], name="flow reservation at %s" % n)

# 各ノードでの非負制約と容量制約を追加する
for (i, j) in links:
    x[i, j].lb = 0.0
    x[i, j].ub = capacity[i, j]

# モデルに制約条件が追加されたことを反映させる
m.update()
m.write("mincostflow.lp")       # mincostflow.lp というファイルに定式化されたモデルを出力する

# 最適化を行い，結果を表示させる
m.optimize()
print "optimal value:\t%8.4f" % m.ObjVal
for (i, j) in links:
    print "%s:\t%8.4f" % (x[i, j].VarName, x[i, j].X)

Python からファイルを呼び出すには，ターミナルで

$ python sampleMCF.py

とすればよい．