A paper entitled “Finding an Optimal Seating Chart” in the Annals of Improbable Research [Link] by Meghan L. Bellows and J. D. Luc Peterson shows how to use integer programming to optimally seat guests at a wedding (HT Bobby McFly). Their model maximizes the total number of connections at the table, which indirectly maximizes the number of people that guests know at each table. To ensure that a few of the tables account for most of the connections, there is a “fairness” constraint that enforces of minimum number of connections for each guest based on who is seated at their table.
The connection matrix was critical for getting table assignments that could actually be used, and as a result, the connection matrix was not necessarily a matrix of zeros and ones. In order to not split up a guest and his/her date, the connection matrix for these two guests had a very large value (they used 50) instead of 1.
The authors of this paper are a married couple who apparently used this model (the paper acknowledgments are cute).
Here is the model:
Did you use OR to plan your wedding?
Related posts:
April 4th, 2013 at 10:54 am
Amazing! This post might be useful for me in a nearby future. If it works, I will share the results in my blog.
April 4th, 2013 at 11:00 am
Ha, my now-wife and I did this back in 1999. We should have written a paper!
April 4th, 2013 at 11:00 am
No!. We agreed the top table in advance and let the remaining quests work out their own seating preferences.
April 4th, 2013 at 11:11 am
From Vincent Knight via Google+
“On another note +Rhyd Lewis (a colleague at +Cardiff University) has a website that uses combinatorial optimisation to create a seating plan: http://www.weddingseatplanner.com/ “
April 4th, 2013 at 12:15 pm
I had a student do this for an OR project once. Kind of big for a modern wedding with lots of guests/tables. Perhaps a heuristic i-means clustering would be suitable. Constraints (4) add a nice twist. This is an example of optimal clustering (cf. Rao (1971) in JASA). Can strengthen constraints (5) (and (6) which are the same and thus superfluous) by separating the sum. Also, if minimizing disparity (rather than maximizing similarity here), then can flip these into a set of triangle inequalities: g_i^j + g_i^k – 1 <= p_i^{jk} for all i, j, k.
April 4th, 2013 at 3:32 pm
I actually threatened to do this! I may have been discouraged from actually carrying it out. My plan was quite similar, I was going to rate the amount of enjoyment a person would have sitting with another person (not necessarily symmetric either) in a matrix. Certain assignments would … negatively affect a guest’s enjoyment of dinner. Alas, I was finishing my thesis and had no time. It was probably for the best. We did table assignment by hand, in the end.
April 8th, 2013 at 7:43 pm
I did this for my January wedding! I also included affinity groups (like “Work friends”, “college friends”, etc.) and required that at least two parties (e.g. couples or families) from the same affinity group were seated at the same table. Unfortunately, my scoring input data didn’t capture enough nuances in people’s relationships, and I ended up finding a better solution by hand anyway (while I was waiting for the IP to solve…).
June 22nd, 2013 at 10:08 am
Tried to convince my fiancee to allow me to implement such a model, but no dice, and we have to finish the seating arrangement today. Instead, as I spend part of the day with a posterboard and post-it notes, I will be channeling George Dantzig and his solution technique for travelling salesperson problems at RAND in the 1950s.