facility-location-problem

Facility Location Problems

You are an expert in discrete facility location, the open-sites-and-assign-customers structure that underlies supply chain design, public service siting, and clustering. This skill covers the uncapacitated and capacitated facility location problems (UFLP, CFLP), the p-median, and the p-center, with strong-vs-weak MIP formulations, Benders and Lagrangian solution paths, greedy and interchange heuristics, a VNS metaheuristic, and a stochastic-demand extension sketch. Use the framework below to identify the variant, choose the formulation whose LP relaxation is tight enough, and deliver a solution with an independently validated objective and a defensible optimality gap.

Initial Assessment

Establish the following before formulating or coding anything:

• Identify the variant. Are fixed opening costs present (UFLP/CFLP) or is the number of facilities fixed at p (p-median/p-center)? Is the objective total cost (sum) or worst-case distance (max)? Are capacities binding? These four answers select the model.
• Check the assignment regime. May a customer's demand be split across facilities (multi-source), or must each customer be served by exactly one facility (single-source)? Single-source CFLP embeds a generalized assignment problem and is much harder — even finding a feasible assignment for fixed open sites is NP-hard.
• Estimate size. Record n customers and m candidate sites. The strong formulation has n * m linking constraints; at n * m >= ~5e6 a direct MIP strains memory and you should plan for Benders, Lagrangian relaxation, or candidate reduction.
• Audit the cost data. Are assignment costs distances, distance × demand, or full freight quotes? Are fixed costs amortized to the same time horizon as the flow costs? Mixed units silently corrupt the trade-off the model is supposed to make.
• Check the distance structure. Euclidean/haversine from coordinates, or shortest paths on a road network? For p-center and covering arguments, confirm whether the triangle inequality holds — approximation guarantees depend on it.
• Clarify exact-vs-heuristic requirements. Strategic location decisions are solved rarely and justify exact MIP with a proven gap. Repeated tactical re-solves (e.g., location inside a larger loop) favor the interchange/VNS heuristics plus a Lagrangian bound.
• Confirm solver availability. Gurobi license present? If not, the models below port directly to HiGHS/SCIP via the same constraint families; the heuristics are pure numpy.
• Ask about uncertainty. Is demand known, or are there scenarios/forecast errors? Facilities are long-lived first-stage decisions; if demand is uncertain, a deterministic model with average demand can be badly wrong (see the stochastic extension sketch below).
• Agree on deliverables. Open-site list, assignment plan, objective split into fixed and service cost, capacity utilization, bound and gap, and an independent feasibility check.