Facility Location Solver

Pseudocode

The uncapacitated facility location problem trades off the fixed cost of opening a site against the transport cost of serving customers from it. Greedy opens whichever site most improves the total.

GreedyFacilityLocation(sites, customers):
    open = {}
    cost[c] = infinity for every customer c

    repeat:
        best = null
        for each unopened site s:
            // saving = reduction in service cost, minus
            // the fixed cost of opening s
            saving = sum over c of max(0, cost[c] - d(c,s))
                     - openCost[s]
            if saving > best.saving: best = s

        if best is null or best.saving <= 0: stop
        open.add(best)
        cost[c] = min(cost[c], d(c, best)) for every c

The greedy rule is submodular: each additional facility helps less than the one before, because customers already served cheaply cannot be improved much. That structure is what gives greedy its provable guarantee, a factor of 1 + ln n for the uncapacitated version, and it is why the stopping rule is simply "no site has positive saving left".

Worked example, step by step

Decide which of two candidate depots to open when serving four customers, weighing fixed cost against travel.

Example graph: Customers at positions 0, 2, 8 and 10 on a line. Candidate sites at position 1 and position 9, each costing 10 to open. Service cost is the distance.

1. Evaluate opening site 1 alone. Distances from position 1 are 1, 1, 7 and 9, totalling 18, plus the fixed cost 10, giving 28.
2. Evaluate opening site 9 alone. Distances from position 9 are 9, 7, 1 and 1, also totalling 18, plus 10, giving 28. The two single-site options tie.
3. First greedy pick. Either site gives a saving over serving nobody, so greedy opens one, say site 1, for a running total of 28.
4. Evaluate adding site 9. With site 1 open, customers at 0 and 2 already cost 1 each and would not improve. Customers at 8 and 10 currently cost 7 and 9, and would drop to 1 and 1, saving 6 and 8 for a total saving of 14. Subtract the fixed cost of 10 and the net saving is 4, which is positive.
5. Open the second site. Total becomes 10 + 10 fixed, plus service costs 1 + 1 + 1 + 1 = 4, giving 24. No further sites exist, so the algorithm stops.

The optimal solution opens both depots for a total of 24, beating either single depot at 28. The instructive part is the second evaluation: the saving from adding a facility is measured only against what customers currently pay, not against serving them from nothing. That is why the marginal value of each new facility falls as more are opened, and why greedy stops when the next one would cost more than it saves.

Complexity, and where it comes from

Time: NP-hard; O(n·m^2) greedy · Space: O(n + m)

With n customers and m candidate sites, each greedy round evaluates every unopened site against every customer at O(n·m), and there are at most m rounds, giving O(n·m squared). The problem itself is NP-hard, reducing from set cover, and that reduction also transfers the hardness of approximation: no polynomial algorithm can beat a factor of 1 + ln n unless P equals NP. Greedy achieves exactly that bound for the uncapacitated case, so it is not merely a reasonable heuristic but provably the best possible ratio in general. The metric version, where distances obey the triangle inequality, admits better constant-factor approximations, currently around 1.488.

When to use Facility Location, and when not to

The right model depends on whether facilities have capacity and whether you are minimising total cost or worst-case distance.

Common pitfalls

• Ignoring the fixed cost when comparing sites. Ranking candidates purely by how much travel they save always opens too many facilities. The saving must be net of the opening cost, and the algorithm must stop when that net figure turns negative.
• Assuming greedy is close to optimal in the worst case. The 1 + ln n bound is logarithmic, not constant, so on adversarial instances greedy can be genuinely far off. That bound is also the best any polynomial algorithm can achieve for the general problem, so the limitation is the problem, not the algorithm.
• Using straight-line distance for road networks. Euclidean distance systematically underestimates travel cost where rivers, motorways or one-way systems matter. Feed in real network distances from a shortest-path computation, or the chosen sites will be wrong in a way no amount of optimisation fixes.
• Forgetting capacity constraints exist. The uncapacitated model happily assigns every customer to one depot. If sites have real throughput limits the resulting plan is infeasible, and the capacitated variant, which is a harder problem, is required.
• Treating demand as uniform. Customers usually differ in volume. Service cost should be distance multiplied by demand, otherwise a distant high-volume customer is weighted the same as a nearby trivial one.

Frequently asked questions

What is the facility location problem?

Given a set of customers and a set of candidate sites, each with a fixed opening cost and a service cost to each customer, the problem is to decide which sites to open and how to assign customers so that total cost is minimised. It models warehouse placement, retail siting, server placement and emergency service coverage.

Is facility location NP-hard?

Yes. It reduces from set cover, and that reduction also carries over the hardness of approximation: no polynomial algorithm can guarantee better than 1 + ln n times optimal unless P equals NP. The greedy algorithm achieves that bound, making it optimal among polynomial approximations for the general case.

What is the difference between capacitated and uncapacitated facility location?

In the uncapacitated version each open site can serve unlimited demand, so every customer simply goes to its nearest open facility. In the capacitated version sites have throughput limits, so customers must be allocated subject to those limits, which makes assignment an optimisation problem in itself rather than a lookup.

How does facility location differ from k-means?

k-means places centres anywhere in continuous space and always produces exactly k of them, minimising squared distance. Facility location chooses from a fixed list of candidate sites, decides how many to open by trading transport cost against fixed opening cost, and typically minimises actual distance rather than its square.

What is the difference between k-median and k-center?

k-median minimises the total or average distance from customers to their assigned facility, which suits cost minimisation. k-center minimises the maximum distance any single customer travels, which suits service guarantees such as ambulance response times. They frequently produce different answers on the same data.