備忘録＠Python ORセミナー: Pulp


数理最適化モデリングのためのライブラリ．
`Gurobi`, `CBC`, `GLPK`などのソルバが使用可能．
いまいち自分が最適化についてわかってないから，今後勉強予定．

# 数理モデルの作成手順

数理モデルで問題解決をする手順は以下のとおり．
※（）はpulpにおけるクラス名．

 1. 数理モデル（LpProblem）を作成する
 1. 変数（LpVariable）を追加する
 1. 目的関数の式（LpAffineExpression）を追加する
 1. 制約（LpConstraint）を追加する

## 数理モデル：LpProblem

`LpProblem(name='NoName', sense=LpMinimize)`

- `name`: 数理モデル名．Defaultで`NoName`になる．
- `sense`: 最小化（LpMinimize）か最大化（LpMaximize）のどちらか．

## 変数：LpVariable

`LpVariable(name, lowBound=None, upBound=None, cat='Continuous', e=None)`

- `name`: 変数名
- `lowBound`: 下限
- `upBound`: 上限
- `cat`: 変数の種類
    * `LpContinuous`: 連続変数
    * `LpInteger`: 整数変数
    * `LpBinary`: バイナリ変数
* `e`: カラムベースモデルに使用（よくわからない）


## 目的関数：LpAffineExpression

変数を使って「`x+2*y`」のように作成可能
式に後から項を追加するのも可能
目的関数は、「`m += 式`」のように指定する(ただし、`m`は数理モデル)


## 制約：LpConstraint

変数を使って「`x+y<=1`」のように作成可能
制約の左辺に後から項を追加するのも可能
制約は、「`m += 式 <= 右辺`」のように指定する

## その他

よく使うらしい関数
`value()`: 変数の値を取り出します
`lpSum()`: 項の和を求めます
`lpDot()`: 2つのリストの内積を求めます

チートシートは[こっち](http://mathopt.sakura.ne.jp/pythonpulp.html)

# ナップザック問題を解いてみる

## よくある最適化問題

あるナップザックに出来る限り多くの品物を入れる
そのとき：

- ナップザックに入れれる重さは最大で600グラム

みたいに制約がある．で，どうする？

## 定式化する

品物$s_i$を入れる→$v_i=1$
品物$s_i$を入れない→$v_i=0$

```math
\begin{array}{cl}
\max & \sum_i{s_i \ v_i} \\
\mbox{subject to} & \sum_i{s_i \ v_i} \leq C \\
                 & v_i \in \{0, 1\} ~ \forall i
\end{array}
```

## pulpで実装する

```pycon
>>> # 品物の重さ
>>> s = [128, 108, 34, 53, 71, 224, 299, 181, 336, 15]
>>> # ナップザックの最大積載量
>>> C = 600
>>> # ライブラリ準備
>>> from pulp import LpProblem, LpVariable, LpMaximize, LpBinary
>>> rn = range(len(s))
>>> # モデル準備
>>> m = LpProblem('knapsack', LpMaximize)
>>> # 変数(i番目の品物をいれるかどうかの0/1)
>>> v = [LpVariable('v%d' % i, cat = LpBinary) for i in rn]
>>> # 目的関数
>>> m += lpDot(s, v)
>>> # 制約
>>> m += lpDot(s, v) <= C
>>> # 解く
>>> m.solve()
>>> # 出力
>>> print(LpStatus[m.status], sum(s[i] * value(v[i]) for i in rn))
>>> print([s[i] for i in rn if value(v[i]) > 0.5])
Optimal 600.0
[108, 34, 53, 224, 181]
```

# その他の最適化問題

他の最適化問題も定式化すれば解ける（みたい）

## 施設配置問題（p-メディアン）

施設候補の中からp個を選び、需要点から施設への距離の総和を最小化する問題

例

* 避難所の候補から4カ所の避難所を選び、住民から避難所への移動距離の総和を最小する (p == 4)
* $x_{ij}$ を住民jが施設iに避難するかどうかを、$y_i$を施設iを選ぶかどうかを表すとする(距離は$d_{ij}$)

### 定式化

```math
\begin{array}{cl}
\min & \sum_i{\sum_j{d_{ij} \ x_{ij}}} ~ ~ ~ ~ (1) \\
\mbox{subject to} & \sum_i{y_i} = p ~ ~ ~ ~ (2) \\
                 & \sum_i{x_{ij}} = 1 ~ \forall j ~ ~ ~ ~ (3) \\
                 & x_{ij} \leq y_i ~ \forall i, j ~ ~ ~ ~ (4) \\
                 & x_{ij} \in \{0, 1\} ~ \forall i, j
\end{array}
```

## 数独

よくあるあれ．

* 制約を満たせばいいから、目的関数は設定しない
* 行i、列jの位置に数字kを使うかどうかを0/1変数で表す
 * v[i,j,k]で表す
* 制約
 * 縦i、横jの位置で、いずれか１つだけの数字を使用可能 (1)
 * 各行iで数字jは、1つだけ使用可能 (2)
 * 各列iで数字jは、1つだけ使用可能 (3)
 * 3$\times$3の中で、数字jは、1つだけ使用可能 (4)

 ### 定式化

 ```math
\begin{array}{cl}
\min & \mbox{no objective function} \\
\mbox{subject to} & \sum_k{v_{ijk}} = 1 ~ \forall i, j ~ (1)\\
                 & \sum_k{v_{ikj}} = 1 ~ \forall i, j ~ (2) \\
                 & \sum_k{v_{kij}} = 1 ~ \forall i, j ~ (3) \\
                 & 3\times3のマスについても同様 ~ (4) \\
                 & v_{ijk} \in \{0, 1\} ~ \forall i, j, k
\end{array}
 ```

## その他の最適化問題

|カックロ|ののぐらむ|美術館|ナンバーリンク|覆面算|
|:-:|:-:|:-:|:-:|:-:|
|不等式|ビルディングパズル|ウォールロジック|波及効果|ナンバースケルトン|
|スリザーリンク|四角に切れ|ましゅ|橋をかけろ|のりのり|
|ブロックパズル|タイルペイント|因子の部屋|黒どこ|推理パズル|
|ひとりにしてくれ|へやわけ|ペイントエリア|数コロ|パイプリンク|
|クリーク|アイスバーン|サムライン|カントリーロード|カナオレ|
|フィルマット|シャカシャカ|ヤジリン|ぬりかべ|ホタルビーム|
|ステンドグラス|さとがえり|スケルトン||ニコリより名称引用|