Running Dinner - Solving a Real-World Math Puzzle with Linear Programming
6 min read
Have you ever heard of a Running Dinner, or maybe even participated in one? If not, then let me explain and show you that it is actually a mathematical puzzle. Don’t worry, this post doesn’t contain any mathematical formulas and no mathematical knowledge is required to understand the content. If you disagree after reading, then please reach out to me.
At a typical Running Dinner, 3 courses are served by 3 different people or teams. Usually a team consists of 2 people, it’s also possible to have just 1 person or more than 2 prepare a course.
Now here’s the catch: each course is also served at different places - the teams have to “run” to the host to enjoy their course. Hence the name - didn’t see that one coming, did you?
To make it more interesting, teams are mixed up differently for each course. Ideally, one team never dines with another team more than once.
Here’s an example to make the concept more tangible:
There are 9 teams called team 1, team 2, team 3, … you get the gist.
And here’s a possible combination for those teams:
Mix & Match
With this description, the Running Dinner is simply a combinatorial problem. Any combination with no repeating matches is a valid solution.
Cool, cool - then this is the end of this newsletter. Have a lovely day.
Buuuuut…
Maybe not every solution is desirable?
What if in our example teams 1, 4 and 7 are neighbours, so they don’t have to spend so much time commuting from one place to the next - at least in one round. That’s pretty convenient!
On the other hand, what if in the same round teams 2, 5 and 8 live on different ends of the city and it takes each of them at least 45 minutes to get from one place to the next. The food will probably be cold when they get there.
Wouldn’t it make sense to combine teams in a way that all of them have to spend as little time commuting as possible?
With this additional condition, the Running Dinner becomes an optimisation problem. And those can be solved with Linear Programming.
No Mathematics Here - Please keep on reading
As promised, I will not use any mathematical language here.
A linear program consists of 2 parts:
Optimisation function
For the Running Dinner, we are aiming to minimise the commuting time for each team.
Constraints
Those are the conditions the solution needs to fulfill, e.g. one team has to prepare exactly one course.
The optimisation function for our Running Dinner is quickly explained. Every team has their own combination of places to go to. The total commuting time for a team is the sum of each individual commute:
Commuting from their own place to course 1
Commuting from course 1 to course 2
Commuting from course 2 to course 3
The goal is to find a solution which minimises the total commuting time for all teams put together. Easy peasy, right?
As mathematics is just an abstraction of the real world, simply working with the optimisation function would lead to illogical solutions.
For example, the shortest commuting time for each team is … no commuting at all. So everyone just stays at their own place, cooking a 3-course-dinner - normal Saturday night, I’d say.
In order to exclude these types of illogical solutions, we have to set constraints, clarifying which solutions are acceptable and which are not.
Constraints have the purpose to make the abstract mathematics of the linear program resemble the real world. They function like a filter, filtering out all solutions which do not comply with every single constraint.
Important to notice is that constraints are anarchical (I love writing this). They are all equally considered. It is not possible to define
If constraint X is not met but constraint Y is, then ignore constraint X.
You would have to find a way to formulate this in a way that all constraints are fulfilled.
What are the constraints for the Running Dinner?
Duh!
There are some obvious ones. They are in fact so obvious that you wouldn’t explicitly formulate them in a normal conversation, as they are just common sense. This is how dumb mathematics can be - and that’s why I firmly believe that there will never be a “Super AI”, but I’m digressing. Let’s take a look at these constraints:
Every team is hosting exactly once and has exactly 1 route.
Basically this means ensuring that every team is part of the solution and that they don’t have more than one solution. For example, Team 6 cannot be left out of the fun altogether.
Also, Team 7 cannot go to both Team 1 and Team 2 for the starter - simply because they cannot be at different places at the same time. Well, theoretically the teams could split up, but that’s not the point.
A team must not be paired with themself and they have to be part of their own route.
For example, the following is not an acceptable solution: Team 1 having the first course at their own place, as well as the second course.
This scenario could then lead to Team 5 not hosting at all.
At every course there are exactly 3 teams at the same place.
For example, Team 2 is hosting course 1. The final solution has to ensure that besides Team 2 two other teams are going to their place as well. An unacceptable solution would be if only one other team would be assigned to Team 2 for course 1.
Playing by the Rules
The following constraints reflect the specific setting of the Running Dinner:
Every course is hosted by exactly one third of the number of teams.
The total number of teams has to be divisible by 3. For example, if there are 9 teams, then 3 of them have to host course 1, another 3 course 2, and another 3 course 3. An unacceptable solution would be to have only 2 hosts in course 1.
Every team is paired max. once with another team.
For example, Team 1 and Team 4 cannot have both the first course at Team 1 and the second course at Team 4.
And there’s our Running Dinner program. Did you spot any mathematics here? If yes, then please tell me where exactly!
If you’re actually interested in the purely mathematical formulation and python code of the Running Dinner problem, then check out the notebook in my github repository.
Hi, I'm Nadine. I’m a mathematician and have more than 12 years experience in data analysis, data science and leadership. I empower people through comprehensive training and coaching in data analysis and mathematical modelling, equipping them with the tools and knowledge to excel professionally. If you’re interested in finding out how I can support you in your learning journey, book a free 30-minutes introduction call with me right here, or send an email to nadine@mathemalytics.com.