2
$\begingroup$

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

$\endgroup$

2 Answers 2

4
$\begingroup$

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):

simulated annealing results

$\endgroup$
6
  • $\begingroup$ 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? $\endgroup$
    – user681814
    Mar 15, 2015 at 15:09
  • $\begingroup$ 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. $\endgroup$
    – Tad
    Mar 15, 2015 at 17:03
  • $\begingroup$ Thank you, yes I see. I get that simulated annealing does not walk through the entire search space, but with the random jump part of sim.annealing I'm concerned that symmetric solutions will compete for algorithmic cycles in local optima, taking away possibilities from better solutions. Anyway you may be right that reasonably good enough solutions are covered with this, and I'm going to try it out. I'm very interested in what you find out if you ever get the time. $\endgroup$
    – user681814
    Mar 15, 2015 at 19:23
  • $\begingroup$ I've included some results. Certainly looks good enough for kindergarten! $\endgroup$
    – Tad
    Mar 16, 2015 at 5:36
  • $\begingroup$ Thanks again! Highly informative and after doing some tests I set up a ruby program running the simulation. It is extremely effective for solving this sort of problems apparently, just doing random swapping for 5000 iterations is easily enough to create a workable solution, and that is even before optimization of any kind. I'm very happy. As a side note, I might add that your results have a good score but in order to be used, the cost function have to penalize repeated meets between two persons (e.g. 3 and 1). This is trivial however. THANK YOU You have been a big help :-) $\endgroup$
    – user681814
    Mar 16, 2015 at 13:58
1
$\begingroup$

I created an NPM package that does exactly this, using @Tad's cost function and technique of using simulated annealing. Here is a link to it.

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.

$\endgroup$
2
  • $\begingroup$ May I please ask why I was downvoted? I'm just trying to be helpful to individuals like me in the future who encountered such a problem; any constructive feedback would be great. $\endgroup$
    – Matias
    Dec 24, 2019 at 22:23
  • $\begingroup$ I am unsure why you were downvoted here Matias, I found both your NPM package and the links to other solutions you provided to be extremely helpful. Thanks! $\endgroup$
    – marcel
    Nov 5, 2021 at 23:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.