CFLP

323. CFLP

Capacitated Facility Location Problem: like UFLP, but each facility has a maximum capacity it can serve.

Add capacity $𝑢_{𝑗}$ for each facility $𝑗$ . Customer $𝑖$ has demand $𝑑_{𝑖}$ .

min \sum_{𝑗} 𝑓_{𝑗} 𝑦_{𝑗} + \sum_{𝑖} \sum_{𝑗} 𝑐_{𝑖 𝑗} 𝑥_{𝑖 𝑗}

s.t.:

\sum_{𝑗} 𝑥_{𝑖 𝑗} = 1, \forall 𝑖 (customer fully served)

\sum_{𝑖} 𝑑_{𝑖} 𝑥_{𝑖 𝑗} \leq 𝑢_{𝑗} 𝑦_{𝑗}, \forall 𝑗 (capacity)

𝑦_{𝑗} \in {0, 1}, 𝑥_{𝑖 𝑗} \in [0, 1] (split delivery) or {0, 1} (single sourcing)

The red link marks an over-capacity assignment that forces a customer onto a farther facility.

Split-delivery CFLP: $𝑥_{𝑖 𝑗} \in [0, 1]$ — a customer can be served by multiple facilities. LP relaxation is tractable.

Single-source CFLP ( $𝑥_{𝑖 𝑗} \in {0, 1}$ ): each customer goes to exactly one facility. Much harder — even checking feasibility is NP-hard.

Capacity coupling: opening a small far facility might be forced just to handle overflow from a nearby capacitated one
LP relaxation weaker — capacity constraints reduce the integrality of the LP
No simple greedy approximation

Standard solution approach (Geoffrion 1974):

Dualize the customer-assignment constraints $\sum_{𝑗} 𝑥_{𝑖 𝑗} = 1$
The relaxed problem decomposes by facility — each facility solves a simple knapsack
Iteratively update Lagrange multipliers via subgradient method
Combine with branch-and-bound for the integer $𝑦$

Gives strong bounds (often within 1-2% of optimum) and a feasible primal heuristic.

For metric CFLP, constant-factor approximations exist:

Practical solvers (MIP, Lagrangian) usually beat the worst-case approximation by far on real instances.

Warehouse network design — each DC has capacity (workforce, square footage, throughput)
Plant location — plants have production limits
Cloud / data center sizing — placement + capacity
Healthcare networks — hospital bed capacity drives location choice