Separation-Constrained Layout
Fit the most people into a room under a minimum-separation rule — maximum independent set on a conflict graph, solved to proven optimality right here in your browser, on a floor plan you can rearrange.
Understand exactly what you're looking at
The theory, how the data is acquired and cleaned, how to read the result — and what BIS would do for you next.
The question is not “is this room safe” but “how many can I seat” — and only the second one is answerable. Given a floor plan, a seat grid and a separation rule, what is the largest set of seats you can fill?
Mark every pair of seats closer than the rule allows, and the answer is the largest set of seats containing no marked pair. That is maximum independent set on the conflict graph — NP-hard in general, but a room is small, so it is solved to proven optimality rather than approximately. Every capacity number on this page is exact.
There is no external dataset — the room is the input. The floor plan, the seat dimensions and the per-aisle widths you set with the sliders fully determine the geometry, and the conflict graph is derived from that geometry: an edge for every pair of seats whose centre-to-centre distance falls under the current rule.
Nothing is fetched and nothing is sampled. Move a slider and the instance is rebuilt and re-solved from scratch.
The model this is ported from is from 2020, and shipping it honestly meant fixing three things:
- Room width was a dead input. The original built seat positions from seat width and the aisle list alone and never checked them against the room — its own example put six of forty-two seats outside the wall. We exclude those and say so on screen.
- Row pitch divided by the wrong number. m rows leave m−1 gaps between them; the original divided by m, so the rows never reached the back wall.
- Every conflict constraint was added twice, once per ordered pair — harmless to the optimum but it doubled the model and made the reported size misleading.
Capacity does not decline smoothly as you tighten the rule — it sits flat, falls off a cliff, then sits flat again. Going from the WHO’s 1 m to the CDC’s 2 m does not halve this room, it quarters it. The thresholds are not in the rule; they are in the furniture, which is why there is one slider per aisle rather than a single spacing control.
The solver strip under the plan shows the real model: binary variables, conflict constraints, branch-and-bound nodes and wall clock. When the node count equals the seat count, the bound proved optimality without ever branching — an easy instance, not just a fast solver, and the difference is worth knowing.
This is a facility-layout problem, and the pandemic is its origin story rather than its subject: the same model covers call-centre desks, exam halls, restaurant floors — anywhere a separation or spacing rule meets a fixed plan.
BIS builds the exact version against your floor plan and yourconstraints, and puts the capacity numbers where your planners can trust them — proven optima, not estimates, with the thresholds made visible before they cost you a room.
This preview runs on real public data. Yours would run on your data.
We start with a conversation, prove the value on a focused POC with your real data, then ship it — in our environment or deployed into yours.