# Combining kindergardeners in 'fair' cookie-baking groups. Kirkman's schoolgirl problem extended version

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:

• A class consisting of N children (usually in the range 18 to 24) is divided into teams of even size T with ~4 kids in each (as even as possible).
• Each team is assigned to a location with a parent overseeing them
• Every week we scramble the teams so that the every child team up with as many new classmates as possible, and every child is assigned to a new location (as new as possible).
• This goes on indefinitely. As time passes, the children will start to be teamed up with old teammates, in locations they already know. It is important that when they team up with old teammates, the more weeks it has been since they were on same team, the better. Same for locations.
• 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): • Thanks Tad, yes it is a way to go for calculating and optimizing cost. Can you please explain the $\beta |P_i|^2$ ? It seems to me that it adds extra cost to teams of larger size. If dynamic optimization with weights is chosen as solution, the main problem is to keep the algorithm time complexity down. Do you have any toughts about how to make a generator function for constructing the partitions, avoiding symmetrical solutions to minimize the search space? Mar 15, 2015 at 15:09
• Yes, $\sum_i |P_i|^2$ is minimized when the teams are balanced. For example, suppose you have $24$ students, and enough parents for $k=6$ teams. If all the teams have $4$ students, then $\sum_i |P_i|^2=6(4)^2=96$. But if the team sizes are $(6,5,5,3,3,2)$, you get $108$. As for the complexity, you're taking advantage of the local "neighborhood" structure so that you don't actually have to search the entire space. If you just need reasonably good solutions, simulated annealing should do quite well: start with a random partition and gradually improve it. I'll try it out if I have some time.
Also, I would like to note that there have been projects like good-enough-golfers and socialgolfer.js that do similar things: scheduling $$K$$ rounds of groupings, each with groups of $$N$$ size (they both use genetic algorithms; you can see their implementation on the respective GitHub repos). However, this would not be flexible if you, say, add a student to the class. That's why I made that NPM package. I do think these available solutions are still worth mentioning, though.