17
$\begingroup$

I have a group of 12 people that I would like to meet in four groups of three each month. How many minimum months would it take such that each person has been in at least one group with every other person? Below is the brute force method I used to get it to seven months:

enter image description here

$\endgroup$
26
  • 1
    $\begingroup$ Thanks for the link. That A) explains what you want to do, and B) serves as context showing that you have worked on this yourself. I expect the votes to close to subside :-) $\endgroup$ – Jyrki Lahtonen Dec 22 '20 at 15:00
  • 4
    $\begingroup$ It takes at least six months. Each person has to meet eleven others and meets two people a month. The question is whether you can avoid too much duplication so you need another month. $\endgroup$ – Ross Millikan Dec 22 '20 at 15:00
  • 3
    $\begingroup$ Nope. After following that scheme for four months, the not-yet-met people are split into four groups of four. And you cannot arrange all them to meet in two meetings. Need a different approach. Sorry about thinking aloud. $\endgroup$ – Jyrki Lahtonen Dec 22 '20 at 15:34
  • 2
    $\begingroup$ @Sdavid552- I think it's because it doesn't have a "nice" solution; it's like splitting 59 Xmas cookies into bags -- you're going to have some leftovers and it's hard to account for raggedy edges. $\endgroup$ – JonathanZ supports MonicaC Dec 22 '20 at 20:07
  • 2
    $\begingroup$ Some keyphrases that might lead somewhere: social golfer problem. Combinatorial designs. $\endgroup$ – Gerry Myerson Dec 25 '20 at 22:45
8
+50
$\begingroup$

You can solve this set covering problem via integer linear programming as follows. For each of the $\binom{12}{3,3,3,3}/4!=15400$ possible groupings $g\in G$ of 12 people into 4 groups of 3, let binary decision variable $x_g$ indicate whether that grouping is used. For each pair $(i,j)$ of people with $i<j$, let $G_{i,j} \subset G$ be the set of groupings that cover that pair. The problem is to minimize $\sum_{g \in G} x_g$ subject to $$\sum_{g \in G_{i,j}} x_g \ge 1 \quad \text{for all $i<j$}$$ The minimum turns out to be 7.

$\endgroup$
3
  • $\begingroup$ What software did you use to solve this problem? I tried a straightforward solution with Google's CP-SAT solver, where I specified the first set of meetings, and it's been running for a day and a half. I'm using the python version, but I don't think that should matter, since since it takes an eye blink to set up the model, and I presume the optimizer itself is compiled C++ or C code. $\endgroup$ – saulspatz Feb 12 at 15:34
  • $\begingroup$ I used the MILP solver in SAS, and it took less than a minute. This problem is highly symmetric, and a solver that doesn't exploit that will do a lot of redundant work. $\endgroup$ – RobPratt Feb 12 at 15:42
  • $\begingroup$ Thank you. Yes, I couldn't figure out how to exploit the symmetry except by specifying the first meeting. Unfortunately, I don't have access to SAS. Do you know of any free software that would do a creditable job on this problem? (Or do I just need to learn to use the Google tool appropriately?) $\endgroup$ – saulspatz Feb 12 at 16:03

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.