Seating wedding guests with constraints: a small optimiser in a Web Worker

Seating wedding guests sounds like a spreadsheet job until you write down the rules. The Smiths sit together. Uncle Bob and Aunt Carol must not share a table. The grandparents stay at table 1. Every table should be about as full as the others. Each rule is easy alone; together they pull against each other.

I recently built a browser seating chart planner, and the part that took longest was the optimiser behind its "Seat everyone" button. Here is how it works.

One cost for everything

The input is guests with a household (a free-text group column), tables with a capacity, pair rules ("together" or "apart"), and pinned guests who stay where the user put them. The optimiser turns this into indices and typed arrays, and rules into weighted edges between two guests.

Instead of a separate feasibility check, everything becomes one number to minimise. Hard rules get a weight that outweighs all the soft terms together:

export const DEFAULT_WEIGHTS: Weights = {
  hard: 10_000,      // per broken "together" / "apart" rule
  together: 100,     // per "together" rule, when it is set as a soft wish
  groupSplit: 100,   // per table a household uses beyond the fewest that could hold it
  groupSpread: 10,   // per table-number gap between the pieces of a split household
  balance: 4,        // per squared guest away from a table's fair share
  // ...plus tag, relation and table-preference terms
};

The balance term deserves a note. Each table's fair share is capacity × seatable guests / total seats, and the cost is the squared distance from it. That spreads guests over every table instead of leaving one nearly empty.

Scoring a move by its delta

A local search tries tens of thousands of moves, so rescoring the whole plan each time would be slow. The fix is to make every cost term belong to exactly one table, group, tag or rule. A move then only touches a few terms: sum them, apply the move, sum them again.

/** Moves guests[i] to targets[i] and returns the change in total cost. Undo by moving them back. */
export function moveGuests(p: Problem, s: State, guests: readonly number[], targets: readonly number[]): number {
  const from = guests.map((guest) => s.tableOf[guest]);
  const before = localCost(p, s, guests, targets);
  guests.forEach((guest, index) => seat(p, s, guest, targets[index]));
  return localCost(p, s, guests, from) - before;
}

localCost uses an epoch counter so each table, group and rule is visited once per call, even when two moved guests share it.

The search, in four steps

1. Pins first. Pinned guests are seated and never moved.
2. Greedy start. A household plus everyone tied to it by "together" rules is a block. Blocks go largest first, each to the table where it adds the least cost. A block that can't go in whole without breaking a hard rule is placed guest by guest.
3. Repair if needed. If everyone has a seat but a hard rule is still broken, the hard part is treated as graph colouring: tables are colours with a capacity, "apart" pairs are edges. DSATUR builds a colouring, then a tabu search works on the remaining conflicts. Its result is used only if it breaks fewer hard rules.
4. Simulated annealing on the full cost.

Each annealing step proposes one of four moves: one guest to another table, a whole block piece, a guest to the table of a household member seated elsewhere, or a swap of everyone movable at two tables.

function propose(ctx: Context, fixed: Uint8Array): Move | null {
  const { p, s, random, movable } = ctx;
  const guest = movable[randomIndex(random, movable.length)];
  const roll = random();
  const table = randomIndex(random, p.tableCount);
  if (roll < 0.35) return shiftOrSwap(ctx, [guest], table, fixed, false);
  if (roll < 0.67) return shiftOrSwap(ctx, blockPiece(ctx, guest, fixed), table, fixed, true);
  if (roll < 0.95) return proposeJoin(ctx, guest, fixed);
  return proposeExchange(ctx, s.tableOf[guest], table, fixed);
}

If the target table is full, a shift becomes a swap. Acceptance is the textbook rule: keep a better move, keep a worse one with probability exp(-delta / temperature). The temperature cools geometrically from 30 to 0.3, so early steps can break a household apart to make room and late steps only polish. The best seating seen is restored at the end.

Random numbers come from a seeded generator (mulberry32), so the same input and seed give the same seating unless the time budget cuts the run short. The run stops at a 250 ms budget by default, or early once the cost reaches the balance floor, the lowest balance cost any whole-number seating can have.

Exact solving for small plans

For up to 60 guests there's a second stage. The same cost is written as a mixed-integer linear program and solved by HiGHS compiled to WebAssembly, in the browser. The annealing result is the starting solution, so the solver only has to improve it or prove it optimal within 1.5 seconds.

Unless the solver fails, it ends with a proof that nothing costs less, or a proven lower bound. Larger plans get a cheap combinatorial bound instead, where a big gap means "not proven", not "far from optimal".

Keeping it off the main thread

A solve of over a second would freeze the page, so the optimiser runs in a module Web Worker. Cancelling is the simplest thing possible: terminate the worker, and start a fresh one next time.

return {
  outcome,
  cancel: () => {
    discardWorker(); // worker.terminate(); worker = null
    finish({ status: 'cancelled' });
  },
};

Each request carries an id and replies with another id are ignored, so a late answer can't overwrite a newer run.

The planner runs it twice. A quick run with the exact solver off is shown immediately. Then, for small plans, a full run goes in the background, and its result replaces the quick one only if it is strictly cheaper and the user hasn't changed anything meanwhile.

When the rules can't all be met

"Something went wrong" is the worst answer here, so the optimiser looks for causes that hold for every possible seating:

• an "apart" pair that a chain of "together" rules ties to one table. A breadth-first search finds the chain so the message can name it.
• a "together" group larger than the largest table.
• more guests who must all sit at different tables than there are tables.
• an odd ring of "apart" rules with only two tables: three guests who each must avoid the other two can't fit on two tables.
• two pinned guests who contradict a rule.

Anything still broken that none of these explain is reported as unresolved, with both names. If there simply aren't enough seats, the planner adds tables first and says how many.

Summary

• Put hard rules and soft goals in one cost, with the hard weight above all soft terms combined.
• Make every term belong to one table, group or rule, and score moves by their delta.
• Greedy start, colouring repair for hard rules, then seeded simulated annealing.
• For small plans, an exact MILP solver in WebAssembly can prove the result optimal.
• Run it in a Web Worker, cancel by terminating, match replies by id.
• When the rules can't be met, explain why, by name.

If you're planning a wedding or any event with tables, the planner is free at seating-chart-generator.com, and the guest list never leaves your browser.