１．はじめに

数理最適化の練習としてチーム分けを行ってみたので、今回はそれについて共有します。
初数理最適化なので嘘をついていたら教えてください。

２．背景と目的の設定

・毎週10人の社員が集まって仕事をする。
・そのとき、昼休みにランチへ行きたい。
・しかし、10人が座れる席は基本的に存在しない。
・したがって、３グループ程度に分かれる必要がある。

・そのとき、なるべく色々な人と話せるようにしたい。
・そのために、AさんとBさん、BさんとCさんといった社員の各組み合わせについて、同じグループになる回数をなるべく均等にしたい。

以下のように分かれる

３．方法

まず、「均等に分かれる」という条件を、「同じチームになった回数の最大値が最小」かつ「最小値が最大」と言い換えます。

ハード制約（絶対に守る条件）
・グループの人数は４，３，３人
・各社員は、毎週いずれか１グループのみに所属（分身したり、消えたりしない）
・W週間で各社員同士が同じグループになる回数について、最小値を一定以上にする（一度も同じグループにならない２人の組み合わせがあってはならない）

ソフト制約
・W週間で各社員同士が同じグループになる回数について、最大値を最小化する

定式化

とりあえず、最初に考えたのが以下の定式化です。

変数

$W$：考慮する週（今回は$4$）
$x_{iwg}$：メンバー $i$ が週 $w$ でグループ $g$ に属しているかどうかを示すバイナリ変数
$y_{ijwg}$：メンバー $i$ と $j$ が週 $w$ でグループ $g$ で一緒かどうかを示すバイナリ変数
$z_{ijg}$：メンバー $i$ と $j$ がグループ $g$ で一緒になる回数を示す整数変数（$\geq$0）
$max$：$w$週間で、任意のメンバーが一緒のグループになった回数の最大値（$\geq$0）
$min$；$w$週間で、任意のメンバーが一緒のグループになった回数の最小値（今回は1に固定）

目的関数

$minimize$ $max$

制約条件

各メンバーは、各週いずれか一つのグループに所属：
$\sum_{g=0}^{2} x_{iwg} = 1$

グループ0は4人、グループ1と2は3人所属：
$\sum_{i=0}^{n-1} x_{iw0} = 4,$
$\sum_{i=0}^{n-1} x_{iw1} = 3,$
$\sum_{i=0}^{n-1} x_{iw2} = 3$

$i$さんと$j$さんが同じグループの場合に1, そうでない場合0の$y$を作成：
$x_{iwg} + x_{jwg} - 1 \leq y_{ijwg} ,$
$y_{ijwg} \geq x_{iwg},$
$y_{ijwg} \geq x_{jwg}$

$z_{ijg}$ は $y_{ijwg}$ の$w週間$での合計を表す：
$z_{ijg} = \sum_{w=0}^{w-1} y_{ijwg}$

各組み合わせ $i,j$ について、同じグループになる回数の合計は$min$以上$max$以下：
$\sum_{l=0}^{2} z_{ijg} \leq max,$
$\sum_{l=0}^{2} z_{ijg} \geq min$

以下の○、×の部分を０か１の変数（$x_{ij}$）にして、ここにいろいろな制約を加えていくイメージです。

そしてiさんとjさんが第w週目のグループlで同じグループである場合に1になるバイナリ変数$y_{ijwl}$を設定します。

というわけで、とりあえず愚直に実装し、いざ実行…。しかし、待てど暮らせど終わりません。この方法ではxiwlやyijwlといった変数の種類、添え字の数が多く、数式が非常に複雑になっていました。これが原因で計算が煩雑になり、時間がかかっていた可能性があります。

そこで「考えられるグループ分けのパターンと、そのグループ分けにおける社員の被り情報（誰と誰が同じチームかの情報）を予め用意しておき、そこから採用するグループを$W$週間分選ぶ」という方式に変更しました。例えるならレゴブロックを一つずつ選んで最適な組み合わせを作るのではなく、ある程度の数のブロックがくっついた状態をたくさん作り、その塊のうちどれを選ぶか、に変えたという感じです。数理最適化では問題を簡単にするためによく使われる手法です。
つまり、以下のようなイメージで、各パターンについて採用不採用のみを変数とします。

存在しうるグループ分けの数は、

 {} _{10}{C} _{4} *{} _{6}{C} _{3} *{} _{3}{C} _{3} = 4200

で$4200$通りです。

この場合の定式化は、以下のようになります。

変数

$W$：考慮する週の数（今回は4）
$patterns$ : グループ分けのパターン数（今回は4200）

$x_i$：パターン $i$ を使用するかどうかを示すバイナリ変数
$kaburi_{ijk}$ ：パターン $i$ でメンバー $j$ と $k$ が同じグループになるかどうかを示すバイナリ変数
$max$：$w$週間で、任意のメンバーが一緒のグループになった回数の最大値（$\geq$0）
$min$；$w$週間で、任意のメンバーが一緒のグループになった回数の最小値（今回は1に固定）

目的関数

$minimize$ $max$

制約条件

使用するパターンの数は $W$ 週分：
$\sum_{i=0}^{patterns} x_i = W$

各メンバーの組み合わせ $j, k$ について、同じグループになる回数は $min$ 以上$max$ 以下：
$\sum_{i=0}^{patterns} kaburi_{ijk} \cdot x_i \leq max,$
$\sum_{i=0}^{patterns} kaburi_{ijk} \cdot x_i \geq min$

というわけで再び実行し待つこと25分…。今回は無事に結果が出力されました。
各社員が同じグループになった回数を表にすると、以下のようになります。

これを見ると、4週間で全員が1回以上同じグループになるようにする場合、4回一緒になる組み合わせが発生するようです。

これではあまり良くないので、考慮する期間$W$を8週間に、同じグループになる最小値$min$を２に変更して再度実行します。すると、今度は（なぜか）1秒で結果が出力されました。

その結果、全組み合わせで2~3回同じグループになる状態になりました。よかったですね。

４．おわりに

はじめて数理最適化に触れましたが、身近な問題に対して効率を追求できる感じが面白いです。
正しい定式化を行うことで、計算量を大幅に減らせることを学びました。