How to sort into X bins Y times with minimum overlap?

Question

Let's say I'm hosting a series of dinner parties for a total of $N$ guests. Each night, there are $X$ tables, and we are meeting for a total of $Y$ nights.

I want to preassign the guests to tables such that they are able to meet as many new people as possible over the series of all nights, i.e. they have as few as possible repeat table buddies.

Is there a formula or algorithm for for sorting $N$ items into $X$ bins, $Y$ times, such that there is as little overlap as possible?

P.S. This is a real-world problem for me! In my case, $N=$ about 40, $X=4$, and $Y=4$.

Answer 1

There are $\binom{40}{2}=780$ pairs of people. With $4$ rounds of $4$ tables of $10$ people, you cannot cover more than $4^2\binom{10}{2}=720$ pairs.

Good-Enough Golfers quickly finds a schedule that contains $96$ "conflicts" (repeated pairs) and hence covers $720 - 2 \cdot 96 = 528$ pairs.

Via integer linear programming, I found a schedule that covers $624$ pairs (not necessarily optimal because I terminated the solver):

{5,16,20,23,27,30,32,34,36,37}
{2,3,8,11,19,22,24,28,33,39}
{6,7,10,12,15,17,25,29,31,40}
{1,4,9,13,14,18,21,26,35,38}

{2,3,13,14,16,18,25,29,34,36}
{5,7,20,22,24,28,31,35,38,40}
{6,10,11,12,19,21,26,32,37,39}
{1,4,8,9,15,17,23,27,30,33}

{13,14,15,17,18,22,24,28,32,37}
{1,4,5,9,11,19,20,25,29,39}
{2,3,6,10,12,23,27,30,35,38}
{7,8,16,21,26,31,33,34,36,40}

{11,15,16,17,19,34,35,36,38,39}
{21,22,23,24,25,26,27,28,29,30}
{5,6,8,10,12,13,14,18,20,33}
{1,2,3,4,7,9,31,32,37,40}