simulated annealing will save my wedding

My friend Ross has installed in my head the pernicious idea of writing a program to do seating arrangements for our wedding. I ran my idea for an implementation by my advisor, and we now have a framework: Generate a cost matrix for dyads of guests and run simulated annealing on a random partition, with a move being a random switch of guests; terminate when you reach a position in which your assignment doesn’t improve. The problem is generating the cost matrix for ~100 guests (that’s ~10,000 cells). I think it would be fairly sparse, and a lot of the cost assignment would be easy: Assign a huge positive cost to dyads characterized by white-hot hate, a huge negative cost to dyads who signed up to be in pairs, and a moderate negative cost to dyads from the same “source” (Webers, Sheehans, Lins, Wus, PDS, Uni, Amherst, Yale, Princeton). You could also go through and assign moderate negative costs to pairs of people who share interests or affinities, or who know each other independently — e.g. my friends Nick (Amherst) and Dave (PDS), both Google employees; or either of them with Greg (Princeton), who’s interested in Googular things; or Shin-Yi’s mom and other Chinese-speaking couples, although possibly not my sister-in-law’s parents, who are for Obama. You could even add table-wise costs to the final calculation: You could stipulate, for example, that a table’s constitution is optimal if half its population is from one source and half from another, so you’re at the sweet spot between comfort and novelty.

This scheme wouldn’t quite capture all the right aspects of the “data” — my friend Meeta, for example, would necessitate a number of by-hand cost assignments since she doesn’t share a convenient institutional affiliation with the guests she’s closest to, and although we all like each other, it’s obvious that the omnibus “Amherst” affinity doesn’t capture the varying strengths of relationships among my friends from Amherst. So curation of the cost matrix could potentially get quite laborious. However, the chief utility of a program like this might not be to arrive at the optimal seating arrangement, but rather to quickly generate seating arrangements that don’t suck and could easily be optimized by hand.

Still, the idea of using machine learning to solve a real problem is pretty interesting. Maybe I could make it Web 2.0 and get my fuck-you money. Mmm… fuck-you money.

Advertisements

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