数理最適化モデリングのためのライブラリ．
Gurobi, CBC, GLPKなどのソルバが使用可能．
いまいち自分が最適化についてわかってないから，今後勉強予定．
数理モデルの作成手順
数理モデルで問題解決をする手順は以下のとおり．
※（）はpulpにおけるクラス名．
- 数理モデル（LpProblem）を作成する
- 変数（LpVariable）を追加する
- 目的関数の式（LpAffineExpression）を追加する
- 制約（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つのリストの内積を求めます
チートシートはこっち
ナップザック問題を解いてみる
よくある最適化問題
あるナップザックに出来る限り多くの品物を入れる
そのとき：
- ナップザックに入れれる重さは最大で600グラム
みたいに制約がある．で，どうする？
定式化する
品物$s_i$を入れる→$v_i=1$
品物$s_i$を入れない→$v_i=0$
\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で実装する
>>> # 品物の重さ
>>> 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}$)
定式化
\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)
定式化
\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}
その他の最適化問題
| カックロ | ののぐらむ | 美術館 | ナンバーリンク | 覆面算 |
|---|---|---|---|---|
| 不等式 | ビルディングパズル | ウォールロジック | 波及効果 | ナンバースケルトン |
| スリザーリンク | 四角に切れ | ましゅ | 橋をかけろ | のりのり |
| ブロックパズル | タイルペイント | 因子の部屋 | 黒どこ | 推理パズル |
| ひとりにしてくれ | へやわけ | ペイントエリア | 数コロ | パイプリンク |
| クリーク | アイスバーン | サムライン | カントリーロード | カナオレ |
| フィルマット | シャカシャカ | ヤジリン | ぬりかべ | ホタルビーム |
| ステンドグラス | さとがえり | スケルトン | ニコリより名称引用 |