1
$\begingroup$

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

  1. 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?)
  2. 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?

$\endgroup$
2
  • $\begingroup$ You didn't account for the symmetry of the groups when calculating your problem sizes. But it doesn't really matter, brute force is still not an appropriate approach. $\endgroup$ Mar 5 at 1:36
  • $\begingroup$ @user1502040 interesting insight; thanks. Can you provide more details about where the calculation went wrong, for my own benefit? $\endgroup$ Mar 5 at 16:55

1 Answer 1

1
$\begingroup$

A standard approach that is very general is to formulate this as an instance of integer linear programming, and apply an off-the-shelf ILP solver. The field of operations research deals with a lot of combinatorial optimization problems, such as arise in scheduling and logistics, and ILP solvers are one standard tool for this (there are other tools as well).

Solving ILP is NP-hard in the worst case, so it's not always feasible to solve for large problems, but for the kind of problem you mention, I expect it will be very flexible and will be sufficient for your needs.

In some special cases, where the constraints/requirements have a particular structure, we can solve this with specialized algorithms, such as maximum bipartite matching, algorithms for the assignment problem, network flow, etc. Those algorithms have the benefit of scaling very well to large problem sizes. But they are not flexible: they can only accommodate very specific types of constraints and restrictions. So if they don't apply, you can fall back to the "big hammer" of ILP solvers, SAT solvers, and/or off-the-shelf optimization algorithms.

$\endgroup$
1
  • $\begingroup$ Ah, I had wondered about ILP, but I couldn't see a translation (it's an area I'm only familiar with in passing). Do you have any recommended reading (textbooks, articles, tutorials, etc.)? $\endgroup$ Mar 5 at 16:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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