🧩 Constraint Solving POTD:Problem of the Day: Facility Location Problem

[github-actions[bot]]

Problem Statement

The Facility Location Problem asks: where should we place warehouses, factories, or service centers to minimize the total cost of serving a set of customers?

Given:

• A set of m potential facility locations (e.g., warehouses)
• A set of n customer locations with demands
• Fixed cost to open facility j
• Cost to serve customer i from facility j

Find:

• Which facilities to open
• How to assign each customer to exactly one open facility

Such that the total cost (opening + serving) is minimized.

Concrete Instance

Suppose we have:

• 3 potential warehouses in cities A, B, C with opening costs: $100, $120, $110
• 4 customers with demands in cities 1–4
• Transportation costs (per unit):

From \ To	Customer 1	Customer 2	Customer 3	Customer 4
Warehouse A	5	8	12	9
Warehouse B	10	3	6	7
Warehouse C	7	9	4	8

Each customer has a demand of 1 unit. Which warehouses should we open, and how should we route customers to minimize total cost?

Why It Matters

Supply Chain Design: Companies must decide where to establish distribution centers to serve regional markets efficiently without over-investing in infrastructure.

Data Center Placement: Cloud providers use facility location models to decide which data centers to operate globally, balancing latency guarantees against operational costs.

Public Services: Governments apply these techniques to locate fire stations, hospitals, or schools to balance coverage and budget constraints.

Retail Networks: Retailers optimize store locations by modeling customer demand, real estate costs, and competition—all variants of facility location.

Modeling Approaches

Approach 1: Mixed-Integer Linear Programming (MIP)

Model:

Decision variables:
  y_j ∈ {0,1}     (open facility j or not)
  x_ij ≥ 0        (units of demand from customer i served by facility j)

Objective:
  minimize ∑_j f_j * y_j + ∑_i,j c_ij * x_ij

Constraints:
  ∀i: ∑_j x_ij = d_i                (satisfy customer i demand)
  ∀i,j: x_ij ≤ d_i * y_j            (can only serve from open facility)

Trade-offs:

• Strength: Linear formulation works with commercial solvers (CPLEX, Gurobi, CBC).
• Weakness: Big-M constraints on x_ij ≤ d_i * y_j can weaken LP relaxations.
• Scalability: Good for instances up to ~1000 facilities and customers with modern solvers.

Approach 2: Constraint Programming (CP)

Model:

Decision variables:
  open[j] ∈ {0,1}                    (facility j open)
  assigned[i] ∈ 1..m                 (customer i assigned to facility)
  cost = sum of opening costs + assignment costs

Constraints:
  ∀i: assigned[i] must map to an open facility
       (if open[assigned[i]] = 0, constraint fails)
  minimize cost

Trade-offs:

• Strength: Reification and channeling constraints allow elegant problem modeling; strong propagation when combined with global constraints.
• Weakness: Less effective on purely continuous cost calculations; less developed for large-scale problems.
• Scalability: Competitive for medium instances; excellent for highly constrained variants (e.g., capacity limits).

Approach 3: Local Search / Metaheuristics

Idea:

• Start with a feasible solution (e.g., open k largest-demand facilities).
• Iteratively improve by adding/removing facilities or reassigning customers.
• Use tabu search or simulated annealing to escape local optima.

Trade-offs:

• Strength: Scalable to very large instances; finds good solutions quickly; handles non-linear costs easily.
• Weakness: No optimality guarantee; quality depends heavily on initialization and parameters.
• Scalability: Excellent for 10,000+ facilities and customers.

Key Techniques

1. Disaggregation & Valid Inequalities

Rather than relying on the weak x_ij ≤ d_i * y_j constraint, use disaggregated formulations or add cutting planes (e.g., ∑_i x_ij ≤ M_j * y_j where M_j is facility j's capacity) to tighten the LP relaxation and accelerate branch-and-bound.

2. Variable Fixing via Lagrangian Relaxation

Relax the demand-satisfaction constraints (dualize them). For each Lagrangian value, solve a knapsack-like subproblem per facility. Recover dual bounds and use them to identify facilities that must/cannot be open, pruning the search tree.

3. Greedy + Local Optimization

A simple construction heuristic:

• Start with no facilities open.
• Greedily open the facility that reduces total cost most.
• Repeat until all customers are served.
• Then apply local search (swap facilities, or reassign customers) to improve.

This often yields solutions within 5–10% of optimal and provides a warm start for exact methods.

4. Symmetry Breaking (in CP)

If multiple facilities are identical (same fixed cost and transportation costs), post ordering constraints open[j] ≥ open[j+1] to break symmetry and reduce the search space.

Example Model (Pseudo-code / MiniZinc-style)

int: m = 3;  % warehouses
int: n = 4;  % customers
array[1..m] of int: f = [100, 120, 110];          % opening costs
array[1..n] of int: d = [1, 1, 1, 1];             % demands
array[1..m, 1..n] of int: c = [
  [5, 8, 12, 9],
  [10, 3, 6, 7],
  [7, 9, 4, 8]
];

var array[1..m] of 0..1: y;          % open[j]
var array[1..n] of 1..m: assigned;   % assigned[i]
var int: total_cost;

constraint forall(i in 1..n)(
  y[assigned[i]] = 1
);

constraint total_cost = sum(j in 1..m)(f[j] * y[j]) 
                      + sum(i in 1..n)(c[assigned[i], i]);

solve minimize total_cost;

Challenge Corner

1. Capacity Extension: Suppose each facility has a maximum capacity. How would you add this constraint to each model? Which approach handles it most gracefully?

2. Dual Bounds: Can you derive a lower bound on the optimal cost by ignoring the facility-opening decision and just serving each customer from its cheapest source?

3. Symmetry in Your Instance: In the example above, could two warehouses be swapped without changing the total cost? How would you add symmetry-breaking constraints to the MIP?

References

1. Guignard, M., & Rosenwein, M. B. (1989). "An Improved Dual-Based Algorithm for the Capacitated Facility Location Problem." Journal of the Operational Research Society, 40(12), 1144–1156.

   • Classic paper on Lagrangian relaxation and variable fixing for FLP.

2. Rossi, F., van Beek, P., & Walsh, T. (Eds.). (2006). Handbook of Constraint Programming. Elsevier.

   • Chapter on global constraints and modeling techniques for location problems.

3. Mirchandani, P. B., & Francis, R. L. (1990). Discrete Location Theory. Wiley-Interscience.

   • Comprehensive reference on facility location variants and algorithms.

4. OR-Tools Documentation: Vehicle Routing Library.

   • Practical examples of location-routing integration: (developers.google.com/redacted)

---

Next time: What does the real world add? Congestion, time windows, multiple product types—we'll explore how variants of facility location extend to integrated supply-chain problems.

Generated by 🧩 Constraint Solving — Problem of the Day · copilot · haiku45 · 6.63 AIC · ⌖ 6.81 AIC · ⊞ 6K · ◷

• expires on Oct 12, 2026, 3:36 AM UTC-08:00

[github-actions[bot]]

This discussion has been marked as outdated by Constraint Solving — Problem of the Day.

A newer discussion is available at Discussion #66104.