I am coordinating cookie-baking events with kindergarten kids. This turns out to be a challenging problem, and I could use a little help:
We would like a general way of creating ‘fair’ cookie-baking teams for kindergarten pupils.
By ‘fair’ I mean the following:
The cost of meeting old teammates and locations, should be distributed evenly. So it is better to have 10 children teaming up with one old teammate
each, than having one child teaming up with 4 old teammates at the same time.
Bonus question: The teams should consist of an even number of boys and girls (as even as possible) ðŸ™‚
I am are both interested in a practical solution (algorithm), and also in general pointers for how we can approach this problem in general (e.g. graph theory,
set theory, constraint satisfaction).
In the future there will be more constraints added to the problem, e.g. child A and child B argue a lot,
so they should preferably not be in the same group. Or the opposite: A and B wants to spend time together and should preferably be in the same group N number of times.
Just imagine any kind of suggestions that parents can come up with, and they all have to fit into the puzzle.
Thank you for your suggestions, I am looking forward to your answer and to crack this problem with a computer program.
Best regards,
Paul
In a real classroom, the contraints will be time-dependent, including the membership in the class, the size of the class, and who’s friends with whom. So a streaming optimization algorithm is the only practical choice – you don’t want to lock yourself into a beautiful combinatorial design and then gain a new student 3 weeks into the process.
For students $u$ and $v$, let $t_{uv}$ be the time since those students were on the same team. Specify a decreasing function $f(t)$ to represent the “cost” of putting two students together again after time $t$, and specify some positive weights $\alpha$ and $\beta$. Then for any partition $P=(P_1,\ldots,P_k)$ of the students into $k$ teams, you want to find partitions with small cost $C(P)$, where
$$C(P) = \sum_{i=1}^k \beta |P_i|^2+ \left(
\sum_{u,v\in P_i} \alpha f(t_{uv}) \right).$$
You can choose the weights to reflect your weighting of the importance of the different criteria. As far as choosing $f$, you probably want memory to be negligible after about $k$ sessions, so $f(t) = 1/(1+(t/k)^2)$ or $\exp(-(t^2/2k^2))$ are natural choices. It’s easy to add on additional criteria into this framework, such as adding a penalty into the first sum if students $u$ and $v$ are the same gender. And if you fix the sizes of the teams up front, you can skip the $\beta$ term, which penalizes imbalanced team sizes.
So how do you minimize the cost? There are too many partitions to try them all, but the cost function has the property that if you make a small change (move one student from one team to another, or swap two students), only a few terms in the sum will change. So the setup is ideal to apply standard combinatorial optimization techniques such as simulated annealing or a genetic algorithm.
Experimental results: I tried simulated annealing with the decay function $f(t)=\exp(-t/k)$, $\alpha=\beta=1$, with $23$ students and $6$ teams. I generated partitions for the first $10$ weeks twice: once so that my (slow) code would terminate in about $2$ seconds per partition, and once so that it took about $30$ seconds per partition. As an initial condition I set $t_{uv}=-100$, so as time goes on, we gradually begin to accumulate penalty for pairing students who’ve previously been together. Here are the results for the long run, with each partition followed by its score.
\begin{array}{cccc}
3 & 5 & 22 & \text{} \\
2 & 10 & 13 & 23 \\
7 & 9 & 11 & 17 \\
12 & 15 & 20 & 21 \\
14 & 16 & 18 & 19 \\
1 & 4 & 6 & 8 \\
\end{array}
89.0
\begin{array}{cccc}
3 & 13 & 14 & 15 \\
1 & 2 & 12 & 19 \\
10 & 16 & 17 & 20 \\
6 & 7 & 22 & 23 \\
4 & 5 & 9 & 18 \\
8 & 11 & 21 & \text{} \\
\end{array}
89.0
\begin{array}{cccc}
3 & 4 & 11 & 19 \\
1 & 10 & 18 & 22 \\
9 & 12 & 23 & \text{} \\
2 & 8 & 15 & 17 \\
7 & 13 & 16 & 21 \\
5 & 6 & 14 & 20 \\
\end{array}
89.0
\begin{array}{cccc}
2 & 6 & 11 & 16 \\
9 & 10 & 21 & \text{} \\
4 & 12 & 14 & 17 \\
8 & 13 & 19 & 22 \\
1 & 5 & 7 & 15 \\
3 & 18 & 20 & 23 \\
\end{array}
89.0
\begin{array}{cccc}
1 & 11 & 14 & 21 \\
2 & 9 & 20 & 22 \\
3 & 7 & 8 & 12 \\
6 & 13 & 17 & 18 \\
5 & 10 & 19 & \text{} \\
4 & 15 & 16 & 23 \\
\end{array}
89.6065
\begin{array}{cccc}
5 & 11 & 12 & 22 \\
2 & 7 & 18 & \text{} \\
1 & 4 & 13 & 20 \\
8 & 9 & 14 & 16 \\
17 & 19 & 21 & 23 \\
3 & 6 & 10 & 15 \\
\end{array}
90.8172
\begin{array}{cccc}
10 & 12 & 13 & 16 \\
1 & 3 & 9 & 17 \\
2 & 5 & 8 & 23 \\
7 & 14 & 19 & 20 \\
11 & 15 & 18 & \text{} \\
4 & 6 & 21 & 22 \\
\end{array}
93.2488
\begin{array}{cccc}
5 & 7 & 13 & 17 \\
3 & 12 & 18 & 21 \\
1 & 16 & 22 & 23 \\
2 & 4 & 10 & 14 \\
8 & 11 & 20 & \text{} \\
6 & 9 & 15 & 19 \\
\end{array}
95.6155
\begin{array}{cccc}
3 & 4 & 5 & 16 \\
14 & 15 & 17 & 22 \\
6 & 12 & 20 & \text{} \\
1 & 8 & 18 & 19 \\
2 & 9 & 13 & 21 \\
7 & 10 & 11 & 23 \\
\end{array}
96.2608
\begin{array}{cccc}
16 & 17 & 18 & 20 \\
2 & 3 & 11 & 19 \\
1 & 5 & 15 & 21 \\
4 & 7 & 9 & 12 \\
8 & 10 & 22 & \text{} \\
6 & 13 & 14 & 23 \\
\end{array}
97.9197
Here are the scores for the two experiments. Clearly running longer gives better results (lower scores):