23
$\begingroup$

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?
$\endgroup$
  • 1
    $\begingroup$ It reminds me a bit of the social golfer problem: see here and here However, the SGP doesn't have the component of one child being the host. Your formulation seems good to me, I don't see an immediate way to change it. One option might be to split it into two problems: first decide on the groups, then decide on the host for each group. I have a feeling that this would work just as well as the complete model. $\endgroup$ – wsg Oct 8 at 11:53
  • $\begingroup$ @wsg awesome, thanks! $\endgroup$ – Sune Oct 8 at 13:39
  • 1
    $\begingroup$ "The reasoning behind the initiative is that you do not bully those with whom you have dined." Is there any evidence for this idea, when it's forced to happen by the system rather than happening organically due to friendships? It also seems like it would put underprivileged children at a disadvantage compared to their wealthier peers (the families might have difficulties affording the extra food needed for these government-mandated dinners), as well as possibly resulting in them getting more bullying for being poor, or inducing bullying where there was none to begin with. $\endgroup$ – nick012000 Oct 9 at 4:17
  • 2
    $\begingroup$ I feel like the gender split should come into this somewhere - if 2 girls, 2 boys should be in each group and each group should be different then dealing with the pairings between all girls and all boys first and then thinking about joining those two sets together reduces the complexity of the problem slightly. Not quite sure how to formulate that into an answer though. $\endgroup$ – Lio Elbammalf Oct 9 at 10:22
  • 1
    $\begingroup$ @nick012000 In fact, no one is force to do anything by "the system". "Free from bullying"(friformobberi.dk) is a collection of initiatives a class can choose to use or not. It is the parents of the class that democratically agree on what to do and what not to do. And yes, there is actually quite a lot of evidence pointing to the fact that the Free from bullying intiatives work as a whole. Unfortunately, the report is in danish but you can find a large report made by the University of Southern Denmark here: sdu.dk/da/sif/rapporter/2019/skoleboernsundersoegelsen_2018 $\endgroup$ – Sune Oct 9 at 11:24
10
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ My model actually works okay. I can solve the problem and from a few (non-rigorous) tests it seems that the model is correct. But it is not at all elegant. And regarding the computation times, that doesn't seem to be a problem given the relatively small size (around 20 pupils in a class) $\endgroup$ – Sune Oct 8 at 13:37
  • $\begingroup$ Do you happen to have any references for how this works in practice for sports scheduling? For example what techniques/software the NFL actually uses to schedule games? When you say that it's a supercomputing problem, do you mean that, e.g., the NFL actually uses a supercomputer to do their scheduling? I'm a physicist by training who is really into sports, and I find this topic fascinating. $\endgroup$ – d_b Oct 8 at 19:49
  • $\begingroup$ The NFL schedule is created using Gurobi, see here. There are several other sports scheduling companies, e.g. Ligalytics. $\endgroup$ – ktnr Oct 9 at 7:27
  • $\begingroup$ @d_b Yes, ktnr's link has pretty much everything. $\endgroup$ – Nikos Kazazakis Oct 9 at 8:57
7
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • 4
    $\begingroup$ Hello and welcome to OR.SE Dr. Fourer. $\endgroup$ – Oguz Toragay Oct 8 at 19:46
  • $\begingroup$ Indeed, it's great to have you here :) $\endgroup$ – Nikos Kazazakis Oct 9 at 8:55
6
$\begingroup$

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.

| improve this answer | |
$\endgroup$

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.