Problem Statement
My wife's business runs a summer camp for 68 students. The students are divided into cabins:
- 27 students in 3 groups of 7 and one group of 6 belong in one set of 4 cabins;
- 41 students in 5 groups of 7 and one group of 6 belong in the other set of 6 cabins. Which set of cabins a student belongs in is fixed, but not which cabin.
The students are also divided into discussion groups. There is a maximum of 10 discussion groups with 6 or 7 students per group. (It is possible there will not be all 68 students in attendance.) No discussion group assignments are fixed, and discussion groups can (and should) be different from cabin assignments.
The business also has a dossier of variables about each student. Let's call these variables $A$, $B$, $C$, etc. There are at least 4 major variables in addition to cabin assignment ($cabin$).
The goal of the problem is to find assignments of students.
- For cabins, each cabin should have a roughly equal distribution among the values of major variables (excepting $cabin$, which is fixed).
- For discussion groups, each group should have a roughly equal distribution among the values of major variables and $cabin$.
As an example, if each cabin in the first set has roughly equal proportions of the values of each of the variables $A$, $B$, and $C$, then this is satisfactory.
Of course, the variables form a hierarchy: it is more important to balance $A$ then $B$ or $C$, $B$ dominates $C$, etc.
An example with 4 students and 2 variables (among one set of cabins and):
| student | $A$ | $B$ |
|---|---|---|
| Alice | 1 | 2 |
| Bob | 1 | 1 |
| Charlie | 2 | 2 |
| David | 2 | 1 |
Then pairing Alice with David and Bob with Charlie, each cabin would have 50% $A=1$ and 50% $A=2$ (idem. for $B$). Discussion groups would need to consider the $cabin$ variable, and realistically the distribution is unlikely to be a perfect split.
Questions
- Is this a known type of assignment problem? A review of problems linked on https://en.wikipedia.org/wiki/Assignment_problem and https://en.wikipedia.org/wiki/Combinatorial_optimization didn't produce any insights for me. (Is it a known type of other problem?)
- Are there known efficient exact solutions or heuristics (which provide a "good" assignment but not necessarily the "best")? The business isn't interested in something exact anyway, so I'm more than happy to accept efficient-enough heuristics that provide a reasonable starting point (one which humans could still iterate on if desired). I would also accept a negative result that proves even reasonable heuristics are impossible in reasonable time. Solutions with implementations or architectures are preferred, but I can implement a formalized algorithm.
Attempts at a Naïve Method
When I tried to work out the size of the problem for a naïve "generate all assignments, score them by the business's evaluation rules, and take the best" I calculated something like this:
- for the first set of cabins, we can first choose 7 of the 27, then 7 of the remaining 21, etc.;
- for the second set, we can first choose 7 of the 41, then 7 of the remaining 34, etc.
This yields (for discussion groups) $$ {68 \choose 7} {61 \choose 7} {54 \choose 7} {47 \choose 7} {40 \choose 7} {33 \choose 7} {26 \choose 7} {19 \choose 7} {12 \choose 6} {6 \choose 6} \approx 1.1490756 \times 10^{61} $$ which seems astronomically infeasible (and also factorial in terms of growth).
For cabins, it's mildly better (and the business admits that, when doing this by hand, it's significantly easier to do cabins first): $$ {27 \choose 7} {20 \choose 7} {13 \choose 7} {6 \choose 6} {41 \choose 7} {34 \choose 7} {27 \choose 7} {20 \choose 7} {13 \choose 6} {6 \choose 6} \approx 1.6877279 10^{42} $$ This still seems too large to be computationally feasible without a more principle algorithm.
P.S. Have I calculated the problem size correctly?
