プロ野球のスケジュール作成を題材に、定式化からpulpを使った実装まで。
定式化はこちら↓
筆者の環境：
macOS Catalina version10.15.6
python3.8.3
pulpのインストール
pip install pulpで入ります。
実装
問題の宣言
import pulp
problem = pulp.LpProblem('GameSchesule',pulp.LpMinimize)まずpulpをimportして、解きたい問題を宣言します。
最大化問題を解きたい時には
problem += pulp.LpProblem('hogehoge',pulp.LpMaximize)のようにします。
変数を設定
以下のようにすることで、変数の組みを辞書型で作成することができます。
第一引数は変数名、第二引数は辞書のキーに対応するタプル、第三引数は変数の下限、四引数は変数の上限、第五引数は変数の型を表します。
整数型”Integer”の他に、実数を表す”Continuous”、0-1を表す”Binary”があります。
# set variables
h = pulp.LpVariable.dicts('home', ([0,1],I,I,W),0,1,'Integer')
v = pulp.LpVariable.dicts('visitor', ([0,1],I,I,W),0,1,'Integer')
home = pulp.LpVariable.dicts('new_home', ([0,1],I,I,W),0,1,'Integer')
vis = pulp.LpVariable.dicts('new_vis', ([0,1],I,I,I,W),0,1,'Integer')作成する変数が少ない時は、
x = pulp.LpVariable('x',0,1,'Integer')のように書くことも可能です。
目的関数を追加
pulpを用いて制約式や目的関数を追加する際には、
problem += (制約式/目的関数)のように記述します。今回解く問題の目的関数は以下のようになります。
problem += pulp.lpSum([D[_from][to]*(home[day][_from][to][w]+vis[day][team][_from][to][w])for _from in I for to in I for w in W for day in [0,1]for team in I])pulp.lpSum()はリストの要素を全て足し合わせるための関数です。
pulpを用いて線形計画問題を解く際には組み込みのsum()を使うよりもpulp.lpSum()を使用した方が動作が速くなります。
制約条件の追加
目的関数とほぼ同様ですが、以下のように関係式を追加する形になります。
# set constraints
for i in I:
# 総試合数に関する制約
problem += pulp.lpSum([h[0][i][j][w]+v[0][i][j][w]+h[1][i][j][w]+v[1][i][j][w] for j in I for w in W]) == self.total_game["r"]
for w in W:
# 1日あたりの試合数に関する制約
problem += pulp.lpSum([h[0][i][j][w]+v[0][i][j][w] for j in I]) == 1
problem += pulp.lpSum([h[1][i][j][w]+v[1][i][j][w] for j in I]) == 1
(以下略)ソルバーの選択(オプション)
pulpでデフォルトで使用されるソルバーは1スレッド版のcbcソルバーですが、個別に使用するソルバーを指定することで並列化したり、grobiやscipなどの外部ソルバーを呼び出すこともできます。
使用可能なソルバー一覧は、pulp.pulpTestAll()で確認できます。
CBCソルバーで設定できるオプションはこちらにわかりやすくまとめられています。
今回はログを出力する(msg=1)、解がひとつ見つかったら終了する(‘maxsol 1’)、並列数は2(threads=2)制限時間は1800秒という設定で実行しました。
solver = pulp.PULP_CBC_CMD(msg=1, options=['maxsol 1'], threads=2, maxSeconds=1800)結果を表示する
解いた結果、最適解が見つかった/途中で打ち切られた/解けなかったのいずれの状態かを確かめるには、以下を出力すればいいです。
status = problem.solve() # 1 / 0 / -1 / -2 / -3
pulp.LpStatus[status] # Optimal / Not Solved / Infeasible / Unbounded / Undefined設定した変数や制約式の値、目的関数の値を調べるには以下を出力すれば良いです。
value(x) # 変数の値
value(x+1) # 制約式の値
value(problem.objective) # 目的関数値参考までに、今回私が作成したソースコードはこちらに置いてあります。勉強用にお使いください。
役立ちリンク集
https://docs.pyq.jp/python/math_opt/pulp.html
https://qiita.com/nariaki3551/items/ea1117afb7f8ffbf7e90
https://qiita.com/samuelladoco/items/703bf78ea66e8369c455
https://qiita.com/mzmttks/items/82ea3a51e4dbea8fbc17
https://qiita.com/nariaki3551/items/94fa74abe8a268372874
この記事は役に立ちましたか？
もし参考になりましたら、下記のボタンで教えてください。
コメント