Python-MIPを使ってブルアカの編成を考える | cloud.config Tech Blog

24卒で入社しました高江です。

最近は麻雀にハマっています。

大学では数理最適化について勉強してました。

今回はタイトルにもあるように、私が数理最適化でお世話になったPython-MIPを使ってブルアカの部隊編成を考えてもらいましょう。

1．数理最適化とは

最初に数理最適化について簡単に説明します。

数理最適化とは現実で起こる諸問題を定式化し、その最大値・最小値を求めるといったものです。

例として、荷物の配達でどのルートから配達を行えば最短距離で全ての配達を終えることができるのか、予算内でレストランでカロリーが最も高くなる注文の組み合わせといったものがあります。

こうしたものを数式に置き換えて計算することを数理最適化といいます。

わかりやすく買い物で考えてみましょう。

制約条件：5000円以内で食材を購入する

変数：食材

目的関数：食材の量、カロリー、栄養価、値段

このとき、制約条件である予算5000円以内で、目的関数の最大化（量が最大になる、カロリーが最大になる、栄養価が最大になる）を行うために最適な変数（食材の数）の値を求めるのが数理最適化です。

2．Python-MIPで楽々最適化

では、定式化した目的関数を計算するとなったとき、あまりにも複雑な式だと計算に時間がかかってしまいます。そこで、便利なのがPython-MIPです。

Python-MIPとは、混合整数計画問題（MIP）をモデル化するためのツールです。混合整数計算問題とは、整数値を取る変数と実数値を取る変数が混在している整数計画問題のことをいいます。前述した買い物の例もこれに当たります。

3．実践編

では、実際にPython-MIPを使ってみましょう。タイトルにもある通り今回はブルアカの部隊編成をPython-MIPで出力させます。

ちなみにブルアカについて簡単に説明すると、ブルーアーカイブというゲームの略称であり、ゲームの内容としては部隊を編成して敵を制圧するゲームです。

詳しい説明は省きますが、部隊に編成できる生徒には様々な属性が割り振られており、敵の部隊に合わせて編成を考えていく必要があります。

というわけで早速コードを書いてみましょう。

ちなみに、MIPのライブラリは以下のコマンドでインストールできます。

pip install mip

最初に変数、制約条件、目的関数を決めます。

変数

生徒（編成に入れるとき1、入れないとき０の値をとるバイナリ変数）

制約条件

ストライカー4人、スペシャル2人を編成する

タンクを1人編成する

ヒーラーを1人以上編成する

サポーターは1人以上編成する

入力した属性のアタッカーを2人以上編成する

入力した属性のストライカーを3人以上編成する

目的関数

部隊全体のEXスキルコストの最小化

次に、これらを定式化します。

これをPython-MIPでモデル化して解きます。

今回は41名の生徒が記録されたcsvファイル（students.csv）からデータを読み取ります。

Pythonimport pandas as pd
import matplotlib.pyplot as plt
from mip import Model, maximize, minimize, xsum

s_df = pd.read_csv("content/drive/MyDrive/blue_archive/students.csv")

p = Model("unit") #モデルを作成

#変数の作成
x = []
for index, row in s_df.iterrows():
	x[row["id"]] = p.add_var("{}".format(row["name"]),var_type = "B")

attack_type = input("敵の装甲に有利な属性を入力してください->")

#制約条件の追加
p.add_constr(xsum(x[row["id"]] for index, row in s_df.iterrows() if row["attribute"] == "striker") == 4)
p.add_constr(xsum(x[row["id"]] for index, row in s_df.iterrows() if row["attribute"] == "special") == 2)
p.add_constr(xsum(x[row["id"]] for index, row in s_df.iterrows() if row["class"] == "tank") == 1)
p.add_constr(xsum(x[row["id"]] for index, row in s_df.iterrows() if row["class"] == "healer") >= 1)
p.add_constr(xsum(x[row["id"]] for index, row in s_df.iterrows() if row["class"] == "suppoter") >= 1)
p.add_constr(xsum(x[row["id"]] for index, row in s_df.iterrows() 
			if row["class"] == "attacker" and row["attack_type"] == attack_type) >= 2)
p.add_constr(xsum(x[row["id"]] for index, row in s_df.iterrows() 
			if row["attribute"] == "striker" and row["attack_type"] == attack_type) >= 3)

#目的関数の追加
p.objective = minimize(xsum(row["cost"]*x[row["id"]] for index, row in s_df.iterrows()))

#最適化実行
p.optimize()

#結果の表示
opt_sol = [x[row["id"]].x for index, row in s_df.iterrows()]
s_df["result"] = opt_sol

ordered_unit = s_df.query("result > 0.5")
print(ordered_unit)

cost = [row["cost"] for index, row in s_df.iterrows() if row["result"] > 0.5]
print("合計EXスキルコスト = {}".format(sum(cost)))
cost = [row["rank"] for index, row in s_df.iterrows() if row["result"] > 0.5]
print("合計★の数 = {}".format(sum(rank)))