16
$\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
    Commented Dec 22, 2020 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
    Commented Dec 22, 2020 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
    Commented Dec 22, 2020 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
    Commented Dec 22, 2020 at 20:07
  • 2
    $\begingroup$ Some keyphrases that might lead somewhere: social golfer problem. Combinatorial designs. $\endgroup$
    – Gerry Myerson
    Commented Dec 25, 2020 at 22:45

1 Answer 1

Reset to default
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
    Commented Feb 12, 2021 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
    Commented Feb 12, 2021 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
    Commented Feb 12, 2021 at 16:03

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .