How many meetings would it take for 12 people to meet in 4 groups of 3 until they met everyone?

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


Solution 1:

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.