~6 s
Exact minimum rooms for a full 10,000,000-booking year, with an oversold certificate.
Hotel room allocation & oversold revenue
RoomBalance answers the three hard questions in room allocation exactly: the fewest rooms that cover your booking calendar, how to match every booking to a room type under your upgrade rules, and — when you're oversold — which bookings to accept to keep the most revenue. Every answer is provably optimal and carries a certificate you can check.
What it does
RoomBalance is an allocation engine you call over a one-line protocol. It covers the three room problems a property actually faces — and for each, it returns the provably optimal answer together with a certificate you can check.
Given every booking as an arrival–departure interval, find the fewest rooms that serve them all — one physical room reused across non-overlapping stays — and how far a fixed inventory is oversold.
O(N log N).Bookings group into request classes by which room types can serve them — a suite can satisfy a deluxe request. RoomMatch tells you whether everyone fits one room each under your upgrade rules, and exactly where you're short.
When demand exceeds your rooms, decide which bookings to accept so the accepted stays still fit and total revenue is as high as possible — the choice a greedy gets wrong.
The certificate
Every answer carries its own proof. RoomBalance cannot overclaim — when a fixed inventory can't cover the calendar it reports exactly how oversold you are, and it never reports a revenue figure it can't prove is the maximum.
| capability | certificate field | what it proves |
|---|---|---|
| StayOptimal | rooms_used = peak_overlap | the fewest rooms that can cover the calendar — the interval-coloring optimum, plus oversold_by against your inventory |
| RoomMatch | exact=1, min_per_room | every booking housed one-per-room under the upgrade rules, or exactly where you fall short |
| OccupancyMax | total_value ≤ offered_value | the maximum revenue any accept/reject split can reach on your rooms — not a greedy's guess |
Each figure is computed by the engine and returned in the same line as the answer — check it without re-solving.
Measured, reproducible
Wall-clock milliseconds, single-threaded, every figure reproducible from source. Below are the engine's own scale timings, the revenue an oversold property recovers over the greedy a property-management system ships, and head-to-head races against OR-Tools CP-SAT and CBC on byte-identical instances.
| bookings | solve_ms | rooms (= peak overlap) |
|---|---|---|
| 10,000 | 3.07 | 238 |
| 100,000 | 34.9 | 2,202 |
| 1,000,000 | 378 | 20,921 |
| 5,000,000 | 2,159 | 103,544 |
| 10,000,000 | 5,884 | 206,491 |
A full year of a ten-million-booking chain, exact minimum rooms, in about six seconds.
Interval coloring is polynomial — StayOptimal is the optimal algorithm,
not a heuristic that beats a weaker one. The win over an in-house naive
O(N²) sweep is scale (it stops finishing around 50k); the sell is the
exactness, the certificate, and the range.
| bookings | RoomBalance ms (1 core) | CP-SAT ms (8 cores) | speedup | rooms (both) |
|---|---|---|---|---|
| 1,000 | 0.26 | 13.5 | 52× | 34 |
| 5,000 | 1.45 | 33.4 | 23× | 133 |
| 20,000 | 6.70 | 99.6 | 15× | 462 |
| 50,000 | 17.6 | 238 | 14× | 1,112 |
| 100,000 | 36.9 | 491 | 13× | 2,202 |
| 500,000 | 186 | 2,541 | 14× | 10,509 |
Minimum interval coloring is polynomial, and CP-SAT's cumulative propagator solves it exactly — it does not blow up here. So this is not "the competitor can't do it": it is a steady 13–52× while single-threaded against CP-SAT's eight cores, agreeing on the minimum every time, then carrying on to 10M bookings where standing up the CP model is itself the problem. The sell is speed, the exact minimum plus oversold certificate, and zero dependencies — not that we alone are exact.
The heuristic a property-management system actually runs: sort bookings by value density, first-fit into any free room. Fast, and it quietly discards revenue. Heavily oversold inventory, identical instances:
| bookings | rooms | RoomBalance value | greedy value | greedy captures |
|---|---|---|---|---|
| 1,000 | 20 | 479,498 | 187,191 | 39.0% |
| 5,000 | 50 | 1,945,937 | 847,440 | 43.6% |
| 20,000 | 100 | 5,506,485 | 2,499,407 | 45.4% |
| 50,000 | 200 | 12,313,456 | 6,534,605 | 53.1% |
| 100,000 | 300 | 21,118,291 | 12,355,620 | 58.5% |
On heavily oversold inventory the shipped greedy captures only 39–59% of the attainable revenue; OccupancyMax returns the provable maximum every time. That gap is the sell — not speed (the greedy is faster and worse), but the revenue it silently discards.
| bookings | rooms | solve_ms |
|---|---|---|
| 1,000 | 20 | 1.4 |
| 5,000 | 50 | 10.4 |
| 20,000 | 100 | 60 |
| 50,000 | 200 | 477 |
| 100,000 | 300 | 999 |
100,000 oversold requests, exact max-revenue selection against 300 rooms, in about one second. OccupancyMax is a flow — heavier than StayOptimal's coloring — but it returns the guaranteed revenue optimum every time.
| bookings | rooms | value (all agree) | RoomBalance ms | CP-SAT ms | CBC ms | vs CP-SAT | vs CBC |
|---|---|---|---|---|---|---|---|
| 100 | 5 | 50,794 | 0.10 | 8.6 | — | 86× | — |
| 250 | 8 | 123,875 | 0.31 | 12.7 | — | 40× | — |
| 500 | 12 | 248,105 | 0.74 | 30.2 | — | 41× | — |
| 1,000 | 20 | 479,498 | 1.83 | 112 | 52.7 | 61× | 29× |
| 2,000 | 30 | 919,606 | 4.35 | 417 | — | 96× | — |
| 5,000 | 50 | 1,945,937 | 14.3 | 2,193 | 580 | 153× | 41× |
| 20,000 | 100 | 5,506,485 | 84.7 | 28,405 | 2,889 | 336× | 34× |
| 50,000 | 200 | 12,313,456 | 442 | DNF | 7,577 | ∞ | 17× |
| 100,000 | 300 | 21,118,291 | 1,594 | DNF | 14,466 | ∞ | 9× |
This selection problem is polynomial (its clique matrix is totally unimodular), so an LP-based solver like CBC also reaches the exact optimum at every scale — we are not the only tool that can solve it, and we do not claim CBC can't. What is measured: CP-SAT is the wrong tool here — its search stops proving anything past ~20k (DNF = only the trivial value-0 answer after the time limit) and we are 40–336× faster where it finishes; CBC does scale, but we are still 9–41× faster end-to-end in a dependency-free binary. The margin over CBC narrows with size (29× → 9×) as our own flow cost grows — we state that rather than hide it. Every value CP-SAT and CBC did prove is bit-identical to ours: independent confirmation the engine is exact.
| bookings | quotient_ms | min per room | matchable |
|---|---|---|---|
| 10,000 | 0.0034 | 1 | yes |
| 100,000 | 0.0012 | 1 | yes |
| 1,000,000 | 0.0008 | 1 | yes |
| 10,000,000 | 0.0009 | 1 | yes |
| 100,000,000 | 0.0008 | 1 | yes |
100 million bookings matched to room types in under a microsecond — the engine flows the 4 types × 4 classes quotient and never materializes the bookings.
| requests → types | RoomBalance ms | CP-SAT | makespan (ours / CP-SAT) | speedup |
|---|---|---|---|---|
| 1,000 → 100 | 0.36 | 327 ms | 10 / 10 | 908× |
| 10,000 → 1,000 | 5.57 | 54,891 ms | 10 / 10 | ~9,850× |
| 100,000 → 10,000 | 339 | timeout (150 s) | 10 / 11 | exact where it times out |
| 1,000,000 → 100,000 | 11,032 | does not scale | 16 / — | — |
This is the one place to lean hard. RoomMatch is polynomial via the transportation quotient; CP-SAT is search over an NP formulation, and it falls off a cliff. It is already 908× behind at a thousand requests and ~9,850× at ten thousand — same exact makespan. At a hundred thousand CP-SAT times out after 150 s and returns a worse answer (a busiest-type load of 11 versus our provable minimum of 10); at a million requests ours still returns the exact optimum (16) in about eleven seconds, while standing up a million-request CP model is not viable at all.
Measured on an 11th-Gen Intel Core i5-1135G7 @ 2.40 GHz, 32 GB, Debian 13, gcc -O2, our
engine single-threaded, on a shared box under moderate load (≈ 1.6 for the scale runs,
drifting to ~3.6 during the head-to-head races) — absolute ms run high vs a quiet box, so
the ratios are order-of-magnitude, not lab-grade, and each is a single run per instance.
Competitor times (CP-SAT, CBC) are each solver's own end-to-end wall — model build plus
solve — with all 8 cores. Correctness: StayOptimal cross-checked on 2,000 random instances
against an O(n²) oracle; OccupancyMax on 3,000 random instances against a
2ⁿ brute-force oracle — both exact on every instance, and CP-SAT and CBC
independently confirm OccupancyMax's value is exact up to 100,000 bookings.
objdump confirms zero floating-point instructions; the engine links no libm.
Live engine
These call the real engine over the local gateway — one request line in, one result line
out. Demo sizes are kept small so every call is instant; the million-booking figures above
are measured results served as data, not run live here. Start the engine with
site_hotel/serve.sh, then open this page through the gateway.
Give each booking as arrival:depart (night intervals). Returns the
provable minimum rooms — the peak concurrent stays — and, against a fixed inventory,
exactly how oversold you are and on which day.
types = rooms per room-type (indexed 0…). requests =
bookings per request-class (indexed 0…). eligibility =
class:type pairs saying which types can serve each class (upgrade rules).
Returns whether everyone fits one room each, and the load per type.
You have more bookings than rooms. Give each stay as arrival:depart, an
inventory of rooms, and optional per-booking values (revenue;
defaults to nights). Returns the provable maximum-revenue subset that still fits, and
the revenue offered vs kept.
Integration
The browser never sends a raw command line — it posts validated JSON and the gateway builds
the engine line itself, so no command injection is possible. Legacy /api/<name>
aliases remain for compatibility.
Advisory · Tier-2
The allocation core above returns certificates. This is a different layer: it estimates
the numbers that core takes as inputs — a no-show rate, an overbooking level, a demand forecast —
from your own history. Every reply carries "advisory": 1,
"uncertified": 1 and an interval; none of them ever returns a certificate, and none
is ever mixed into a /v1/hotel|rooms|occupancy answer. A recommended overbooking
C re-enters the certified core only as an explicit input (inv = R + C).
These call the same daemon, but they estimate — every reply is
advisory=1 uncertified=1, carries an interval where one applies, and never a
certificate. Nothing here is mixed into a certified /v1/hotel|rooms|occupancy
answer; a recommended value re-enters the core only if you pass it as a plain input.
Measured — backtested on real history (Antonio, 119,390 bookings)
From your own arrivals and no-shows, a posterior mean shrunk toward a prior, plus a 90% interval. Estimate, not a certificate — the raw empirical rate is shown alongside.
The level C that maximizes expected net revenue given a no-show rate, a
room value and a walk cost. It returns C as a suggestion; you choose whether
to call /v1/occupancy with inv = R + C. It is never auto-applied.
With otb bookings on the books and an expected remaining pickup,
the final = on-the-books + remaining, with an interval from the residual scale sd.
An estimate that informs the room count R — never a certificate.
Split your no-show history into an older and a recent window. The geodesic distance between the two rates is compared to a 1/√N sampling-noise floor: drift means weight the recent window; otherwise pool all history. A read, not a certificate.
Decision — optimizer exact given a supplied curve; no measured revenue lift
Give parallel lists of candidate prices and the demand you expect at each, plus rooms. It returns the exact revenue-max price capped at capacity. The optimizer is exact given the curve you supply; the elasticity itself is not measured here, so there is no revenue-lift claim.
From per-night bid prices and a nightly rate, the shortest length of stay whose rate clears the sum of the first L bids — else close-to-arrival. A proposed restriction, not a certificate.
A take/pass read: a group's revenue against the transient revenue it would displace,
with exact min() accounting over a per-night transient forecast. A
recommendation, not a certificate.
Cold-start seeds come from a public dataset for a brand-new property with no history; the moment
you supply your own bookings they take over. A public-data average is never presented as a
prediction about your guests. Every advisory number is measured before it ships — see the
backtest in the repo (tier2/TIER2_BACKTEST.md).
Why it matters
The peak concurrent stays is the room count you must have. StayOptimal makes it provably minimal and tells you exactly how far a fixed inventory is oversold — a number you can hand to operations before you promise a room you don't have.
When you're oversold, which bookings you accept decides the night's revenue. On heavily oversold instances a shipped greedy captured only 39–59% of the attainable revenue; OccupancyMax keeps the provable maximum, and shows you the gap.
RoomMatch checks that every booking can be housed one room each under your upgrade ladder — and its cost tracks the number of room types and request classes, not the number of bookings, so a hundred million reservations cost the same as ten thousand.
"Fewest rooms to cover the calendar," "everyone housed under the upgrade rules," "the maximum revenue this inventory can earn tonight" — each is a certificate a heuristic cannot give and RoomBalance can.
Trustworthy in production
Every property below is verified against the shipped binary — for the operator who has to put this in the path of a real booking system.
ldd shows libc only — no libm, nothing transitive to vendor, audit, or patch.
Opens an AF_UNIX socket at 0600 only — no network syscalls anywhere, and it writes no files. It cannot phone home.
Integer decision logic, zero floating point anywhere (objdump-verified). Same input, same output, on every box — cacheable and sign-off-able.
Pure C, no garbage collector, no JIT, no interpreter. No p99 spike from a GC pause or a cold import.
RoomMatch never materializes the bookings — it flows the room-type quotient — so matching cost is independent of reservation volume.
Every response carries its own certificate — minimum rooms, oversold amount, or provable-maximum revenue. Trust the result without re-solving it.
No session, no auth handshake, no schema. printf … | nc -U from any language.
StayOptimal on 2,000 random calendars vs an O(n²) oracle; OccupancyMax on 3,000 random instances vs a 2ⁿ brute-force oracle — exact on every one.
Honest scope
Overclaiming here loses the operator, so we state it plainly. RoomBalance is exact allocation given your bookings and your rates. It is not a yield or pricing system, and it does not pretend to be.
uncertified, carries an interval, and never shares a response with a certificate.inv = R + C input — stays your call.vs alternatives
Run a pilot
Export a week of bookings — arrivals, departures, room types, rates. We'll show you the exact minimum rooms, whether everyone fits under your upgrade rules, and — if you were oversold — the revenue a greedy left on the table. No accounts, no checkout: a conversation and a measurement.
Start a pilot conversationNous Research Centre · erick.llamas@gmail.com