how to use OR to plan your wedding

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:

WeddingIPmodelDid you use OR to plan your wedding?

Related posts:

About these ads

8 responses to “how to use OR to plan your wedding

  • Thiago Serra

    Amazing! This post might be useful for me in a nearby future. If it works, I will share the results in my blog.

  • Greg

    Ha, my now-wife and I did this back in 1999. We should have written a paper!

  • Daniel Sandars

    No!. We agreed the top table in advance and let the remaining quests work out their own seating preferences.

  • Laura McLay

    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/

  • Unreal Chris Rump (@cmrump)

    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.

  • Brian Piper

    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.

  • Susan Martonosi

    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…).

  • Andreas Thorsen

    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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 2,129 other followers

%d bloggers like this: