>Isn't "Keep people either together or apart" an NP-Hard problem,

Yes.

>and basically unsolvable for more than a couple preferences?

Our PerfectTablePlan table planner can optimize seating for thousands of guests with thousands of preference constraints (between individuals and groups) on a standard desktop PC/Mac. It uses a genetic algorithm to quickly produce a 'good enough' (but not guaranteed to be optimal) solution. For seating plans it isn't really clear what the optimum is anyway. It is more important that than Bob sits next to Jill or not next to Jack or not next to an empty seats? Debatable.