Facility location: what guarantee may a planner promise?¶
A retailer choosing warehouse sites will sooner or later be asked "how close to the best possible plan is ours?", and someone will want to answer with a worst-case guarantee such as "always within 1.5 times optimal". This page shows the answer the library gives: no polynomial-time planner can honestly promise a worst-case factor better than about 1.736, no known planner even reaches that, and the useful number is the gap you can measure on your own instances. It is written for a logistics or network-planning lead and the engineers behind the planning service.
At a glance
| Question | Which k warehouse sites should we open, and what can we say about how good the plan is? |
| Owner | Network planning; the planning service quotes the answer. |
| Today's habit | Run a heuristic, quote its cost, and keep looking for an algorithm with a better worst-case promise. |
| What this adds | A stated floor on what anyone may promise (from the router), and a recipe to measure your own plan's gap instance by instance. |
| Demo outcome | Greedy plan costs 5,096 pallet-km per week; the best plan costs 4,145; greedy is 1.229 times optimal on this instance. |
| Kind of example | A helper, not a decision: there is no act/abstain verdict. |
| Example id | facility_location (uv run grounded-decision examples facility_location) |
The question today¶
A retailer picks k warehouse sites from a list of candidates. Each store
is served by its nearest open warehouse, and the cost to minimise is weekly
pallets times distance, summed over stores. This is the metric k-median
problem. For realistic sizes no method finds the guaranteed best plan
quickly, so every planner runs a heuristic or an approximation algorithm.
Where today's habit goes wrong¶
Two things go wrong in practice:
- A heuristic's cost is quoted with no reference point. "The plan costs 5,096 pallet-km" says nothing about whether 4,000 was possible.
- Teams promise, or chase, worst-case guarantees that cannot exist. A promise like "always within 1.5 times optimal" is below a proven hardness floor, so no fast planner can keep it on every input.
What the library will and will not claim¶
The router (dispatch with the k_median subgoal) returns a fixed
statement rather than solving anything: do not claim a worst-case factor
below 1.7358.
| The library claims | The library does not claim |
|---|---|
| No polynomial-time algorithm can guarantee a factor better than \(1 + 2/e \approx 1.736\) on every instance, under standard complexity assumptions. | That any algorithm achieves 1.736. None is known; the best published worst-case guarantees are above 2. |
| On a given instance you can measure your plan against a lower bound and report that gap. | That greedy, or the heuristic you run, has any worst-case factor at all. The demo's greedy has none. |
1.736 is a floor on promises, not a promise
The router's result carries factor_claimed = 1.7358… and the
envelope label ugc_opt. Read both as "the smallest factor anyone
may claim", not as a guarantee this library or your planner
delivers. Do not put 1.7358 in an API response or contract as your
planner's worst-case ratio. The result is a hardness result that
rests on P ≠ NP-type assumptions, not on the Unique Games
Conjecture.
- In the wider literature: the \(1 + 2/e\) hardness bound for metric k-median is due to Jain, Mahdian and Saberi (2002). Whether some polynomial-time algorithm can match it is open.
- In this project's math catalog: result 125, "Metric k-median threshold 1+2/e", recorded from the literature (published, not machine-checked). See Approximation limits.
Data you provide¶
| Input | Source | Refresh | Owner | Quality bar |
|---|---|---|---|---|
| Candidate sites with coordinates (or a road-distance matrix) | Real-estate / network planning | Per planning cycle | Network planning | Distances must obey the triangle inequality (road distances do). |
| Stores with locations and weekly demand (pallets) | Demand forecast | Per planning cycle | Supply-chain analytics | Forecast error usually moves cost more than the choice of algorithm. |
k, the number of sites the budget allows |
Finance | Per cycle | Planning lead | — |
Worked example¶
From uv run grounded-decision examples facility_location: five candidate
sites, seven stores, open two.
| Item | Value |
|---|---|
| Router answer | ok=True, "do not claim worst-case factor below 1.7358 (catalog 125)" |
| Greedy plan (open the site that cuts cost most, twice) | river_port, south_park: 5,096 pallet-km per week |
| Best plan (every pair tried; possible only because the instance is tiny) | north_depot, south_park: 4,145 pallet-km per week |
| Measured gap on this instance | greedy / best = 1.229 |
| Today's habit | quote 5,096 with no reference, keep hunting for a better worst-case ratio |
Greedy opened the central river_port first, which looks good with one
site and is wrong with two. The 23 % gap is an instance fact, not a
worst-case statement.
Measuring the gap on instances too large to brute-force
On real instances you cannot try every combination. Instead solve the linear-programming relaxation of k-median (let each site be "partly open" between 0 and 1, with at most \(k\) in total, and each store's demand split across open sites). Its optimum is a lower bound on the best real plan, so \(\text{gap} \le \text{your cost} / \text{LP bound}\).
On the demo instance, the LP relaxation solved with SciPy's
linprog (not a dependency of this library; we ran it with
uv run --with scipy python on the example's CANDIDATE_SITES and
STORES) gives a bound of 4,144.9: equal to the brute-force best
plan, so the reported gap of 1.229 is exact here. On larger
instances the LP bound is usually a little below the true best, and
the gap you report is then an upper bound on the real gap.
What your service does with the result¶
- Do not advertise a worst-case factor below 1.7358, and do not advertise 1.7358 either unless you run an algorithm that provably achieves it (none is known).
- For each plan, report the measured gap against the LP lower bound (or the best plan found so far) next to the cost.
- Track that gap over planning cycles. Put engineering effort where the gap is large, and into demand forecasts and capacity data, which usually matter more.
Tuning and monitoring¶
Nothing in the router is tunable. Watch the measured gap per instance: a gap that grows when the network grows is a reason to try a better heuristic or a local-search improvement step on top of greedy.
Limits and risks¶
- Toy instance. Seven stores and five sites; real networks have thousands of stores and side constraints (capacities, service-level radii) that plain k-median ignores.
- Straight-line distances in the demo; use road distances or travel times.
- The router does not solve the problem. It returns a statement about guarantees; the planning itself is your code.
Wiring it in¶
from grounded_decision.router import Subgoal, dispatch
from grounded_decision.types import Envelope
result = dispatch(Subgoal("k_median", Envelope.UGC_OPT, {}))
# result.ok is True; result.detail is the text to show in planner docs:
# "do not claim worst-case factor below 1.7358 (catalog 125)"
Then compute each plan's cost and its LP lower bound in your planning job,
and store both. greedy_plan, exact_plan and serving_cost in
src/grounded_decision/examples/facility_location.py show the cost
calculation. More on the router: Use the hardness router.
Run it yourself¶
uv run grounded-decision examples facility_location
uv run grounded-decision examples facility_location --json
The report has two "ticks": the router's answer and the instance measurement. How to read it: Example library: reading a report.
Further reading¶
- Approximation limits (Unique Games): the approximation results the router records, and which of them depend on the Unique Games Conjecture (this one does not).
- Questions the library refuses.
- Trust levels and honest limits.