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

  • 12
    Like
  • 0
    Comment
More than 1 year has passed since last update.

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

数理モデルの作成手順

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

  1. 数理モデル(LpProblem)を作成する
  2. 変数(LpVariable)を追加する
  3. 目的関数の式(LpAffineExpression)を追加する
  4. 制約(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つだけの数字を使用可能 (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}

その他の最適化問題

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