Optimizing the Seating Arrangement for My Wedding

Weddings are joyous occasions, especially when you're the one getting married, but the logistics can be a bit daunting—especially when it comes to seating arrangements. Imagine this: hundreds of guests (I'm Italian, what did you expect), each with their own relationships, preferences, histories. Placing them in the optimal arrangement is a puzzle worthy of any data enthusiast and bona-fide crazy person.

Here’s a glimpse into how I tackled this challenge using some nifty data science techniques.

The Challenge

The goal was to seat guests in a way that maximizes overall happiness and minimizes potential friction. Sounds simple, right? But when you factor in old family feuds, new friendships, and everything in between, it becomes quite the conundrum.

The Approach

Data Collection

First, I gathered information about the guests—who gets along with whom, any potential conflicts, and group dynamics. This was turned into a numerical representation that could be fed into our algorithms.

Mathematical Formulation

The problem was formulated as a Mixed-Integer Linear Programming (MILP) problem. We defined:

• function to be minimized:

$$ \min_{x_i^j, x_i^k} \sum_{i=0}^n \sum_{j=0}^{m-2} \sum_{k=j+1}^{m-1} \left( - C^{j,k} p_i^{j,k} \right) $$

• constraints:

$$ \sum_i^n x_i^j = 1, \forall j $$ $$ a \leq \sum_j^m x_i^j \leq b, \forall i $$ $$ x_i^j, x_i^k, p_i^{j,k} \in \left{ 0, 1 \right} $$ $$ a x_i^k \leq \sum_j^m p_i^{j,k} \leq b x_i^k, \forall i,k $$ $$ a x_i^j \leq \sum_k^m p_i^{j,k} \leq b x_i^j, \forall i,j $$

given:

• $n$ tables, and $m$ guests
• $ x_i^j = 1 $ if guest $j$ sits at table $i$
• $ p_i^{j,k} = x_i^j x_i^k = 1 $ if guests $j$ and $k$ both sit at table $i$
• $a$ and $b$ respectively the minimum and maximum number of people at a table
• $C^{j,k} = f(j,k)$ is the connection score between guests $j$ and $k$.

Furthermore, the connection score will be calculated based on the following empirical formula:

$$ C^{j,k} = \sum_{p} c_p \alpha_p^{j,k} $$

where $p$ parameters are taken into account, including:

• partnerships
• languages
• age
• city of residence
• interests
• etc...

Data preparation

The collected data was meticulously prepared for analysis. Each guest's information was encoded into numerical values, in a matrix representing their relationships and compatibility with other guests.

Factors such as shared interests, language, age, partnerships, city of residence, and known conflicts were quantified. This preparation was crucial for accurately modeling the problem and feeding it into our optimization algorithms.

Example

Leading to the following connection matrix:

Brute-force optimization

Initially, I used Pyomo to solve the MILP directly. This approach attempted to find the optimal seating arrangement by using a solver, such as GLPK, which uses a Branch and Bound method aided by some heuristics to navigate the solution space.

The problem is defined as follows:

model = pyo.AbstractModel()

model.max_tables = pyo.Param(default=max_tables)
model.tot_guests= pyo.Param(default=tot_guests)

model.max_guests_per_table = pyo.Param(default=max_guests_per_table)

# define our iteration ranges i, j, k, the connection matrix C(j,k) and the variables x(i, j), p(i, j, k)
# p represents the choice of seating guest j with guest k at table i

model.tables_i = pyo.RangeSet(0, model.max_tables - 1)
model.guests_j = pyo.RangeSet(0, model.tot_guests - 1)
model.guests_k = pyo.Set(initialize=model.guests_j)

model.connection_matrix = pyo.Param(
    model.guests_j,
    model.guests_k,
    within=pyo.Reals,
    default=connection_matrix.to_numpy()
)

model.x = pyo.Var(model.tables_i, model.guests_j, bounds=(0, 1), within=pyo.Binary)
model.p = pyo.Var(model.tables_i, model.guests_j, model.guests_k, initialize=0, within=pyo.NonNegativeReals)

# define our rules / constraints

def rule_C1(model, i, j, k):
    return model.p[i, j, k] <= model.x[i,j] if k!=j else pyo.Constraint.Skip
model.connection_matrix1 = pyo.Constraint(model.tables_i, model.guests_j, model.guests_k, rule=rule_C1)

def rule_C2(model, i, j, k):
    return model.p[i, j, k] <= model.x[i,k] if k!=j else pyo.Constraint.Skip
model.connection_matrix2 = pyo.Constraint(model.tables_i, model.guests_j, model.guests_k, rule=rule_C2)

def rule_C3(model, i, j, k):
    return model.p[i, j, k] >= model.x[i,j] + model.x[i, k] - 1 if k!=j else pyo.Constraint.Skip
model.connection_matrix3 = pyo.Constraint(model.tables_i, model.guests_j, model.guests_k, rule=rule_C3)

def rule_one_table_per_guest(model, j):
    return sum(model.x[i, j] for i in model.tables_i) == 1
model.connection_matrix4 = pyo.Constraint(model.guests_j, rule=rule_one_table_per_guest)

def rule_max_guests_per_table(model, i):
    return sum(model.x[i,j] for j in model.guests_j) <= model.max_guests_per_table
model.connection_matrix5 = pyo.Constraint(model.tables_i, rule=rule_max_guests_per_table)

#define the objective function

model.OF = pyo.Var()
def rule_OF(model):
    return model.OF == sum(
        sum(
            model.p[i, j, k] * model.connection_matrix[j, k] for j in model.guests_j for k in model.guests_k if j>k
        ) for i in model.tables_i
    )
model.COF = pyo.Constraint(rule=rule_OF)
model.obj = pyo.Objective(expr=model.OF, sense=pyo.maximize)

While this approach works with a limited number of guests, the real set of invitees (200+) would require age-of-the-universe timeframes with current computational power.

Refining with Genetic Algorithm

Another approach which is often viable whenever the solution space is too large to find a Generally Optimal solution is to use a Genetic Algorithm (GA).

This method mimics natural selection, iteratively improving the solution by combining and mutating previous solutions. It’s like having thousands of virtual wedding planners working simultaneously!

# first, we can define the constraints and the happiness function
def is_valid_max_guests_per_table(ga_instance, solution):
    return all([np.sum(solution == i) <= max_guests_per_table for i in range(max_tables)])

def validate_solution(ga_instance, solution):
    return is_valid_max_guests_per_table(ga_instance, solution)

def happines_func(ga_instance, solution, _):
    if not validate_solution(ga_instance, solution):
        return -1e4
    tables_list = [np.where(solution == i)[0] for i in range(max_tables)]
    return np.sum([
        np.sum([connection_matrix.iloc[j,k] for j in tables_list[i] for k in tables_list[i] if j > k])
        for i in range(max_tables)
    ])

# and then we can instantiate and run the model


ga_instance = pygad.GA(
    num_generations=10000,
    stop_criteria='saturate_50',
    num_parents_mating=15,

    sol_per_pop=50,
    num_genes=tot_guests,

    gene_type=int,
    gene_space=np.arange(max_tables),

    parent_selection_type='rws',

    crossover_type='single_point',
    mutation_type='adaptive',
    mutation_percent_genes=[35, 10],

    fitness_func=happines_func,

    random_seed=12345,
)

ga_instance.run()

Initial Solution with Greedy Algorithm

Realizing that the brute-force approach was computationally expensive, and the Genetic Algorithm didn't lead to good enough solutions, we used a Greedy Algorithm, a straightforward approach where a heuristic is used at any point in time to determine the best next step.

With this approach, guests are seated one by one in the best immediate spot. This gave us a decent starting point but left room for improvement. One option, that I explored, was to provide a seed using the Genetic Algoritm, that the Greedy Algorithm could use as a starting point.

Nonetheless, I soon realized that the algorithm was light enough that it would easily be possible to search the entire solution space by means by initializing a random arrangement, and repeating the process until all the possible arrangements are exhausted.

The implementation of the algorithm is available on my Github.

The Results

Of course, I didn't use the results of this little side projects for something as important and delicate as the seating arrangement at my wedding. And of course, it's not as if I had any say in the matter - my wife chose all the pairings anyway!

Still, this was a really enriching endeavor, and the outputs produced by the final solution were reasonable enough to be a good starting point for the actual hand-picked tables. The results were obviously very sensitive on the initial pick of values for the parameters (does X really wants to sit with Y? What are their actual interests?!?), and their weights (how important is it to sit together a couple - probably very; and what about people from the same city?).

Turning a wedding challenge into a data science project added an extra layer of excitement. It was incredibly satisfying to see the algorithms work their magic, transforming a complex problem into an elegant solution :)

A Jupyter notebook version of this project is also available, also on my Github.

Cheers, Lorenzo