Capacitated Facility Location

CFLP · BALINSKI 1965

Logistics · Network & Facility · Strategic

The Capacitated Facility Location Problem extends UFLP with an explicit capacity $u_i$ at each facility: no facility can serve more demand than its capacity allows. This fundamentally changes the structure: where UFLP always assigns each customer to its cheapest open facility, CFLP may need to split demand away from the nearest facility when capacity binds. It's the practitioner-most-relevant location formulation — real warehouses and DCs have real throughput limits. Solved classically by the Cornuéjols, Sridharan, Thizy (1991) Lagrangian relaxation and today by commercial MIP on moderate instances.

Mathematical formulation

Capacitated extension of Balinski UFLP

SymbolMeaning
$I$candidate facility sites
$J$customers with demand $d_j$
$f_i$fixed opening cost at site $i$
$u_i$capacity (throughput) at facility $i$
$c_{ij}$per-unit flow cost from $i$ to $j$
$y_i \in \{0,1\}$1 if facility $i$ is opened
$x_{ij} \ge 0$flow from facility $i$ to customer $j$ — may be fractional (split demand) in the "divisible" CFLP, or binary in the "single-source" CFLP
Objective: opening + transportation cost
$$\min \; \sum_{i \in I} f_i \, y_i \;+\; \sum_{i \in I} \sum_{j \in J} c_{ij} \, x_{ij}$$
(1) Demand satisfaction at every customer
$$\sum_{i \in I} x_{ij} = d_j \quad \forall j \in J$$
(2) Capacity at each facility
$$\sum_{j \in J} x_{ij} \le u_i \, y_i \quad \forall i \in I$$
(3) Variable domains (divisible CFLP)
$$y_i \in \{0,1\}, \quad x_{ij} \ge 0$$

Single-source vs divisible. If every customer must be served by exactly one facility, replace $x_{ij} \ge 0$ with $x_{ij} \in \{0, d_j\}$ (equivalently, introduce a binary assignment variable). Single-source CFLP is significantly harder than the divisible variant — contains bin packing as a special case.

Complexity & solution. NP-hard (generalises UFLP). For metric single-source CFLP, the best-known approximation ratio is around 5 (Pál-Tardos 2001). In practice: Lagrangian relaxation on the capacity constraints (Cornuéjols, Sridharan, Thizy 1991) drives branch-and-bound; modern MIP solvers handle hundreds of facilities directly. The Volume Algorithm (Barahona-Anbil 2000) and column generation are also widely used.

Key references

Balinski, M. L. (1965).
“Integer programming: Methods, uses, computation.”
Management Science, 12(3), 253–313. doi:10.1287/mnsc.12.3.253
Cornuéjols, G., Sridharan, R., & Thizy, J.-M. (1991).
“A comparison of heuristics and relaxations for the capacitated plant location problem.”
European Journal of Operational Research, 50(3), 280–297. doi:10.1016/0377-2217(91)90261-S
Barahona, F., & Anbil, R. (2000).
“The volume algorithm: Producing primal solutions with a subgradient method.”
Mathematical Programming, 87, 385–399. doi:10.1007/s101070050017
Pál, M., & Tardos, É. (2001).
“Group strategyproof mechanisms via primal-dual algorithms.”
FOCS 2003. (Capacitated facility location approximation.)
Avella, P., & Boccia, M. (2009).
“A cutting plane algorithm for the Capacitated Facility Location Problem.”
Computational Optimization and Applications, 43, 39–65. doi:10.1007/s10589-007-9125-x
Daskin, M. S. (2013).
Network and Discrete Location (2nd ed.).
Wiley. doi:10.1002/9781118537015

Capacity is what separates textbook from real.
Let's scope your CFLP instance.

Get in Touch
Data and numerical examples are illustrative. Pages on this site are educational tools, not production software.