Mathematics of Love: Optimizing a Dining-Room Seating Arrangement for Weddings with Python

Dr. Hannah Fry‘s book, The Mathematics of Love [1], is one of those rare finds, smart, funny, and incredibly easy to read. I enjoyed it so much that I ended up giving copies to some of my closest friends. They loved it too, but a few of them hit a snag with Chapter 8, which, ironically, was the chapter they were most excited about.

This chapter goes into the tricky business of organizing wedding seating arrangements, using mathematical programming and optimization to figure out how to seat guests so everyone has the best time possible. Sounds cool, right? But here's the catch, the book doesn't actually walk you through how to set up or solve the problem, which left my friends feeling a bit lost.

Now, I know what you're thinking: wedding seating? Really? But don't be fooled , it's a really difficult problem to solve, and the solution has way more applications than just weddings (although this one is already important). Think organizing tables on cruise ships [3], forming sports teams or workgroups, optimizing portfolios, and in my world as a business school professor, putting together effective teams for group projects (group conflicts and free riding have dramatically decreased since I started organizing groups with the methodology described in this article). So yeah, it's a problem worth knowing how to solve, at least in my humble opinion.

In this article, I'm going to pick up where Dr. Fry left off and show you how to actually tackle this problem using Python and Gurobi. We'll start by breaking down the problem, then jump into the details of it's Mixed Integer Programming (MIP) formulation. After that, we'll bring in a sample dataset and solve it step by step. And to wrap things up, I'll talk about some cool extensions and advanced methods you can use to take this even further.

Now If you have never used Gurobi before, especially from Google Colab (The IDE that we will use in this article), I invite you to read one of my previous articles where I explain how to set up your Gurobi web license in your Colab environment. You can find the link to the article below:

Optimizing Project Schedules: Using Gurobipy and Cheche_pm warm-starts for Efficient RCPSP…

If you also need a tutorial and more information about linear programming (LP) or integer programming (IP) techniques I strongly recommend you to check these excellent articles written by Bruno Scalia C. F. Leite, I am leaving the links down below. Another great source is William's HP book about Mathematical Programming [2].

Linear programming: Theory and applications

A Comprehensive Guide to Modeling Techniques in Mixed-Integer Linear Programming

Article index:

• The Problem
• MILP formulation of the RQMKP
• Installing the libraries and setting up the Colab environment
• Problem Data
• Solving the RQMKP
• Visualizing the RQMKP solution
• Conclusions
• References

The Problem

As Dr. Hanna Fry puts it, aside from choosing a terrible best man to give the speech, one of the biggest mistakes a couple can make at their wedding is seating enemies at the same table (In my home country not having enough tequeños would also be considered a mortal sin). Make that mistake, and you're in for a night of icy glares, passive-aggressive comments, and, if alcohol is involved, maybe even a brawl. Getting the seating arrangement right can make a world of difference in the overall vibe of the big day.

Every optimization problem has an objective function, and in this case, our goal is to maximize the total happiness of the guests. Guest happiness depends on how they interact with each other. Let's take an example: Pongo and Cruella. Cruella loves Pongo's beautiful hair, so the interaction term from Cruella's side is +1. But it's not always mutual – Pongo, worried about Cruella's obsession with his fur, feels uneasy, so his interaction term is -1. If they're seated together, their happiness cancels out to zero. Now, imagine doing this for 100 guests instead of just two. How much harder does it get? If you try to brute force the Sh-t out of this, you'll find that there are 100 factorial (100!) ways to arrange the seating – that's an astronomical number. This is precisely why mathematical optimization is our best bet.

To make matters more complex, we have constraints to consider. It's not just about maximizing happiness; we also need to respect the table capacity limits and keep couples together (they tend to be angry if they are separated). So, our problem is to find an assignment of guests to tables that maximizes total happiness while respecting these constraints.

Now, here's a philosophical twist: Should we aim to maximize the total happiness of the entire venue, or should we try to maximize the happiness of the least happy table? Which approach is fairer to our guests? What if maximizing total happiness makes one table absolutely miserable? Don't worry, this article will tackle both approaches, but I am leaving the question open as food for thought.

These kinds of problems are known in the literature as quadratic assignment problems. However, the specific problem we're solving here can be addressed as a Restricted Quadratic Multiknapsack Problem (RQMKP).

You've probably heard of the Binary Knapsack problem – there are tons of articles on Medium about how to solve it, I'll leave a link to a cool Knapsack article written by Maria Mouschoutzi, PhD below.

How Many Pokémon Fit?

But the RQMKP? That's what the Knapsack problem evolves into after eating its vegetables, getting eight hours of sleep, and hitting the gym five times a week. This isn't just a Knapsack; it's "the" Knapsack problem – the Goku Ultra Instinct version of it. It's been proven to be strongly NP-Hard [6], which makes it a real beast to solve.

Unlike the regular Knapsack problem, the RQMKP involves multiple ("M") knapsacks that need to be filled. The objective function includes both quadratic ("Q") and linear terms, which, in our case, represents happiness – a function that, I should remind you, we need to maximize. The "R" stands for restricted, meaning we must place each item into one of the available knapsacks without exceeding their individual capacities, but every item has to be placed somewhere.

In our wedding dining context, when we focus on maximizing the total happiness of the event, we're dealing with the Max-Sum variant of the RQMKP. When we aim to maximize the happiness of the least happy table, we're looking at the Max-Min variation (we are maximizing the minimum of the tables).

Now that we have a broad understanding of the problem, let's discuss the formal mathematical programming formulations.

Mathematical formulation of the RQMKP

We'll start out with the simpler version of the problem, the Max-Sum RQMKP. Once we've tackled that, we'll move on to the more challenging Max-Min variation.

The Max-Sum RQMKP

A mathematical formulation of the Max-Sum RQMKP problem is presented in Figure 1 below.

At first glance, the formulation above might seem daunting, but it's actually quite straightforward. It uses binary variables x_{i,k}, which equal 1 if guest i is seated at table k, and 0 otherwise. The objective function is simply the sum of the interaction terms c_{i,j} for all pairs of individuals {i,j} who are seated together at the same table.

1. Constraint (1) ensures that for each individual i, only one binary variable x_{i,k} equals 1, meaning each person can be seated at only one table.
2. Constraint (2) makes sure that the number of guests at table k does not exceed its maximum capacity B_k. Note that different tables might have different capacities, which is why there's a specific parameter B_k for each table.
3. Constraint (3) ensures that all couples {i,j} in the set of couples E are seated together at the same table k.
4. Finally, Constraint (4) guarantees that the variables x_{i,k} remain binary.

The Max-Min RQMKP

A mathematical formulation of the Max-Min RQMKP problem is presented in Figure 2 below. This formulation is slightly more difficult, but nonetheless easy to grasp.

This formulation is very similar to the Max-Sum-RQMKP, but here, the objective function is a new variable ζ that we are trying to maximize. Constraint (1) forces ζ to be less than or equal to the total happiness of each individual table. This means that, in the best-case scenario, ζ represents the happiness of the least happy table.

The rest of the constraints (2–5) are exactly the same as in the Max-Sum case, so there's no need to repeat them.

With the formulations in place, let's proceed to set up the environment to solve these problems.

Installing the libraries and setting up the Colab environment

To use Gurobi in Google Colab, we first need to install it using the following code:

!pip install gurobipy

Once installed we can proceed to import the required libraries for this project.

import pandas as pd
import numpy as np
import networkx as nx
import matplotlib.pyplot as plt
import gurobipy as gp
from gurobipy import GRB
from google.colab import userdata

We're going to use the standard "mirepoix" (

Tags: Data Science Editors Pick Operations Research Python wedding-planning

Comment