319. 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.

319.1. Formulation

Sets: customers , candidate facilities . Costs: (open facility ), (assign customer to facility ).

Decision variables:

s.t.:

319.2. 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: subsets — NP-hard in general, but tractable up to  1000 facilities with MIP solvers.

319.3. Erlenkotter’s dual ascent

A classical specialized algorithm (Erlenkotter 1978):

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

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

319.4. LP relaxation

The LP relaxation (drop to ) is a strong relaxation — gap typically under 5%. Good starting point for branch-and-cut.

319.5. Approximation algorithms

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

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

319.6. See also