#8 📈 I just got married and I had to solve an optimization problem… At the wedding!
#8 📈 I just got married and I had to solve an optimization problem… At the wedding!
Getting married is a piece of cake, but seating your guests? That's the real challenge!
Seating arrangements can make or break a wedding.
It's like a dance, ensuring that diverse groups of friends and family come together harmoniously. Mismatched leave attendees bored or uncomfortable.
Today we’ll see in Feasible how mathematical optimization can create seating charts that will blow your guests away.
You might think it's not a big deal, but there are even scientific articles about it.
Let's go for it! 😎
The Delicate Art of Seating Guests
Imagine your dream wedding: friends and family gathered, love in the air, and everyone celebrating your union.
But creating a harmonious atmosphere for all can be quite the challenge, especially when it comes to seating arrangements. One wrong move, and you could end up with awkward encounters, discomfort, or even conflicts among your guests. It's essential to carefully consider the preferences and dynamics of your attendees to ensure an enjoyable experience for everyone.
You’ll see.
For just 100 guests to be seated at 10 tables of 10 people each, there are more possible seating combinations than atoms in the universe! Yes, you read that right. But how can we calculate the exact number? (if you are curious enough you can go to the formula at the end)1
So if we had 100 guests and 10 tables with 10 seats each to seat them, we would have:
6,495465689×10⁸⁵ possible combinations
And there are around 10⁸⁰ atoms in the universe. Or say it different: a 1 followed by 80 0s…
100000000000000000000000000000000000000000000000000000000000000000000000000000000.
So add it 5 more 0s and then you get the total possible combinations for your wedding -for just 100 guests!
Now your problem of seating guests at your wedding has come to a totally different dimension, right? You know exactly why is so difficult to do that part of the wedding -apart from some guests asking you to be seated together and so on.
Ok so how can we define the problem in a more analytical way? What we have is:
Assign n guests to j tables
Tables have capacities
Guests have preferences
Some guests cannot be seated with others
Some guests must be with others
With two goals in mind:
Satisfy all the above constraints.
Maximize some metric -like total affinity among guests in the same table.
Let me introduce you to…
The Science Behind Perfect Seating
There's a secret weapon that can help you navigate this seating conundrum: Operations Research. It's a field of study that uses elegant techniques to balance preferences and maximize satisfaction. In this newsletter, we will explore how mathematical optimization can create seating charts that are nothing short of magical.
Let's break down the problem into three main parts: data, mathematical modeling, and algorithms. Each of these components plays a vital role in crafting the perfect seating arrangement.
First things first: data. Is there a mathematical way to express the relationships between your guests? Absolutely! Meet the mighty graph. Think of each guest as a node and the connections between them as edges. These connections can represent the relationships and preferences among your guests. Are they friends? Assign a positive weight to the link. Are there any tensions? A negative weight should do the trick.
🥳 Now, here comes the fun part.
By assigning weights to the links based on friendships and preferences, we can create a numerical representation of the dynamics within your guest list. A numerical representation like:
-2 would represent a pair of guests that cannot be seated together.
-1, a pair of guests that are not so friends.
0, a pair of guests that are indifferent to be seated together.
+1, a pair of guests that are friends.
+2, a pair of guests that need to be seated together.
Next, we dive into mathematical modeling. This is where we transform the real-world complexities into a structured format. We define decision variables, constraints, and an objective function.
Decision variables help us determine which table each guest will be seated at, while constraints ensure that guests with certain relationships are seated apart or together. The objective function is our guiding star, aiming to maximize happiness and create harmonious tables.
But how do we solve this complex optimization problem? Algorithms come to the rescue!
There are two main approaches: exact solutions and approximate solutions. Exact solutions require formulating the problem in a mathematical language and using a solver. This method is perfect if you need a precise seating arrangement. On the other hand, approximate solutions involve creating an algorithm to find a close-to-optimal solution. These algorithms leverage existing frameworks. How to choose the approach? In this case I would go with the exact way of solving the problem: you only need to solve it once. But for a more general understanding I will write a post around the topic 😉.
Now, I have fantastic news for you. Software solutions like Perfect Table Plan have been developed specifically to solve this problem. They take your input data, apply mathematical modeling and algorithms, and provide you with an optimized seating arrangement. The hard work is done for you, so you can focus on other aspects of your special day.
Of course, it's essential to review the generated solutions and ensure they align with your specific needs. Customization is key to creating an unforgettable experience for your guests.
Conclusion
Optimal seating arrangements play a vital role in creating a positive and enjoyable atmosphere at your wedding. Thanks to Operations Research, we can harness the power of data, mathematical modeling, and algorithms to craft seating charts that will leave your guests smiling from ear to ear.
If you want to read more about this problem, there are some papers that may get your attention:
See you in the next issue.
Best regards.
PS: some exciting things are coming for Feasible… 😏 Stay tuned!
There are n! ways to order a list of n people. And after that, we group them into j groups (tables) of size k each -let’s assume an exact division is possible for simplicity.
In each group, there are k! different ways to order the people, but all these are considered equivalent for our purposes (we don't care what order people are listed within a table). So we divide by k! and do it j times, once for each table.
We could then shuffle all the groups, and all the results of such shuffling are also considered equivalent. So we divide by j! to count for these permutations.
So in the end we have the following formula:
And it's just a matter of substituting n, j, and k to find out the total number of combinations.