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:
- finding optimal marriage pairings using the assignment problem
- a roundup of operations research models for finding love