Combinatorial problem in my daughter’s class

Question

In Denmark, a rather substantial amount of work and effort has gone into reducing bullying in the Danish public schools. Many initiatives, which purposes are to strengthen the unity and solidarity in the individual classes, have been introduced (and this with quite remarkable results actually).

One of these initiatives is the so-called “Dinner with friends” initiative. The idea is that the kids in a class should go home to each other for dinner in small groups of four to five kids. These visits to each other’s homes should happen approximately 6 times a year (three times in the fall and three times in the spring) and each time the groups are different such that the kids get to visit and dine with as many of their class mates as possible. The reasoning behind the initiative is that you do not bully those with whom you have dined.

Making such a “Dinner with friends”-plan is obviously a combinatorial optimization problem (at least it is to me)!

The plan for the 6 events during the year should be such that

• at most 5 kids go to the same dinner arrangement
• at least two girls and two boys go to each dinner arrangement,
• all kids should try to be the host of a dinner at least once a year,
• if kid $j$ is host at a dinner, then this kid cannot be a host for the next event (for the sake of the parents)
• Each kid should go to exactly one dinner on each of the event days (possibly as a host)

The objective is to maximize the number of different pairings of kids during the events. That is, if $z_{ij}$ is a binary variable equaling one if kids $i$ and $j$ go to the same dinner at least once during the 6 events, then the objective is to maximize the sum over these $z_{ij}$-variables.

I have a working ILP formulation using the following variables:

• binary $y_j^e$-variables that equal one if kid $j$ is host at event $e$,
• binary $x_{ij}^e$-variables equaling one if kid $i$ goes to kid $j$’s house during event $e$,
• binary $z_{ij}$-variables equaling one if kids $i$ and $j$ go to the same dinner at least once during the six events.

However, my model is not very elegant! Therefore, I have two questions:

1. Is this a known problem in the literature? To me, it is somewhat similar to graph partitioning but not all the way there. There is also an element of scheduling in the problem, but I am embarrassingly unfamiliar with the scheduling literature.
2. I have a feeling that this problem could be formulated much more elegantly with different variables. Could you suggest a way to formulate the problem elegantly?

Answer 1

This is a variant of the University Course Scheduling problem (e.g. this one). Interestingly, writing software to solve this was Bill Gates' first gig when he was still a student.

There is a lot of software around for this type of problem (just google course scheduling software).

It's also very similar to sports scheduling (e.g. how the NFL schedule is calculated, including pairing teams), so you could check that out too.

There are many ways to model this and it can get very complicated - one of the hardest bits is if you want to pair children, i.e., if I have dinner at Mark's I have to have Mark over for dinner. The simplest way is saying that each child must have dinner at least 6 times, and that no one child can host more than some number of dinners.

Paired scheduling (like they do with sports teams), is actually a supercomputing problem, so be mindful that this is an inherently very hard problem. If your formulation is not working out try dropping some of those constraints, especially on when people are available, and it should be manageable.

This is also infinitely easier if you pre-select the hosts and times, and then try to assign guests.

Answer 2

This reminds me of the Progressive Party Problem, for which an elegant MIP formulation is given here:

Erwin Kalvelagen, On solving the progressive party problem as a MIP. Computers & Operations Research 30 (2003) 1713–1726

An AMPL implementation of this formulation, and an alternative approach for getting a good solution faster, are described in my tutorial, Identifying Good Near-Optimal Formulations for Hard Mixed-Integer Programs. See the example headed "Breaking Up 3" beginning on slide 36.

Answer 3

As wsg mentioned in a comment, your problem is related to the Social Golfer problem. You can find references on the web and in the OR literature under this naming. For example, have a look at this webpage or this one. This problem has tight connections to Latin square, Kirkman's schoolgirl problem, and more generally combinatorial design problems. This is a historical benchmark for Constraint Programming (CP) solvers.

Your ILP formulation is good. You should be able to solve it by using free MILP solvers like COIN-CBC or even GLPK if the number of kids is very small. But for classes with 20-30 kids, given our experience with this problem, it may be quite difficult to get solutions. Indeed, as pointed out Nikos above, the modeling of the pairing (your variables z[i][j]) leads to quadratic binary expressions. These expressions can be linearized as described here on the forum. Once linearized, these ones make the linear relaxation of the ILP very bad while increasing the size of the ILP (because the number of z[i][j] variables grows quadratically).

Thanks to its local-search heuristics, this is the kind of highly combinatorial problems for which LocalSolver is able to deliver good solutions quickly, despite the bad, useless linear relaxation. The LocalSolver model for the Social Golfer problem is given here in the Example Tour, for languages like Python, Java, C#, or C++. LocalSolver is a commercial product but if you're interested to use it for free to solve this problem, you will be welcome.