いやー。困った困った。

10X の @metalunk です。先日 10X は全社オフサイトを開催しました。普段はほとんどの社員がリモートワークをしており（10X 社員は日本国内ならば居住地自由です）、直接顔を合わせることが少ないです。そのため今回のオフサイトの目的の一つは、多くのメンバーとコミュニケーションを取り、関係性づくりをすることでした。

そこで、Head of チームビルディングを拝命した私は、コミュニケーション促進に定評のある、ボードゲームをすることに決め、さらに、時間内に効率的にチームをシャッフルすることで、できるだけ多くの人と交流する企画を考えました。

参加人数は64名、各ゲームのプレイ人数は5, 6人であるから、12チームに分ける必要があります。1ゲームのプレイ時間は25分として、5セットプレイできそうです。

さて、このときどんなチームわけをすると、できるだけ多くの人と同じチームになれるでしょうか？

問題設定

参加人数は64名。

時間割は5セット。

ゲームは以下の6つで、それぞれ2つ準備があるため合計12ゲーム。プレイ人数はそれぞれ5, 6人

リレー形式マリオカート
Dixit
はぁっていうゲーム
ワンナイト人狼
ブラフ
コードネーム

さらに、参加者が飽きないよう、同じゲームを2回プレイすることは防ぎます。

この組み合わせの総数はこのようになります。

7のあとに0が182個続く、とても大きい組み合わせで、全列挙するにはあまりに多すぎます。

ところで、数式をブログに書くのはあまりに大変すぎるので、数式は味わいのある手書きで行きますね。

整数計画問題として定式化

このような、組み合わせの総数が爆発的に大きくなる問題は、最適化問題として定式化し、問題の構造を利用して効率的に解くのが良いです。

以下のように定式化しました。

目的関数の工夫

当初、「メンバーごとの、同じチームになる人数の総和」を最大化する問題を解けば良いと考えました。

しかし、これを表現すると以下のようになり、max 関数が入り込み、目的関数は線形でありません。

この問題は MIP (Mixed Integer Programming) solver で解こうとしていたため、目的関数は線形である必要があり、工夫が必要です。

そこで「同じチームになる人数」の最大化を諦め、「同じ人と同じチームになる回数」に上限をつける制約条件にすることを思いつきました。式で書くとこうなります。

しかし、これも線形ではありません。そこで、新たな変数 z を導入することで、線形に変換できました。

プログラミング

MIP に定式化できたため、あとは MIP solver に解いてもらいます。今回は OR-Tools の SCIP solver を利用しました。

OR-Tools を使うと、コードで簡単に MIP を表現できます。私はこの作業を初めて行いましたが、本当に簡単で感動しました。

def solve(
        self,
        people: list,
        times: list,
        games: list,
        game_capacities: dict,
        acceptable_duplicates: int,
):
    # Create the MIP solver
    solver = pywraplp.Solver.CreateSolver('SCIP')

    # Create the variables x and z
    x = {}
    for i in people:
        for j in times:
            for k in games:
                var_name = self._x_var_name(i, j, k)
                x[var_name] = solver.IntVar(0, 1, var_name)
    z = {}
    for i1 in people:
        for i2 in people:
            if i1 >= i2:
                continue
            for j in times:
                for k in games:
                    var_name = self._z_var_name(i1, i2, j, k)
                    z[var_name] = solver.IntVar(0, 1, var_name)
    print('Number of variables =', solver.NumVariables())

    # Constraints
    # Everyone belongs to a team for all time range
    for i in people:
        for j in times:
            ct = solver.Constraint(1, 1, 'ct')
            for k in games:
                ct.SetCoefficient(x[self._x_var_name(i, j, k)], 1)

    # The number of people in a game is smaller or equal to the capacity
    for j in times:
        for k in games:
            ct = solver.Constraint(0, game_capacities[k], 'ct')
            for i in people:
                ct.SetCoefficient(x[self._x_var_name(i, j, k)], 1)

    # Anyone doesn't play the same game twice
    for i in people:
        for k in games:
            ct = solver.Constraint(0, 1, 'ct')
            for j in times:
                ct.SetCoefficient(x[self._x_var_name(i, j, k)], 1)

    # The number of times that one person plays with the same person <= U
    # Linearized version of the constraints below
    # \sum_(j \in J) \sum_(k \in K) x_i1_j_k * x_i2_j_k <= U for all i1 \in I, for all i2 \in I
    for i1 in people:
        for i2 in people:
            if i1 >= i2:
                continue

            sum_z = 0
            for j in times:
                for k in games:
                    _z = z[self._z_var_name(i1, i2, j, k)]
                    _x = x[self._x_var_name(i1, j, k)]
                    _y = x[self._x_var_name(i2, j, k)]

                    sum_z += _z

                    solver.Add(_z - _x <= 0)
                    solver.Add(_z - _y <= 0)
                    solver.Add(_x + _y - _z <= 1)

            # z <= U
            solver.Add(sum_z <= acceptable_duplicates)

    print('Number of constraints =', solver.NumConstraints())

    solver.Solve()

問題サイズの課題

ここで新たな問題が発生しました。問題サイズが大きすぎて解けませんでした。

40人くらいまでは解けます。しかし、1人増えるたびに数百倍問題が難しくなるため、64人では厳しいようです。新たな工夫が必要です。

z の導入で変数サイズ、制約条件の数が増えていることがわかっていたので、モデリングを工夫してどうにか問題を小さくしようと悩みましたが、いい方法が浮かびませんでした。賢いみなさん、どうか助けてください。

仕方がないので妥協して、64人の問題を2つの子問題30人、34人に分割して解くことにしました。

「同じ人と同じチームになる回数の上限」は 1 が最適ですが、それでは解けなかったため 2 としました。

結果

時間ごとに、チームわけが生成できました。同じ人と同じチームになる回数は高々2回です。

評価

参加者たちに聞くと、同じ人と同じチームになった回数はせいぜい2回くらいで、多くの人と交流できたとのことです。解を眺めた感じでも、かなりいい解が得られていた感触があります（ちゃんと評価すれば数字が出せますが横着しています）

弊社の機械学習エンジニアが、チームビルディング(ボードゲーム)の64人のチーム分けの困難さについて話しています @metalunk pic.twitter.com/hdK6b4fBz4
— uemr (@_nauya) April 15, 2022

最適化されたチームで盛り上がっている様子

その後

オフサイトでたくさん日本酒を飲んだ帰り道、@tapih は、より効率的にチームわけをする手段はなかったのだろうかと考えておりました。そして、より良い手段を発見しました。

この方法でチームわけをすると「同じ人と同じチームになる回数」が高々1回であり、最適解であることが言えます。素晴らしい！！MIP として解いたときはあんなに大変だったのに、最適解を一行で出す方法が発見されました！！

このアルゴリズムの気持ちを表現するとこんな感じです。

実装もシンプルです

def solve(self):
   solution = [{g: [] for g in self._games} for _ in self._times]
   for n, person in enumerate(self._people):
       for t in self._times:
           a = n // len(self._games) + 1
           b = n % len(self._games)
           x = (a * t + b) % len(self._games)
           solution[t][self._games[x]].append(person)