Wedding Seat Optimization Using Simulated Annealing

This is very cool! One of my colleagues recently solved the same problem for his own wedding by modelling it as a hypergraph partitioning problem and solving it with KaHyPar (http://kahypar.org/ / http://github.com/SebastianSchlag/kahypar). Every guest is represented by a node and weighted hyperedges express relationships (a couple and their kids, extended family, friends, acquaintances, etc). The goal is to partition the hypergraph into (roughly) equal-sized parts (i.e., tables) while minimising the sum of weights of cut hyperedges ("λ-1 metric"). It's simple enough to model and took a few milliseconds to solve :) He ended up actually using the resulting assignment and was really happy with it.

I don't think he had any guests who could not be seated at the same table, so I'm not sure how that would be modelled. I don't think any of the hypergraph partitioning tools out there handle negative edges well.

We optimized via a two-person wedding in Vegas. Cost including hotel stay: $240 in 1992 dollars. Value of not dealing with needy relatives, weird in-laws, massive debt, and who sat where: Priceless.

Damn, I just learned about linear programming in a class and about MCMCs in another; this is why I love reading HN: there's so much more CS to learn!

Is there a way to look at the Python Notebook on mobile? All I see is the source code, which isn't very mobile-friendly.

Nice application of simulated annealing, thanks for sharing!