Skip to content

From LP fractions to real pharmacies

Jip Claassens edited this page Sep 15, 2026 · 1 revision

From LP fractions to real pharmacies

In one sentence: the LP says a candidate cell is "half open"; this page explains how each λ point is turned into exactly p real pharmacies (fixed count, seeds, swap polish, honest scoring) and what the LP-versus-rounded gap does and does not certify.

Where this sits: GeoDMS → Arrow → Julia LP → sweep → rounding → scenarios → deck. Upstream: The facility location model explained, The lambda sweep and the Pareto frontier; downstream: Scenarios S1 S2 S3 pins S2 on the rounded points. The compact statement is §3 of Lambda sweep method and issue #47.

Why a rounding step exists

At each price λ per location the sweep solves an LP relaxation (Glossary): an openness y*_j in [0, 1] per candidate cell and a fractional assignment of each client's residents. A cell that is "0.5 open" cannot be built, so each LP point is followed by a rounding: pick whole cells to open, route every client to its nearest open cell, and price that concrete network.

Why a heuristic rather than an exact integer solve is not recorded (likely: cost and simplicity). The relaxation is nearly integral — frac_y, the number of fractional cells, is a handful to a few hundred at the scenario points — so an exact fixed-count MIP for S1/S2 is on the roadmap (doc/todo.md item 5). The rounding is a certified upper bound, not the last word.

Three roundings — top-p, greedy, multistart — are computed and logged at every rounded point; ROUNDING (default multistart) picks the one selected for the arrows, the S2 bisection and the deck. Top-p and greedy are multistart's own seeds, so logging them costs nothing, and their stranded counts are the diagnostic that exposed top-p's rural failure (e1c426b, June 2026). Issue #47 and the deck write x_j for what the code calls y (the notation table is on The facility location model explained).

A toy problem to follow along

LINEAR cost, c(t) = t minutes, soft coverage — the LP may leave a client unserved at BIG per resident (The facility location model explained). A stranded resident — no open pharmacy in the client cell's choice set, its OD rows (Glossary) — costs BIG = c(120) = 120. Four candidate cells A–D, four client cells:

client residents choice set (cell: minutes)
0 100 A: 5
1 12 A: 60, B: 10, C: 12
2 10 A: 60, C: 10, D: 12
3 8 A: 60, D: 10, B: 12

No pair of whole cells serves clients 1–3 closely, so the LP hedges: at λ = 300 it returns y* = (A 1.0, B 0.5, C 0.5, D 0.5); client 0 goes to A, clients 1–3 split half/half between their two near cells. So sum_y (= Σy*) is 2.5, frac_y = 3, LP travel 100·5 + 30·11 = 830, total cost 830 + 300·2.5 = 1 580.

Step 1 — fix the count: p = round(Σ y*)

The rounding never chooses how many pharmacies to open: p_open = clamp(round(Int, sum_y), 1, M) (solve_at_w!, around line 531) — Σy* to the nearest whole number, between 1 and M, the number of candidate cells. The recorded reason (issue #47, lp_run.jl header, since 51157a0 of 26 May 2026): the rounded point must stay "an apples-to-apples point on the same Pareto curve" — same count axis as the LP point, so S1 (the frontier point at today's count, Scenarios S1 S2 S3), bisected on sum_y, lands on the same n_open.

Julia's round is half to even: 2.5 → 2. Toy: p = 2, although the true integer optimum at λ = 300 opens three cells ({A, B, C}: travel 816, total 1 716).

Step 2 — must-open cells and the fractional pool

Cells with y* ≥ 1 − 10⁻⁶ are must-open: every rounding keeps them (issue #47, "held fixed"). Cells with 10⁻⁶ < y* < 1 − 10⁻⁶ form the fractional pool; the rounding must pick k = p − #must-open of them. Cells with y* ≈ 0 are never opened — swaps only trade inside the pool, which cannot run out because p ≤ #must-open + #pool (not motivated anywhere; likely cost, each swap being a pass over the OD rows). Toy: must-open {A}, pool {B, C, D}, k = 1.

Step 3 — the seeds

Multistart polishes MS_RESTARTS = 10 starting sets — seeds, distinct from MS_SEED, the constant that fixes the random stream — and keeps the best. Two are deterministic, eight random.

Seed 1 — top-p

Sort all candidates by y* descending and take the first p. Toy: A, then B, C, D tie at 0.5; the sort is stable (lowest id first), so B wins → {A, B}, travel 500 + 120 + 600 + 96 = 1 316, nobody stranded.

Top-p is blind to geography: where the LP spreads one pharmacy's worth of demand over many low-y* cells in a rural valley, none clears the cut-off and the valley is stranded. e1c426b (7 June 2026) found that top-p "abandons hundreds-to-thousands of rural many-small-fraction client cells"; at Austria's LINEAR S2 point it still strands 806 client cells (greedy 0, multistart 2) with travel 69 % above multistart's.

Seed 2 — lazy greedy (CELF)

greedy_round starts from the must-opens and repeatedly adds the pool cell whose opening saves the most population-weighted travel, until p are open. The gain of a cell is the sum, over the clients for which it would become the new nearest, of residents × (current best cost − its cost). Toy, from {A} (clients 1–3 at 60 minutes): gain(B) = 12·50 + 8·48 = 984, gain(C) = 12·48 + 10·50 = 1 076, gain(D) = 10·48 + 8·50 = 880. Greedy opens C → {A, C}, travel 500 + 144 + 100 + 480 = 1 224. That is how greedy fixes top-p's blindness: a low-y* cell that serves an otherwise far-served cluster gets picked.

Gains only shrink as the set grows (diminishing returns), so greedy_round re-scores only the cell at the top of its ranking (the fresh flag) and accepts it once fresh — the CELF trick; the submodularity argument and the 1 − 1/e guarantee are on Background theory. A quirk: a client no must-open reaches starts at cost Inf, not BIG, so greedy covers somebody first and only then minimises travel — probably why it is worse than top-p in 129 of the 1 406 logged rows, all at high λ (not verified). Multistart repairs this by re-scoring with BIG.

Seeds 3–10 — y*-weighted random draws (A-Res)

randomized_seed draws k pool cells without replacement with probability proportional to y*: each cell gets a key log(U_j) / y*_j, U_j uniform on (0, 1), and the k largest keys win — the Efraimidis–Spirakis (2006) scheme "A-Res", with the proof that the LP's fractions are "read directly as selection probabilities" in issue #47 and on Background theory. The randomness "lets the local search escape the local optimum a single deterministic rounding reaches" (issue #47).

Step 4 — polish every seed by swaps

Each seed is polished by vertex substitution, the classic local search for the p-median problem (exactly p sites, least total travel; Glossary): close one open pool cell r, open one closed pool cell f, if that lowers travel; repeat. swap_round! makes one best-improving swap per call; multistart_round calls it up to MS_ROUNDS = 12 times per seed, stopping when no swap improves.

Rather than re-assigning every client per (r, f) pair, the Resende & Werneck (2007) fast interchange keeps per client its nearest and second-nearest open cost (d1, d2; BIG if none) and sums loss[r] (closing r: its clients fall back to d2), gain[f] (opening f: clients nearer to f than d1) and a correction extra[f][r] for clients of r that would go to f rather than to their second-nearest. profit(f, r) = gain[f] − loss[r] + extra[f][r] is the exact travel change; a swap is accepted only when profit > 10⁻⁶, so travel strictly decreases at every accepted swap and the polish must terminate (Background theory has the derivation).

Toy, seed {A, B}: loss[B] = 12·50 + 8·48 = 984; gain[C] = 10·50 = 500 (client 2 only); extra[C][B] = 12·(60 − 12) = 576 (client 1 would move from B to C rather than back to A). Profit of swapping B for C: 500 − 984 + 576 = 92 — exactly 1 316 − 1 224. The random seed {A, D} (1 420) also swaps to C; every seed ends at {A, C}.

Step 5 — score honestly, keep the best

Every polished seed is scored by travel_of: each client at its nearest open cell at c(t) times residents, and a client with no open cell in its choice set charged BIG per resident — the same price the LP pays for unserved demand and the baseline for unreachable clients (big_cost(): c(120 min) for linear-type functions, 1.0 for LOGISTIC; Travel cost functions). This is what the code's comment calls coverage-honest: before e1c426b (7 June 2026) the rounding metric silently dropped stranded clients, which hid the top-p failure above; the baseline followed on 6 July (206923c, its word is coverage-consistent). The log's uncov_* columns ("stranded") count them for all three sets.

The lowest-travel polished seed wins (strict <: on a tie the earlier seed is kept), so travel_multi ≤ min(travel_topp, travel_greedy) holds by construction — and in all 1 406 logged rows of doc/deck_data.json. Toy: multistart = 1 224, nobody stranded. The random seeds come from a MersenneTwister(MS_SEED) re-created at every call, so identical inputs give identical open sets — the randomness is "a diversification device, not a source of run-to-run variance" (issue #47).

What the bounds certify — and what the reported gap is

The LP curve is a certified lower bound and the multistart curve a feasible upper bound on total cost; the integer optimum lies in the shaded band

The LP is a relaxation, so its optimum lies at or below the true integer optimum. The multistart set is a feasible network of the same soft-coverage problem — exactly p cells, everyone at their nearest open cell or stranded at the same BIG — so its cost lies at or above it:

travel_relax + λ·Σy*   ≤   integer optimum at λ   ≤   travel_multi + λ·p

Toy: 1 580 ≤ 1 716 ≤ 1 824. This is rigorous only because travel_relax (LP travel plus BIG × the unserved fraction, solve_at_w! around line 506), travel_of and the baseline all price stranding identically — true since 4ec47a9 (16 July 2026) fixed BIG at c(120) everywhere; the earlier per-area t_max and why it went are on Travel cost functions.

The chain bounds total cost only — not the count p (the toy's optimum has 3, we fixed 2) and not travel alone. Yet the "multi vs relax" column of the deck and results page is the travel-only ratio (travel_multi − travel_relax) / travel_relax (build_deck.mjs). The λ terms differ by λ·(p − Σy*), so this ratio can be negative — it is in 147 of the 1 406 rows, all points where p was rounded up and the rounded network had up to half a pharmacy more to spend than the LP. Toy: the travel-only "gap" reads +47 % (394 above 830), but 150 of that is location cost saved by opening 2 cells instead of 2.5, so the certified total-cost gap is 244 (+15 % of 1 580). A real row: Netherlands LINEAR w = 0.02 (doc/deck_data.json), sum_y 6 533.5 rounded up to 6 534, relax travel 6 284 887 above multi travel 6 283 895, yet the totals obey the chain: 19 351 887 ≤ 19 351 895.

Measured gaps

The "+0–18 % under LINEAR, +0–4.7 % under LOGISTIC" of the results page and README (Pharmacy results September 2026 §5, deck p62) are hand-typed strings in build_deck.mjs (around lines 165–167 and 622) from June–July 2026 (0c8aabb, 27c8c5e), before soft coverage and the #52 bisection, never refreshed; the 18 % has no recorded source. What doc/deck_data.json holds at commit e25416b (travel-only gap; "stranded" = client cells multistart leaves without an open pharmacy; λ = w · FACILITY_MIN_COSTS, Glossary):

Where LINEAR LOGISTIC
All S1/S2 points, full range −0.04 % … +2.9 % −0.08 % … +3.4 %
ITF S2 (Sud) — the only visible gap +2.9 %, 208 stranded +3.4 %, 730 stranded
Every other S1/S2 point < 0.3 % < 0.3 %
Sparse Sweden — many stranded, gap ≈ 0 SE2 S1: +0.05 %, 56 stranded SE3 S1: 0.00 %, 130 stranded
High-λ tails beyond S2 (no scenario) NL w = 1.5: +69 % (frac_y 530); Belgium w = 0.5: +179 % (frac_y 2 243) ITC w = 0.1: +46 % (frac_y 1 116)

The Swedish rows show what the ratio measures: the LP strands the same cells at the same BIG, so the rounding costs nothing extra; the results page's "sparse Swedish regions keep the largest gaps" is not reproducible from the current data. As of September 2026 (commit e25416b), quote ≤ 3.4 % at S1/S2 until the README is regenerated.

In the code

All in lp_run.jl at commit e25416b (permalinks pinned; line numbers drift). Open solve_at_w! at the comment "Three roundings of the LP relaxation" (L460, around line 525: p_open, top-p, the ROUNDING switch, mean_t), then multistart_round (L211: seeds, polish, keep best). The pieces: greedy_round (L23), assign_nearest for the arrows (L91), client_nearest for d1/d2 (L111), travel_of (L136), randomized_seed (L148), swap_round! (L161). Signatures: Code walkthrough lp_run; log columns: Log lines and output files; S2 is bisected on the selected rounding's travel cost_c (Code walkthrough lambda_sweep_simplex).

Cost: the three roundings take "≈50–100 s per point on a mid-size region, ten times the LP itself at low λ" (comment above solve_at_w!), which is why the refine-only walk of #52 calls solve_at_w!(…; rounding=false) — LP-only rows, no roundings, no arrows — until a bracket can close (Scenarios S1 S2 S3).

Knobs

All in settings.jl around lines 47–60; the 10 / 12 / 20240601 values have no recorded rationale (likely runtime).

Name Default What it changes Why you would change it Interactions
ROUNDING multistart Which set is selected (arrows, cost_c, S2 bisection, deck); all three are computed. Comparison experiments only. Any other value silently gives top-p.
MS_RESTARTS 10 Seeds per point, including top-p and greedy. More diversity at linear extra cost. ≤ 2 → no random seeds.
MS_ROUNDS 12 Maximum accepted swaps per seed. Raise when frac_y is in the hundreds and the tail gap is large; 0 disables polishing. Each round is a pass over the OD rows.
MS_SEED 20240601 RNG seed, re-used at every λ. Sensitivity test of the rounding to the draws. Random seeds only.
BIG_TRAVELTIME_MIN 120 BIG = c(120) for linear-type functions (LOGISTIC: 1.0). Experiments only. Couples LP, rounding and baseline — never change it for one of them.

Pitfalls and open questions

  • The printed gap is travel-only and can be negative; whether to print the total-cost gap alongside is open.
  • p = round(Σy*) is a heuristic count. Half-to-even is a Julia default, not a decision; floor/ceil or trying both neighbours were never compared.
  • Greedy prices clients no must-open reaches at Inf (Seed 2); intent unrecorded, harmless for the selected result.
  • MS_ROUNDS = 12 probably truncates the polish on the high-λ tails (the +69 %/+179 % rows); the log records no swap counts, so this is unverified, and those points enter no scenario table.
  • mean_t is not coverage-consistent — sweep rows count stranded residents at 0 minutes, the baseline at 120; compare cost_c instead (Log lines and output files).
  • Top-p is vertex-sensitive (ties in y* depend on which optimal vertex HiGHS, the LP solver, returns); multistart far less so.
  • The pool excludes y* = 0 cells (Step 2). Clients in excluded NUTS regions (Scope rules and data gaps) with wpop = 0 would give NaN gains in greedy; in practice they have no surviving OD rows.

See also

Clone this wiki locally