Building A Wedding Seating Plan Using Probabilistic Methods & Simulated Annealing

This article covers the Wedding Seating Plan problem which is a combinatorial puzzle of how best to assign guests to tables given that they may want to avoid or be seated with other guests to avoid.

Two in-depth example approaches are examined using a Brute Force Search and Simulated Annealing as well as a summary overview of other typical optimization approaches such as Genetic Algorithms , MILP , WalkSAT, etc

Weddings tend to be stressful events to plan for usually because of the many decisions that need to be made on dates, venue, catering and so on that lead to the need for a lot of alignment between spouses.

Image Source : Dreamstime.com Stock Image

An especially tricky challenge is getting the seating arrangement just right as often there will be certain guests who need to be seated with each other (e.g. possibly because they are immediate or close family members) but also other guests that may need to kept apart (Possibly because some distant aunt holds a grudge against another distant uncle over what some flippant remark he made about her hair-do a decade ago at some other cousin’s wedding )

A Useful But Somewhat Less Mathematical Guide (Source : Brides.com)

Most of the time, you can probably get away with ‘manually’ adjusting the table seating through trial and error but if you have a large enough number of guests and/or tables , it can get rather complicated to do so efficiently given the sheer number of possible configurations you can choose from.

Thankfully , this scenario can be framed as an combinatorial optimization problem and has been studied with a number of different approaches to ‘solving’ it. (I use quotes around ‘solving’ because technically this problem is NP Hard so really it’s about finding ‘good enough’ solutions)

In this article we will walk thru TWO different approaches. The first approach is a (naïve) brute force approach that uses a spreadsheet tool. Even though this only works for small sized problems (i.e it scales poorly), it is useful to build an intuition for the problem. The second approach is via some Python code with a slightly more sophisticated technique called Simulated Annealing. Finally, we’ll round off with an overview of other possible solution methods if you want to further explore the topic.

Full code (i.e the Python Jupyter Notebooks and the XLSM files etc) are available at this Github Link:

ZhijingEu/Wedding-Seating-Problem-Simulated-Annealing

Outline:

• 1.Framing The Scenario As A “Computable” Problem
• 2. Approach 1 : Naive Brute Force Search with Excel
  2.1 Defining The “Cost” Function
  2.2 Developing A Search Algorithm
  2.3 Shortcomings With The Brute Force Approach
• 3. Approach 2 : Simulated Annealing With Python
  3.1 Defining The “Cost” Function
  3.2 Developing A (Better) Search Algorithm : Simulated Annealing
  3.3 Shortcomings With Simulated Annealing Approach
• 4. Other Possible Solution Approaches
  4.1 CNF + WalkSAT
  4.2 Tabu Search
  4.3 Mixed Integer Linear Programming
  4.4 Genetic Algorithms
  4.5 K-Means Clustering
  4.6 Other More Complex Formulations — What If Seating Order Matters ?
• 5. Conclusion

For those of you too lazy to read thru the full details below , this article is also available as a walk thru video here:

1. Framing The Scenario As A “Computable” Problem

At the highest level, any solving approach to this problem involves two steps:-

1.Firstly there is a need to define what criteria makes one seating configuration better than another. Put another way, it is about developing a scoring scheme or a cost function to evaluate any given seating configuration.

Source : Icon Archive Stock Image

2. The next step is to efficiently search through the possible configurations to find the one(s) (there may be more than one answer) that produces the best score (i.e optimizes the ‘cost function’)

Source Image : Adapted From DreamsTime.com Stock Image

This choice of search method determines how long it takes to run the algorithm e.g will the algorithm exhaustively check ALL possible combinations (Hint- this is usually a bad idea as it will not scale well as we will see later…) or will it use some other type of short-cut (i.e a heuristic) to explore only a part of all possible combinations but still come up with a good enough solution ( and if so , given that there could be more than one table seating arrangement that meets the constraints — how will the algorithm know if the solution it found is the best?)

3. There is an implicit third step which is an ‘out the box’ step where we try to reduce computational complexity by only modelling a “subset” of the problem.

Source Image : IStockPhoto

E.g. If you already know one of the tables must be filled by the bride/groom and their immediate family — removing them from the equation helps (a little) to whittle down the potential search space and no of constraints to consider etc.

To give you a sense of just how much — if we take an example of a 96 pax guest list (to keep within the cap of 100 pax as per Singapore’s current COVID safe guidelines for Wedding parties ) with 12 tables of 8pax each — this leads to 1.1214693399503206e+86 (!!!) different possible combinations. (This is even if we ignore the seating positions of the individual guests)

Removing only just 8 pax (i.e 88 pax and 11 tables of 8 pax each ) makes it a slightly smaller figure of 1.0148966011615896e+76 — (i.e a reduction by factor of 1e10 from before)

A related idea is to be clever in how you “kick off” the search process. All techniques below perform a search beginning from some initial starting point . Typically if you don’t know any better — this would be a completely random arrangement. However sometimes solving a simplified version of the problem (e.g maybe run the problem with relaxed constraints and see what it spits out) and using that as the starting point may in fact place the algorithm ‘closer’ to the true global optimum point.(Warm Starting)

2. Approach 1 : Naive Brute Force Search with Excel

Image Source : BruteForceStrength.com

This relatively simple (*) Excel spreadsheet allows users to input a guest list, table size and a listing of up to 3 pairs of people who must either be seated together or seated apart.

(If you are wondering — the guest names were generated using https://www.fakenamegenerator.com)

(*) I say it’s simple but it involves some Excel Macros (Don’t judge me- VBA has it’s use sometimes) for Random Number Generation and other things like adding placeholder seats to ensure all tables are filled (i.e a 92 pax guest list with a chosen table size of 8pax will need 12 tables i.e there will be 4 empty seats)

2.1 Defining The “Cost” Function

Spreadsheet Tool Identifies 2 Violations (Refer to Yellow and Blue for pairs of ppl who should be together but are NOT)

Through a combination of pivot table and lookup formulas, the spreadsheet evaluates any given configuration by comparing every guest at each table with their other co-table guests against the required together/apart conditions. The spreadsheet then counts up the no of “violations" (i.e where a pair who should stay together get assigned to different tables or vice versa for people who should be apart). The ideal goal would be zero violations.

2.2 Developing A Search Algorithm

The spreadsheet tool cycling through the various solution options for a 32 pax , 8 pax per table set up to find a solution

The spreadsheet generates then uses a macro to randomly generate table assignments and loops through multiple iterations until either it hits a pre-defined max number of iterations or it stumbles onto a seating arrangement that satisfies all the constraints.

This is essentially a brute force approach as there is no real technique involved and relies purely on cycling through enough combinations and hoping to be ‘lucky’ enough to find a winner (There may be more than one!). As you may expect, this approach scales very poorly when the number of conditions increase.

Uh-oh. The simulation falls over at 96 pax , 8 pax per table case

However knowing that more often than not, when the numbers grow, the tool may not find a solution — there is a manual adjustment mode that allows the user to step through single iterations and then make changes to the seating allocations.

In the Github link I’ve also included a Python Notebook implementation of the same ‘logic’ just to compare the difference in computational speeds between Excel and Python. The good news is because Python uses a bunch of numpy calculations — it’s almost ~20x faster than Excel VBA.

This code can also serve as the starter code for anybody who wants to adapt it to any of the other techniques discussed later in this article ; )

2.3 Shortcomings With The Brute Force Approach

• This approach falls over when you scale up. The ‘apart’ conditions are fairly easy to satisfy by chance if you only have a few pairs and large enough no of tables but the ‘together’ becomes really hard as the number of tables grow as we are really relying on chance to stumble onto a solution
• Less to do with the Brute Force approach but the way the problem has been framed is that the constraints formulation makes it hard to identify inconsistent constraints e.g when A & B must be together , B & C must be apart but A & C must still be together (Which is impossible because if A & C sit together then B & C would end up at the same table too)
• On the same point about problem formulation — the Together/Apart seating constraints may be too stringent in that they are ‘on/off’ only and cannot handle situations where we may not mind relaxing the constraints to find “good enough" solutions e.g. we may want to absolutely keep some people together (e.g. spouses) but are less fussed for other groups of people (e.g. high school friends should be seated at the same table but if it can’t be done — separate tables are fine too)

3. Approach 2 : Simulated Annealing With Python

Image Source : SciencePhoto.com Stock Image

The following is based heavily on the work of this article below by Linan Qiu. I’ve added some of my own code that

1.Provides the option to either generate ‘dummy’ data for testing or allow users to import guest lists/conditions from the earlier Excel tool

2. Checks the logical consistency of the seating constraints

3.View the results in a more user friendly way.

Wedding Seat Optimization

If you are really interested in how it works , do read the full article above as I won’t be reproducing all the details here.

3.1 Defining The “Cost” Function

The key difference with this improved method of formulating the problem is that it is now possible to refine the “strength of the constraints” better. Rather than just listing the pairs of guest who need to be kept together (negative numbers) or apart (positive numbers)— numerical values are assigned to each constraint where -ve denotes Together and +ve denotes Apart and the larger the score, the bigger the effect.

Using the same example as before for the 92 pax , 8 pax per table scenario and the data is imported into the Jupyter Notebook.

import pandas as pd
import numpy as np
InputFileName="Example_Guests96pax_TableSize8pax.xls"
table_size = pd.read_excel(InputFileName, 'TableSize').columns[1]
GuestListRaw = pd.read_excel(InputFileName, 'GuestList')
guest_list=GuestListRaw["Guest"].values.tolist()
RelMatrixRaw=GuestListRaw.dropna(thresh=2)
RelMatrixRaw
relationships_edges={}
Together1=RelMatrixRaw[["Guest","Together1"]].dropna(thresh=2)
Together2=RelMatrixRaw[["Guest","Together2"]].dropna(thresh=2)
Together3=RelMatrixRaw[["Guest","Together3"]].dropna(thresh=2)
Together1.columns=["Guest","Together"]
Together2.columns=["Guest","Together"]
Together3.columns=["Guest","Together"]
Together=pd.concat([Together1,Together2,Together3])
Apart1=RelMatrixRaw[["Guest","Apart1"]].dropna(thresh=2)
Apart2=RelMatrixRaw[["Guest","Apart2"]].dropna(thresh=2)
Apart3=RelMatrixRaw[["Guest","Apart3"]].dropna(thresh=2)
Apart1.columns=["Guest","Apart"]
Apart2.columns=["Guest","Apart"]
Apart3.columns=["Guest","Apart"]
Apart=pd.concat([Apart1,Apart2,Apart3])
for element in list(zip(Together["Guest"], Together["Together"])):
        relationships_edges.update({element:-50})
for element in list(zip(Apart["Guest"], Apart["Apart"])):
        relationships_edges.update({element:50})

Next , the relationships (which are a dictionary with tuple pairs) are transformed by a nifty library called Networkx and then summarized into a matrix like below:

import networkx as nx
#Generate Relationship Matrix
temp_graph = nx.Graph()
for k, v in relationships_edges.items():
    temp_graph.add_edge(k[0], k[1], weight=v)
relationships_mat_unnormed = nx.to_numpy_matrix(temp_graph.to_undirected(), nodelist=guest_list)
relationships_mat = relationships_mat_unnormed / 100
# View Relationship Matrix
RelationshipMatrix=pd.DataFrame(relationships_mat)
RelationshipMatrix.index=guest_list
RelationshipMatrix.columns=guest_list
RelationshipMatrix = RelationshipMatrix[(RelationshipMatrix.T != 0).any()]
RelationshipMatrix = RelationshipMatrix.loc[:, (RelationshipMatrix != 0).any(axis=0)]
RelationshipMatrix

This makes it easier to see the relationships all at once as the matrix is symmetrical.

The real benefit with this reformulation is that instead of just a score of X no of violations, given some useful matrix properties — it is possible to take the trace of the resulting Seating Arrangement matrix * Relationships matrix (kinda — read the full article by Linan Qiu for the math) and return a single value that reflects how ‘good’ the seating arrangement is (the lower the number the better)

The “Cost Function” evaluation of seating arrangements that the algorithm will use to judge ‘goodness’ and minimize (Lower= Better)

Furthermore having the relationships in a matrix view allows the user to better identify inconsistencies

Modifying the earlier imported inputs with some ‘illegal’ values where Together (A,B) is -50 but Together (B,A) is -75 (as is the case with Mr and Mrs Bao Chin) and impossible circular logic where Together (A,B) at -50 , Together (B,C) at -50 but Apart (B,C) at +50 (as with Mr.Morrison, Mr.Yasser and Mrs.Olsen) using the code as follows….

#CHECKS FOR INCONSISTENCIES BETWEEN RELATIONSHIPS
pairs=[]
rel_values=[]
for pair, rel_value in relationships_edges.items():
    pairs.append(pair)
    rel_values.append(rel_value)
pairs
print("Checking For Pair Inconsistencies")
print(" ")
sorted(pairs[0])==sorted(pairs[0])
rel_values[0]!=rel_values[0]
indicesWithIssues=[]
for i in range(0,len(pairs)):
    for j in range(0,len(pairs)):
        if sorted(pairs[i])==sorted(pairs[j]) and rel_values[i]!=rel_values[j]:
            if i not in indicesWithIssues and j not in indicesWithIssues:
                print("Inconsistency Detected Between:")
                print(pairs[i],":",rel_values[i])
                print(pairs[j],":",rel_values[j])
                print(" ")
                indicesWithIssues.append(i)
                indicesWithIssues.append(j)            
        else:
            pass
print(" ")
print("Checking For Triad Inconsistencies")
print(" ")
all_cliques= nx.enumerate_all_cliques(temp_graph)
triad_cliques=[x for x in all_cliques if len(x)==3 ]
checkSignForTriad=[]
for triad in triad_cliques:
    print("Identified A Triad Consisting Of :",triad)
    for i in range(0,len(pairs)):
        if sorted(triad[1:])==sorted(pairs[i]) or sorted(triad[:2])==sorted(pairs[i]) or sorted([triad[0],triad[2]])==sorted(pairs[i]):
            print(pairs[i],":",rel_values[i])
            checkSignForTriad.append(rel_values[i])
    if (checkSignForTriad[0]<0 and checkSignForTriad[1]<0 and checkSignForTriad[2]<0) or (checkSignForTriad[0]>=0 and checkSignForTriad[1]>=0 and checkSignForTriad[2]>=0):
        print("Triad OK!")
    else:
        print("Triad Inconsistent ! Please Re-Check As All Triangles Should Be ALL Together or ALL Apart")
        indicesWithIssues.append(i)
    checkSignForTriad=[]
    print(" ")
if indicesWithIssues!=[]:
    print("Warning ! If Not Corrected, Errors May Arise")
else:
    print("OK! No Inconsistencies Found")

Running the above ‘consistency check’ script produces the following:

Code automatically detects inconsistencies

Now that we have ‘fixed’ the illegal/inconsitent constraints, we are ready to solve the problem.

3.2 Developing A (Better) Search Algorithm : Simulated Annealing

Simulated annealing is a “probabilistic meta-heuristic technique for approximating the global optimum of a given function in a large search space”

Simulated Annealing From Scratch in Python - Machine Learning Mastery

In metallurgy annealing is the process of heating metal to a high temperature and then slowly cooling it. This slow gradual cooling process is critical because if cooled too fast the atoms would suddenly come to rest wherever they were when the metal was hot, resulting in a random arrangement and a poor quality result. The gradual cooling process allows the atoms to align to the the ‘best’ orientation making the metal more ductile and stronger.

Rather than randomly bashing it’s way through all possible combinations, Simulated Annealing uses a more nuanced approach as follows (taken wholesale from Linan Qiu’s article) :-

1. First, generate a random solution
2. Calculate its cost using some cost function you’ve defined
3. Generate a random neighboring solution
4. Calculate the new solution’s cost
5. Compare them:

• If c_new < c_old: move to the new solution
• If c_new > c_old: maybe move to the new solution

Repeat steps 3–5 above until an acceptable solution is found or you reach some maximum number of iterations.

The core idea is the temperature of the current iteration — based on a pre-determined temperature reduction scale (e.g. a simple linear reduction or more complicated geometric reduction) and the current temperature — the algorithm tends to be more ‘forgiving’ of bad solutions in the early iterations (i.e allowing it to ‘jump’ out of local minimum traps and reach the ‘true’ global optimums)

Source : Review Of Optimization Techniques In Artificial Networks (Ghasemalizadeh et al) , 2016

Performance wise, when we ran this with the Excel Spreadsheet Tool (and even the Python ‘mimic’ of the Excel Spreadsheet Tool at a higher number of 10,000 Iterations), the best it could ever achieve was a Score of 4 violations (vs Target of 0)

Based on the Simulated Annealing Method, it took 1min + to process

Exporting the results back into the Spreadsheet Tool and cross checking, there is still 1 condition not met.

However by ‘relaxing’ the requirements for EXACT solution, we have managed to arrive at a solution that is still a lot better than the Brute Force approach of randomly trying different table arrangements…

3.3 Shortcomings With Simulated Annealing Approach

• While it is much faster than just searching at random , it still takes time to run when the number of guests/conditions increase.
• The solution generated may not be guaranteed to exactly meet all seating constraints (assuming that they are still ‘either/or’ rather than just preferences)
• Simulated Annealing is more complex and requires better understanding of the actual mechanics of the algorithm to adjust the settings e.g. what to set for the initial temperature and what to use for the temperature cool-down schedule.
• While it stands a better chance of finding the ‘true’ global optimum, the algorithm cannot say for sure if the solution it found is truly the optimal solution or just a local optimum…

4. Other Possible Solution Approaches

We’ve only covered 2 approaches above but there are MANY other ways to frame the problem (in terms of the cost function) and different solution search processes. Below are some examples where the first two are cousins to the Brute Force Random Walk and Simulated Annealing approach and a few more distant relatives.

4.1 CNF + WalkSAT

Image Source : WalkSAT Home Page

In the example below, the author has Python code that translates all the constraints into CNF-s Conjunctive Normal Forms which are the product of multiple product of sums or an AND of ORs.

RishabhTyagiHub/Constraint-Satisfaction-Problem — -Wedding-Seating-Arrangement

If that sounds confusing — worry not because if you followed along the Excel example above, you probably already have the gist of it — basically it’s about checking if guest X meets all the criteria of who to be seated together with / apart from. This typically generates a lot of TRUE/FALSE for every pair of guests checked on each table but the key idea in CNF is to reduce the end result of all the preceding checks into a single TRUE or FALSE statement

WalkSAT — Wikipedia

However since the mathematical formulation is more formalized, it can then be solved using a local search algorithm called WalkSAT (SAT=Satisfiability).

WalkSAT is a little bit like a random walk BUT in the first stage of each step, a constraint violated by the current assignment will be randomly selected

The algorithm then randomly tries to ‘flip’ one of the variables appearing in that earlier selected constraint that results in the fewest previously satisfied clauses becoming unsatisfied, with some probability of picking one of the variables at random

If it is unable to find a solution for too long (i.e exploring a dead end part of the solution space) the algorithm restarts with a new random assignment.

So as a crude analogy it’s a bit like a drunkard’s walk except he has a guide dog who knows the way home ‘correcting’ him the right way when he goes off track.

4.2 Tabu Search

Source Image : BoardgameGeek.com

The paper below is a write up of the methodology used by this website WeddingSeatPlanner.com

Wedding Seat Planner

Source : Creating Seating Plans : A Practical Application R.Lewis & F.Caroll 2016

Tabu Search is very closely related to Simulated Annealing but incorporates a ‘memory’ that avoid revisiting poor solutions.

From the Wikipedia page: Local (neighborhood) searches take a potential solution to a problem and check its immediate neighbors (that is, solutions that are similar except for very few minor details) in the hope of finding an improved solution. Local search methods have a tendency to become stuck in suboptimal regions or on plateaus where many solutions are equally fit.

Tabu search enhances the performance of local search by relaxing its basic rule. First, at each step worsening moves can be accepted if no improving move is available (like when the search is stuck at a strict local minimum). In addition, “taboos" are introduced to discourage the search from coming back to previously-visited solutions.

Very sadly , even though the site offers the service FREE , the interface only is via Flash code which since Dec 2020 is no longer supported by any of the main browsers.

4.3 Mixed Integer Linear Programming

Image Source : VectorStock.com Stock Image

Another formulation of the problem is as a Multiple Integer Linear Program. The crux is to use a binary decision variable that denotes whether a guest is assigned to a certain table or not , constrain it so that every guest is only assigned to a single table and a max table size

A simple case implementation can be found in the help documentation for PuLP (A Linear Programming Library for Python that I actually covered in a one of my previous articles)

A Set Partitioning Problem — PuLP 2.4 documentation

There is also a presentation version of the above here. A word of fair warning though, this is only a TOY example and is not optimized for how it does the search process for the best configuration and only uses the default CBC Solver. If you review the code this line is the one that makes it fall over combinatorially:

#create list of all possible tables
possible_tables = [tuple(c) for c in pulp.allcombinations(guests, 
                                        max_table_size)]

When I ran this for the 96 pax , 8 pax /table scenario — unsurprisingly (given that it was probably trying to generate a quintillion combinations and storing it in memory) — it hung my laptop : /

A more sophisticated take using the same general approach can be found in this SAS article below.

Do you have an Uncle Louie? Optimal wedding seat assignments

This example ‘costs’ the unhappiness levels in a similar way but instead uses one of SAS’s proprietary solvers called DECOMP (It’s custom designed to handle situations that have to do with partition sets into smaller sub-sets under some constraints) to better plow through the solution space to find the best solution.

The final example is this next paper that was authored by a husband-wife pair from Princeton who actually used it for their own wedding (which I thought was both super geeky but incredibly sweet)

Finding an optimal seating chart for a wedding

As a contrast to the SAS/OR version- this solution was implemented via GAMS/CPLEX (another optimization solver program) and has a slightly different formulation in that it tries to maximize the number of people each guest knows at their table i.e This time there are no ‘hate/keep apart’ seating constraints ; )

Regardless of the exact implementation details , the benefit of the MILP family of approaches is that since the solving methods usually use a “back-tracking search” strategy (e.g. Branch & Bound Method) , assuming you are not in a hurry* , this approach eventually GUARANTEES that the solution found will be the global optimum solution or will prove that there is no solution.

*If you read the article from the Princeton couple, for their wedding reception party of 107 people with table sizes of 10 , it took 36 hours to comb through the 2.69e+111 possible combinations —However the paper was written in 2012 so hardware improvements today may have better performance)

4.4 Genetic Algorithms

Image Source : VectorStock.com Stock Image

Unlike Simulated Annealing which ‘tracks’ only a single state and decides at each iteration whether to ‘move’ to a neighboring solution , Genetic Algorithms generate a population of possible solutions , pick the best ones (based on the cost scores) to combine them (cross-over) and applies some random changes (mutations)

This Github link below is an example of a Genetic Algorithm approach to the Wedding Seating Problem written in R where in the author’s own words: it uses a binary chromosome(each guest is either chosen for the given table or they are not) that chooses one table at a time, removes these guests from the matrix, reduces the size of the chromosome, and then chooses the next table.

meganstiles/Seating_Chart

If you don’t mind paying a bit , this other company Table Plan provides a software service to generate seating arrangement solutions that also uses Genetic Algorithms too.

Table Plan software - perfect table seating for weddings and events

Based on some online searching (here and here) it seems that it is quite domain specific but generally if the problem has more than one optimal solution (which is often the case) then Genetic Algorithms will find better solutions faster than Simulated Annealing Algorithms.

4.5 K-Means Clustering

(Edit- I came across this after I already published the first draft of this article but decided to include it anyway because it had a completely different framing of the problem that was interesting)

Data Science for Wedding Planning

Rather than framing this as an optimization / set partitioning type problem as with all the other approaches , the author of the article above had a novel take where he used the K-Means algorithm to identify the clusters of guests that should be seated together.

The basic idea is to describe each guest based on a number of binary characteristics (e.g. the author used things like same school y/n ? family y/n ? same clubs ? etc ) and then use the K-Means algorithm to cluster the most similar people together based on the number of tables that they want to planning for.

4.6 Other More Complex Formulations — What If Seating Order Matters ?!

One last example … all the solutions above assume that ‘ordering’ of the seats within a table are irrelevant. A table of A,B,C,D,E is the same as A , C, B, E, D (if you can imagine them sitting in a circle)

I haven’t found an example but I think it is actually possible to reformulate the problem to NOT ONLY look at which guests must sit apart/together but also incorporate a set of ‘second level’ constraints of whether they need to be seated side by side.

The math would likely need to make use of Stirling Numbers of the First Kind which is an interesting concept I stumbled across while researching this article . It’s basically a way to count the number of ways to arrange a number of elements around an ordered ‘circle’ like below.

Source : Wolfram Alpha

5. Conclusion

Image Source : Math/Confused Lady Meme (KnowYourMeme.com)

In conclusion — Hopefully by walking through all these different approaches, I’ve managed to demonstrate that there are many different ways to “translate” the problem into an algorithmic optimization scheme** depending on what it is that we are trying to solve for.

I also hope that I’ve provided you with some working code (and an Excel approach for any non-coders) that you can personally use to solve your seating arrangement problems and provided some starting resources if you want to delve deeper into the topic and build your own custom solutions.

Finally, I leave you with an ‘out of the box’ perspective... I showed a draft of this article to a friend and her reaction was — omg this is too complicated ! Isn’t an easier way to just set it up as a buffet and allow people to seat themselves wherever they like ? Don’t underestimate that most people tend to be very good at avoiding other people they don’t want to be around with and sticking to the people they want to be close with…

Till next time !

.

.

.

.

.

.

** If you enjoyed this article — Here are few extra things that you could do for extra credit*wink*wink* :

1. The examples above mostly all work by defining some sort of “happiness” score and then attempts to optimize the “overall” happiness across all tables. However this could lead to a situation where an individual table could have a low “happiness” scores that is masked because there are other tables with high scores. Therefore as a challenge you could try to modify the existing code for the Simulated Annealing example to instead use an alternative optimization objective that tries to ensure a fairer distribution of “happiness” across all tables (e.g estimated perhaps through a Gini Coefficient score ?)
2. On the What If Seating Order Around A Table Matters Too ? scenario : I couldn’t find anything online but if you know of a good example outlining the conceptual approach or actual working code that implements this, please leave a link in the comments…
3. For the hard core geeks who are on the cutting edge of things — you can explore Quantum Solvers — I recommend trying out Qiskit, IBM’s SDK that allows users to create their own quantum algorithms and run them either on quantum simulators or prototype quantum devices on IBM’s Quantum Experience. Qiskit is relatively easy to pick up as it runs on Python. I did a quick web search and found 2 examples for a 3SAT CNF and MILP Vehicle Routing Problem but it looks like nobody has yet to set up a solution for the Wedding Seating Problem specifically

A Walkthrough of Qiskit’s New Optimization Module