Introduction to Integer Programming in Facility Location

Facility location decisions are strategic choices that ripple through every part of an organization’s operations. Whether you are siting a new distribution center, expanding a network of retail stores, or deploying emergency response stations, the question of where to place facilities directly affects costs, service quality, and competitive advantage. Integer programming provides a rigorous mathematical framework to answer these questions optimally, even when the problem includes binary choices, discrete constraints, and complex trade-offs. This guide walks through the fundamentals, formulation techniques, solution methods, and real-world applications of integer programming for facility location problems, equipping decision-makers with the tools to turn location data into actionable, optimal plans.

Understanding Facility Location Problems

Facility location problems (FLPs) are a class of optimization problems that aim to select positions for one or more facilities from a finite set of candidate sites, while assigning customers to those facilities to minimize a combination of fixed opening costs and variable transportation or service costs. The core challenge lies in balancing the number of facilities—and their locations—against the resulting service distances, capacity utilization, and budget limits.

Classic variants include:

  • Uncapacitated Facility Location (UFLP): No limit on how much a facility can serve; the trade‑off is between fixed opening costs and transportation costs.
  • Capacitated Facility Location (CFLP): Each facility has a maximum capacity (e.g., warehouse square footage or production volume), requiring careful demand allocation.
  • p‑Median Problem: Choose exactly p facilities to minimize total weighted distance between customers and their assigned facility.
  • p‑Center Problem: Minimize the maximum distance between any customer and its nearest facility – critical for emergency services.

Other variations incorporate multi‑period dynamics, stochastic demand, or multiple levels of hierarchy. Regardless of the variant, the common thread is the need for discrete decisions: open or not open a facility, assign a customer to one facility or another. These binary choices make integer programming the natural optimization engine behind facility location models.

Fundamentals of Integer Programming

Integer programming (IP) is a branch of mathematical optimization where some or all decision variables are constrained to take integer values. In facility location, the most common integer variables are binary (0/1) representing open/close decisions. The general form of an integer program is:

Minimize  cT x
Subject to  A x ≤ b,  x ∈ ℤn+ (or {0,1}n)

When only some variables are integer, the model is called a mixed‑integer program (MIP). MIPs are ubiquitous in practice because they combine continuous decisions (e.g., flow quantities) with discrete choices (e.g., location selections).

The key advantage of integer programming over simple linear programming is its ability to enforce logical constraints. For example, the constraint “if facility A is opened, then facility B cannot be opened” can be expressed as xA + xB ≤ 1. Similarly, “customer j can be served only by an open facility i” becomes yij ≤ M × xi, where M is a large constant.

Solving an IP is generally NP‑hard, meaning no polynomial‑time algorithm exists for all instances. However, modern solvers leverage clever enumeration techniques (branch‑and‑bound) and polyhedral theory (cutting planes) to solve large, real‑world instances in acceptable time.

Formulating Facility Location as an Integer Program

Variables and Objective

The most common formulation for a single‑echelon, single‑product facility location problem uses two sets of variables:

  • xi: binary variable equal to 1 if facility i is opened, 0 otherwise.
  • yij: continuous (often non‑negative) variable representing the amount of flow shipped from facility i to customer j. In some models this can be binary if single‑sourcing is required.

The objective function minimizes total cost:

Minimize   Σi Fi xi + Σi Σj Cij yij

where Fi is the fixed cost of opening facility i, and Cij is the per‑unit transportation cost from i to j. For the p‑median problem, the term Σ Fi xi is replaced by a constraint Σ xi = p (no fixed costs).

Key Constraints

Four categories of constraints are typical:

  1. Demand satisfaction: For each customer j, total received flow from all facilities must equal (or exceed) its demand Dj.
  2. Capacity limits: For each facility i, total outflow ≤ capacity Ki × xi. This enforces that a closed facility ships nothing.
  3. Logical linking: yij ≤ M × xi (big‑M constraint) ensures flow can only originate from an open facility.
  4. Binary/integrality: xi ∈ {0,1}; if single‑sourcing is required, yij ∈ {0,1}.

A compact formulation for the uncapacitated case can omit explicit capacity constraints; the big‑M constraints are still needed to link flow to open facilities.

Example: Small UFLP Instance

Suppose we have three candidate facilities and four customers. Demand D = [100, 150, 80, 120]; fixed costs F = [5000, 7000, 4000]; transportation costs per unit are given in a matrix (not shown for brevity). The integer program will select a subset of facilities and assign each customer’s demand to one or more open facilities to minimize the sum of fixed and transportation costs. A solver will test combinations: open only facility 2? Or facilities 1 and 3? The IP formulation guarantees the globally optimal combination.

Solution Methods for Integer Programming Models

Solving large‑scale facility location IPs requires efficient algorithms deployed in robust solver software.

Branch‑and‑Bound

Branch‑and‑bound systematically explores the space of integer solutions by relaxing integrality (solving the linear programming relaxation), then branching on a fractional variable. The LP relaxation provides a lower bound (in minimization). Subtrees are pruned when the bound exceeds the current incumbent (best integer solution found). This is the backbone of nearly every commercial MIP solver.

Cutting Planes

Cutting planes add additional linear constraints (cuts) that tighten the LP relaxation, bringing the fractional solution closer to the integer hull without removing feasible integer points. Common cuts for facility location include cover inequalities and Gomory mixed‑integer cuts. Modern solvers combine branch‑and‑bound with cutting planes in a technique called branch‑and‑cut.

Heuristics and Metaheuristics

When exact methods are too slow (e.g., for extremely large networks), heuristic approaches can produce high‑quality solutions quickly. Popular heuristics include:

  • Lagrangian relaxation: Dualize difficult constraints (e.g., capacity) to decompose the problem into simpler subproblems.
  • Greedy algorithms with interchange: Start with an initial set of facilities then swap or add/remove sites to improve the objective.
  • Genetic algorithms / simulated annealing: Useful for highly combinatorial variants, though without optimality guarantees.

Commercial and Open‑Source Solvers

For industrial‑size problems, state‑of‑the‑art solvers such as Gurobi, IBM ILOG CPLEX, and FICO Xpress are preferred for their speed, reliability, and built‑in presolve. Open‑source alternatives like SCIP and the Google OR‑Tools framework are also capable for many problems. The choice depends on budget, problem scale, and required performance.

Advanced Modeling Considerations

Stochastic Facility Location

Demand is rarely known with certainty. In stochastic integer programming, uncertainty is represented by scenarios. The objective becomes expected cost, and constraints must hold for each scenario or with a chance (probabilistic) formulation. Two‑stage stochastic programs decide facility locations in the first stage and adapt flows in the second stage once demand is observed.

Robust Optimization

Robust models protect against worst‑case realizations of uncertain parameters (e.g., demand spikes, cost inflation). Instead of minimizing expected cost, they minimize the maximum cost over a predefined uncertainty set. This is computationally more tractable than full stochastic programming and is increasingly used in supply chain design.

Multi‑Objective Facility Location

Often decision‑makers care about cost, customer service (e.g., average distance), and equity (e.g., fairness in service coverage). Multi‑objective integer programming uses techniques such as the weighted sum method or epsilon‑constraint method to generate a set of Pareto‑optimal solutions, allowing trade‑off analysis.

Real‑World Applications

Integer programming for facility location is deployed across diverse industries:

  • Supply Chain & Logistics: Amazon and Walmart use location models to decide where to place fulfillment centers and distribution hubs, balancing inventory holding costs, transportation costs, and delivery speed.
  • Healthcare: Hospitals, clinics, and vaccination sites are sited to maximize population coverage while respecting budget and capacity. During the COVID‑19 pandemic, integer programming helped plan testing and vaccination station placement in several cities.
  • Emergency Services: Fire stations, ambulance depots, and disaster relief centers are placed using p‑center models to minimize response times. New York City Fire Department reportedly used such models for station relocation.
  • Retail & Banking: Banks decide branch locations; retailers plan store networks. Integer programming can incorporate demographic data, competitor locations, and cannibalization effects.
  • Telecommunications: Cell tower placement and fiber‑optic network design rely on extensions of facility location models with additional coverage and interference constraints.
  • Renewable Energy: Siting wind farms or solar plants involves location decisions that consider wind/solar potential, land cost, and transmission line availability—amenable to IP with continuous energy output variables.

Benefits and Practical Challenges

Benefits

  • Optimality: Unlike rule‑of‑thumb or manual methods, integer programming provides provable optimal solutions (or bounds).
  • Flexibility: A wide range of constraints—budget, service levels, exclusivity, precedence—can be expressed in linear form and integrated.
  • Scalability with solvers: Modern solvers routinely handle dozens of facilities and thousands of customers, even with complex constraints.

Challenges

  • Computational difficulty: Large instances (e.g., 1000 potential facilities, 10,000 customers) may still require hours of solver time. Heuristics or decomposition may be necessary.
  • Data quality: Models are only as good as input data—cost estimates, demand forecasts, capacity assumptions. Sensitivity analysis is essential.
  • Model simplifications: Real‑world operational details (e.g., time windows, inventory policies, nonlinear costs) are often linearized or omitted, which may limit solution realism.
  • Implementation gap: An optimal solution on paper must be accepted by managers and fit into existing workflows. It requires clear visualization and explanation.

Conclusion

Integer programming is the gold standard for solving facility location problems when discrete decisions matter. By framing the location–allocation trade‑off as a mathematical optimization model, organizations can make data‑driven decisions that reduce costs and improve service. From basic uncapacitated models to stochastic and robust variants, the flexibility of IP matches the complexity of real‑world siting. Advances in commercial solvers and modeling languages have made these techniques accessible even to non‑specialists. To learn more about the underlying theory, the INFORMS tutorial on facility location provides an excellent starting point. Whether you are optimizing a single warehouse or a global network, integer programming offers the rigorous framework needed to turn location‑planning challenges into measurable advantages.