Wedding Seating Optimization

The Problem

Our wedding was largely DIY. We had a hundred things to worry about, and fussing over table assignments was near the bottom of the list. Of all the planning tasks, there wasn't much I wanted to do less than seating.

I had just joined Grubhub's Decision Science team, where I was working on the autodispatch system, a MIP that assigns couriers to deliveries. It occurred to me that the formulation could be generalized: couriers to deliveries, guests to tables, same structure. My colleagues and I set out to develop a formulation that was adequate for the problem and performant enough to solve in reasonable time.

Our first attempt modeled affinity as distance on a social graph between guests. When the solver produced questionable pairings, we layered on explicit weight overrides to force certain guests apart. Two weeks before the wedding, the solver seated the bride's father at the same table as her single friends despite a -10,000 penalty. We scrapped the whole thing and rewrote it in FICO Xpress with explicit pairwise affinity scores: less elegant than graph distance, but it gave us direct control over the inputs that actually mattered.

The Approach

The seating problem is a constrained assignment problem. Each guest party needs to be placed at exactly one table, subject to capacity limits and relationship constraints. The natural formulation is a mixed-integer program (MIP): binary decision variables for assignments, linear constraints for capacity and compatibility, and a linear objective that maximizes total "happiness" across all tables. The original implementation used FICO Xpress; the interactive demo below is a rewrite in GLPK.js (GLPK compiled to WebAssembly), running entirely in your browser.

Formulation

Let $P$ be the set of guest parties, $T$ the set of tables, and $a_{ij}$ the affinity between parties $i$ and $j$ (positive means they want to sit together, negative means keep them apart).

Decision Variables

$x_{p,t} = 1$ if party $p$ is assigned to table $t$.

Linearization

To express "parties $i$ and $j$ are at the same table," we introduce continuous variables $y_{i,j,t} \in [0, 1]$ with McCormick envelope constraints:

Since the $x$ variables are binary, $y_{i,j,t} = x_{i,t} \cdot x_{j,t}$ at any integer feasible solution.

Constraints

Each party is assigned to exactly one table:

Table capacity is respected:

where $s_p$ is the size of party $p$ and $C_t$ is the capacity of table $t$.

Objective

Maximize total happiness across all co-seated pairs:

The solver also supports alternative objectives: maximizing the minimum per-table happiness (fairness), or minimizing the spread between the happiest and unhappiest tables.

Symmetry Breaking

Because the tables are interchangeable, any solution can be trivially "improved" by relabeling tables. Swapping table 1 and table 2, for instance, changes nothing about who sits with whom. With $|T|!$ equivalent permutations of every solution, the branch-and-bound search wastes enormous effort re-exploring symmetric branches that lead to the same objective value.

To break this symmetry, we let the user fix the assignment of some guests to a particular table. These are natural choices: my parents at this table, the best man's family at that one, and so on. For each anchor party $p_k$ assigned to table $k$:

Each anchor party gives its table a unique identity, collapsing the $|T|!$ equivalent permutations down to one canonical form and dramatically reducing solve time.

Results

The solver found a provably optimal assignment in under 30 seconds. We attempted to solicit feedback on the perceived optimality of the seating arrangements, but the response rate from our guests was too low to draw any meaningful conclusions, a result we attribute to confounding factors including an open bar.