3
$\begingroup$

I am trying to design an algorithm that allows to create balanced teams for a summer camp. There are about a 100 campers of different ages. Gender ratio isn't necessarily 50/50. Also there are a different number of campers for each age group. The idea is to create fair and well-balanced teams while having approximately the same amount of boys and girls in each team as well as the same number of kids in each age group per team. The usual approach is to make a list and manually make the teams (prior to the camp), but this is stupid and has a lot of balancing issues.

My idea is to create an algorithm based on some kind of score (eg. time to run an obstacle course) simple enough to be programmed in excel or some other tool everybody knows how to use. My first idea of how it could look like is:

  1. Separating boys and girls into different categories
  2. Ordering them from fast to slow (this should still make it so that the oldest kids are roughly at the top of the list and the slowest at the bottom)
  3. Design algorithm that creates teams with the same averages while taking kids from all over the list. This is the part I'm having trouble with because I don't want to use iterative methods.
  4. Once I have the boys teams and girl teams ready mix them together so that

    4.1 Each group has the same amount of kids (number of boys + number of girls)

    4.2 The average time of each team should be as close as possible (here are iterative methods ok because there are less combinations)

If anyone has experience, ideas or has seen something similar I'd gladly read it.

$\endgroup$
  • 2
    $\begingroup$ How many teams are you aiming it, and how big are they? $\endgroup$ – Yuval Filmus Jun 26 '18 at 15:55
1
$\begingroup$

There's probably a tradeoff between ease of implementation and the quality of the solution. I'll list a few possible approaches. The first step is to pick a way to measure the quality (imbalance/unfairness) of a proposed solution. One possibility would be the variance of the team averages; another would be the gap between the largest team average and the smallest team average. Then, pick one of the following methods to choose an assignment that is as good as possible, under this quality measure:

  1. Random. The simplest to implement method is random assignment. Randomly assign each kid to a team (subject to the requirement that each team has the same number of boys and same number of girls). Measure the quality of each assignment. Do this for 1000 random assignments. Pick the best one. That's very easy to implement.

    Here is a simple way to do the random assignment: randomly re-order the list of kids, and put the first $k$ into the first team, the next $k$ into the second team, and so on, where $k$ is the desired team size. To also ensure gender equality, do this separately for the boys and girls.

  2. A greedy heuristic. A different approach is to assign the kids to teams in a heuristic way. Sort the kids from slowest to fasteast. Now iterate over the kids in this order and, for each kid, assign that kid to a team. Assign the kid to the fastest team (measured by their average speed given the current assignment). If some teams currently have fewer members than others, only choose among the teams with the fewest members. To ensure gender equality, when a boy picks a team, have them only pick among the teams with the fewest number of boys; and symmetrically for girls. There are other heuristics you could consider, but this seems like it might yield good results.

  3. Random + heuristic. You can combine the first two ideas. First, randomly pick a fraction of the kids, and then randomly assign them to teams. Second, assign the rest of the kids via the above heuristic. You can repeat 1000 times and take the best assignment seen so far.

    It will probably help to ensure that the initial random assignment assigns the same number of boys and girls to each team.

  4. Simulated annealing. A more sophisticated method is to start with a random assignment and use simulated annealing to improve it. In each step, you randomly pick a pair of kids of the same gender but from different teams, and you consider what would happen if you swapped them. Depending on how this affects the quality of the solution, you decide whether to make the swap or not, in a particular way. Simulated annealing might improve on the other methods, but it is also a little fiddly, as there are parameters you have to tune to get it to work to best effect.

  5. Integer linear programming. If you're willing to measure quality by the difference between the largest team average and the smallest team average, a more sophisticated method still is to use integer linear programming. You have a zero-or-one integer variable $x_{i,j}$ indicating that the $i$th kid is assigned to the $j$th team, and then you can write down linear inequalities that capture the requirements on a solution to be valid. This can potentially give you the optimal solution.

I suspect the latter two approaches are more complicated than is really necessary and just trying a bunch of random assignments might be good enough.

In general, your problem is NP-hard; it is as hard as bin-packing. If you cared enough you could investigate the heuristics and approximations for bin-packing and try seeing if you can adapt them to your problem. I don't know that that will be worth the effort.

$\endgroup$
  • $\begingroup$ +1 for ILP suggestion. That would be a fun exercise to work out $\endgroup$ – koverman47 Jul 27 '18 at 2:29

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.