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

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://kahypar.org/ / http://github.com/SebastianSchlag/kahypar 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.