UFLP

322. UFLP

Uncapacitated Facility Location Problem: open a subset of candidate facilities and assign each customer to one open facility, minimizing fixed + transport costs. No capacity limits.

322.1. Formulation

Sets: customers $𝐼$ , candidate facilities $𝐽$ . Costs: $𝑓_{𝑗}$ (open facility $𝑗$ ), $𝑐_{𝑖 𝑗}$ (assign customer $𝑖$ to facility $𝑗$ ).

Decision variables:

$𝑦_{𝑗} \in {0, 1}$ — open facility $𝑗$ ?
$𝑥_{𝑖 𝑗} \in [0, 1]$ — fraction of customer $𝑖$ ’s demand served by $𝑗$ (or $𝑥 \in {0, 1}$ for single-sourcing)

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

s.t.:

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

𝑥_{𝑖 𝑗} \leq 𝑦_{𝑗}, \forall 𝑖, 𝑗 (can only assign to open facilities)

𝑦_{𝑗} \in {0, 1}, 𝑥_{𝑖 𝑗} \geq 0

322.2. Picture

322.3. Structure

Once $𝑦$ is fixed (which facilities are open), the assignment is trivial — each customer chooses its cheapest open facility. So UFLP reduces to choosing a subset of facilities.

For $| 𝐽 | = 𝑛$ candidates: $2^{𝑛}$ subsets — NP-hard in general, but tractable up to 1000 facilities with MIP solvers.

322.4. Erlenkotter’s dual ascent

A classical specialized algorithm (Erlenkotter 1978):

Start with weak dual solution
Iteratively raise dual variables while maintaining feasibility
At each step, dual values determine which facilities must be open
Heuristic primal construction from dual

Often achieves provably-optimal solutions on instances with 1000+ candidates. Predates modern MIP solvers but still competitive.

322.5. LP relaxation

The LP relaxation (drop $𝑦 \in {0, 1}$ to $𝑦 \in [0, 1]$ ) is a strong relaxation — gap typically under 5%. Good starting point for branch-and-cut.

322.6. Approximation algorithms

UFLP admits constant-factor approximations (the problem is APX-hard but admits PTAS in some special cases):

Greedy (Mahdian, Markakis, Saberi, Vazirani 2003): $1.61$ -approximation
LP-rounding / primal-dual: $1.5$ -approximation for metric UFLP (Byrka 2007)
Open-source: $1.488$ -approximation (Li 2013) — current best

For metric UFLP (costs satisfy triangle inequality), $1.46$ is the lower bound on what’s achievable (Sviridenko-Vyacheslav 2010).

322.7. See also

CFLP — with capacities
Facility Location overview
$𝑝$ -median — fixed number of facilities, no fixed cost
Lagrange relaxation — bounds for branch-and-bound