Facility location

Short note. A compact reference, correct as far as it goes. It will be expanded into a full guide with a worked example and an interactive demonstration.

Problem

You’re choosing from a set of candidate sites (warehouses, plants, cell towers) which to actually open — each has a fixed cost — and then deciding how each customer’s demand is served from the opened sites, to minimize fixed cost plus transportation/service cost.

When to use it

Warehouse network design, plant siting, retail store placement — any “where should we build, and who does each site serve” question. This is the canonical pattern behind supply chain network design work.

Formulation

Binary y_i = 1 if facility i is opened. Continuous (or binary, for single-sourcing) x_ij is the fraction of customer j’s demand served from facility i:

minimize   sum(f_i * y_i) + sum(c_ij * x_ij)
subject to:
  sum_i(x_ij) = 1            for all j      # every customer fully served
  x_ij <= y_i                for all i, j   # can only serve from open facilities
  sum_j(d_j * x_ij) <= cap_i * y_i           # capacity, if facilities are capacitated

The x_ij <= y_i line is the same conditional-activation idea as Big-M, just written in its simplest ratio form since y_i is already binary and x_ij is bounded by 1.

Code sketch

import pulp

prob = pulp.LpProblem("facility_location", pulp.LpMinimize)
y = {i: pulp.LpVariable(f"open_{i}", cat="Binary") for i in facilities}
x = {(i, j): pulp.LpVariable(f"serve_{i}_{j}", lowBound=0, upBound=1)
     for i in facilities for j in customers}

prob += (pulp.lpSum(fixed_cost[i] * y[i] for i in facilities) +
         pulp.lpSum(transport_cost[i, j] * x[i, j] for i in facilities for j in customers))

for j in customers:
    prob += pulp.lpSum(x[i, j] for i in facilities) == 1
for i in facilities:
    for j in customers:
        prob += x[i, j] <= y[i]

Pitfalls

• If you force x_ij to be binary (single-sourcing: each customer served from exactly one facility), the problem gets meaningfully harder — the continuous relaxation is a common simplification when split-sourcing is operationally acceptable.
• Real network design almost always layers in multi-echelon structure (plants feeding warehouses feeding stores) — that’s this pattern applied twice with the output of one layer as the “customers” for the next.
• Don’t forget the fixed cost trade-off can be non-obvious: opening one more facility might raise fixed cost but cut transportation cost enough to win overall. Always sanity-check a few opened/closed configurations by hand against the solver’s answer.