Describe selection algorithm in multipart facility rounding

[cjacobscrisioni]

How does the Julia code allocate discrete facilities in every draw?

[MaartenHilferink]

Selection algorithm in the multi-start facility rounding

Documented in the methodology draft §2.2.2 and implemented in lp_run.jl (randomized_seed, multistart_round). Summary for the record.

Setup. The LP relaxation returns a fractional openness x_j ∈ [0,1] per candidate facility. We fix the discrete facility count to p = round(Σⱼ xⱼ) (so the discrete pattern stays an apples-to-apples point on the same Pareto curve), split facilities into must-open (x_j ≥ 1−tol, held fixed) and fractional (0 < x_j < 1), and choose k = p − #must-open of the fractional facilities to open.

Multi-start. We generate several candidate patterns and keep the lowest-cost one:

• two deterministic seeds — top-p (largest x_j) and a greedy/CELF rule (must-open set + repeatedly add the fractional facility that most reduces population-weighted travel);
• the rest are randomised weighted draws (below);
• each candidate is polished by a best-improving swap local search (Resende–Werneck fast interchange);
• scoring is coverage-honest: a client with no open facility in its choice set is charged c(t_max), so stranding demand is never free.

The weighted random draw — Efraimidis–Spirakis A-Res. For each fractional facility j, draw U_j ~ Uniform(0,1) and form the key

key_j = ln(U_j) / x_j

then open the k facilities with the largest keys. This is weighted sampling without replacement with selection probability ∝ x_j — the relaxed solution is read directly as selection probabilities.

Why ∝ x_j. −ln(U_j) is a standard Exponential(1) variate, so −key_j = −ln(U_j)/x_j is Exponential with rate x_j. Taking the largest key = taking the smallest of independent exponentials with rates x_1, x_2, …. The minimum of independent exponentials is attained by facility j with probability x_j / Σᵢ xᵢ; iterating over the successively removed facilities reproduces the standard without-replacement weighted distribution. High-x_j facilities are thus likely — but not certain — to be chosen, which diversifies the starts and lets the local search escape the local optimum a single deterministic rounding reaches (notably where the LP spreads ~one facility's worth of demand over many small fractions).

Reproducibility. The RNG is seeded with a fixed constant (MS_SEED), so the whole discretisation is deterministic — identical inputs → identical discrete solution. The randomness is only a diversification device, not a source of run-to-run variance.

References

• Efraimidis, P.S., Spirakis, P.G. (2006). Weighted random sampling with a reservoir. Information Processing Letters 97(5), 181–185.
• Resende, M.G.C., Werneck, R.F. (2007). A fast swap-based local search procedure for location problems. Annals of Operations Research 150(1), 205–230.

[MaartenHilferink]

Reopen if you have any follow-up questions.