何をしたいのか
株式会社セガゲームスの開発・運営する「PHANTASY STAR ONLINE 2」（以下PSO2）における，ペットのキャンディーボックスへのキャンディーの配置を最適化したい．
数理最適化と呼ばれる手法を利用してこの問題を解くことを考えます．
今回は、問題を数式として表す（定式化）までを行い，具体的なプログラムについては別で投稿します．
前書きはいらないという人はモデル化の部分からどうぞ．
キャンディー配置とは
PSO2では，サモナーと呼ばれる職業はペットを召喚して戦うことができます．このペットには，それぞれキャンディーボックスと呼ばれる8×8サイズの箱が与えられており，これに入手したキャンディーと呼ばれるアイテムをはめ込むことでペットを強化できます．
しかし，キャンディーボックスは8×8マスの全てを使えるわけではなく，ペットの種族ごとに特定のマスにはキャンディーを置けないようになっています（16箇所）．
さらに，キャンディーも1×1の大きさのものから4×4のものなど，様々な大きさのものがあります．
詳しくは，以下のプレイヤーズサイトや攻略Wikiを参照して頂きたい（というかPSO2をやっていない人がこの記事を読むことはあまり想定していないため，一般的な説明は以降省きます）．
- http://pso2.jp/players/
- http://pso2.swiki.jp/
数理最適化・数理計画法とは
ここでは，数理最適化とか数理計画法と呼ばれる手法を用いて問題を解きます．
数理最適化とは，目的関数と制約条件が与えられたとき，その最適解（もしくは準最適解）を求めるための方法論です．応用数学やオペレーションズ・リサーチ（OR）といった分野でよく研究されています．
変数が連続か離散か，制約があるかないか，など様々な条件で問題は細かく分類されていきますがここでは省略します．
なぜ数理最適化ソルバーを利用するのか
ここでは，数理最適化問題（以下，最適化問題）として今回の問題を定式化（つまり数式にする）し，汎用の数理最適化ソルバー（以下，ソルバー）と呼ばれるプログラムを利用して解きます．
普通に専用の探索プログラムを書いて探索した方が速いのはおそらく間違いないです．ではなぜそうせず，汎用の数理最適化ソルバーを用いて解くのでしょうか？
それは以下の利点が存在するためです．
- （定式化部分と求解部分が分離されているため）後で制約条件が追加されても改修が楽
- 開発・保守が楽
実際，仕事でソルバーを使っている人たちもこの2点が大きいと思われます．
数理最適化ソルバー：
数理最適化問題を解くためのアルゴリズムを搭載したプログラム．単にソルバーと呼ばれることもある．
モデル化
キャンディーボックスの各マスは2次元の座標$(i, j)$で表すことにします．では，問題を定式化するために以下の記号を導入します．
集合：
- $I$ ：キャンディーボックスの縦のマスの添字集合（{ $0, 1, 2, \ldots, |I| - 1 $ }）．今回は8×8なので，0から7の整数．添字を$i, k$とする．
- $J$ ：キャンディーボックスの横のマスの添字集合（{ $0, 1, 2, \ldots, |J| - 1 $ }）．今回は8×8なので，0から7の整数．添字を$j, l$とする．
- $S$ ：キャンディーのタイプの集合（{パフェ，ロール，グミ，・・・}）．添字を$s$とする．
- $P$ ：キャンディーの集合（{スタミナグミ，ボディサンド, リアクトサンド，・・・}）．添字を$p$とする．
- $P_s$ ：キャンディータイプsのキャンディーの集合．集合$P$の部分集合．例えば，$P_{サンド} = $ { ボディサンド，リアクトサンド，マインドサンド}である．
パラメータ：
- $v_{p}$ ：キャンディー$p$の価値を表す．任意の数値．
- $c_{klp}^{ij}$ ：キャンディーボックスの座標$(k, l)$を左上の点としてキャンディー$p$を配置とき，座標$(i, j)$も占有する場合1，それ以外のとき0となるパラメータ．
- $a_{ijp}$ ：キャンディーボックスの座標$(i, j)$を左上の点として，キャンディー$p$を配置可能なとき1，それ以外のとき0であるパラメータ．
- $n_{p}$ ：キャンディー$p$の配置個数上限．例えば，スタミナグミなら20など．持っているキャンディーの個数に合わせて指定することも可能．
- $b_{p}$ ：キャンディー$p$の最低配置個数．キャンディー$p$を最低何個配置したいかを表す．例えば，スタミナグミを最低1個配置したいなら，$b_{スタミナグミ}=1$．
- $m_{s}$ ：キャンディータイプ$s$の合計配置個数上限．例えば，$s = $サンドなら5となる．
変数：
- $x_{ijp}$ ：キャンディーボックスの座標$(i, j)$を左上の点としてキャンディー$p$を配置するなら1，それ以外なら0となる0-1変数．
（注意）考えたい問題は，ペットの種類ごとに解けば良い問題であるため，ペットの種類の集合などは定義していません．
定式化
上記記号を用いて，問題を混合整数線形計画問題（最適化問題の1種，一部変数が整数であるという条件以外の式は全て線形）として以下のように定式化できます．
\begin{align}
\mathbb{maximize} & & \sum_{i \in I} \sum_{j \in J} \sum_{p \in P} v_{p} x_{ijp} & \\
\mathbb{subject \ to} & & x_{ijp} \leq a_{ijp} & & \forall i \in I, j \in J, p \in P \\
& & \sum_{k \in I} \sum_{l \in J} \sum_{p \in P} c_{klp}^{ij} x_{klp} \leq 1 & & \forall i \in I, j \in J \\
& & b_{p} \leq \sum_{i \in I} \sum_{j \in J} x_{ijp} \leq n_{p} & & \forall p \in P \\
& & \sum_{i \in I} \sum_{j \in J} \sum_{p \in P_{s}} x_{ijp} \leq m_{s} & & \forall s \in S \\
& & x_{ijp} \in \{ 0, 1 \} & & \forall i \in I, j \in J, p \in P \\
\end{align}
目的関数は，キャンディー$p$の価値$v_{p}$とキャンディー$p$を座標$(i,j)$に配置するかどうかを表す変数の積の総和であり，配置することにしたキャンディーの価値の合計を表します．
- 1番目の制約式は，キャンディーはそもそもキャンディーボックスにおいてそのキャンディーを置ける場所にしか置けない（つまり「置ける場所=$a_{ijp}$が1」でなければ「配置する=$x_{ijp}$が1」になれない）ということを表しています．
- 2番目の制約式は，キャンディーボックスのある座標$(i,j)$に置けるキャンディーは1つのみであることを表しています．
- 3番目の制約式は，キャンディーボックス全体でキャンディー$p$の配置個数は最低個数$b_{p}$以上，上限個数$n_{p}$以下であることを表しています．
- 4番目の制約式は，キャンディーボックス全体でキャンディーの種類$s$の配置個数が上限$m_{s}$を超えないことを表しています．
これで最適化問題として定式化できました（$a_{ijp}$とか$c_{klp}^{ij}$とかかなり手抜きですが許してください．．．）．
次回，実際にPython-PuLP（及び内蔵されているソルバーのCBC）を利用して解くプログラムを公開したいと思います．
走り書きなので何かあればご指摘をお願い致します．