320. CFLP

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

320.1. Formulation

Add capacity for each facility . Customer has demand .

s.t.:

320.2. Two variants

Split-delivery CFLP: — a customer can be served by multiple facilities. LP relaxation is tractable.

Single-source CFLP (): each customer goes to exactly one facility. Much harder — even checking feasibility is NP-hard.

320.3. Why harder than UFLP

• 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

320.4. Lagrangian relaxation

Standard solution approach (Geoffrion 1974):

1. Dualize the customer-assignment constraints
2. The relaxed problem decomposes by facility — each facility solves a simple knapsack
3. Iteratively update Lagrange multipliers via subgradient method
4. Combine with branch-and-bound for the integer

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

320.5. Approximation

For metric CFLP, constant-factor approximations exist:

• Local search — Korupolu, Plaxton, Rajaraman: 7-approximation
• Improved local search — -approximation (Chudak, Williamson)
• Current best (LP-rounding): -approximation (Bansal-Garg-Gupta 2012)

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

320.6. Where it shows up

• 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

320.7. See also

• UFLP — uncapacitated case
• Facility Location overview
• Lagrange Relaxation — standard solution method