Skip to content
Tutorials Center
My learning

Topics

Lesson 36 of 38 ยท Projects and Practice

Project: Facility Location

Build a capacitated facility location model end to end: decide which warehouses to open and who they serve, solve with a MILP, verify by brute force, and run what-if scenarios.

In this project you will plan a small distribution network. A company has six possible warehouse sites and twenty customers. Opening a warehouse costs a fixed amount per year; shipping goods costs money per unit and distance; each warehouse has limited capacity. Which warehouses should open, and which warehouse should serve which customer?

This is the capacitated facility location problem (CFLP), one of the most important models in supply-chain design. It combines ideas from this chapter: binary decisions (Binary Variables and Logic), strong linking constraints (Cutting Planes and Formulation Strength), assignment and transportation structure (The Transportation Problem) and branch and bound (Branch and Bound).

Step 1: Understand the problem

Data:

  • F candidate sites with fixed yearly cost f_i and capacity u_i.
  • C customers with demand d_j and location.
  • Shipping cost per unit from site i to customer j: t_ij, here half the Euclidean distance.

Decisions:

  • y_i binary: is site i open?
  • x_ij in [0, 1]: the share of customer j's demand served from site i (allowing a customer to be split between sites).

Step 2: Write the model

TEXT
minimize    sum_i f_i y_i + sum_i sum_j t_ij d_j x_ij
subject to  sum_i x_ij = 1                       for each customer j     (all demand met)
            sum_j d_j x_ij <= u_i y_i            for each site i         (capacity, only if open)
            x_ij <= y_i                          for all i, j            (strong linking)
            x_ij in [0, 1],  y_i in {0, 1}

The capacity constraint already forces x_ij = 0 when y_i = 0, but the extra x_ij <= y_i rows make the LP relaxation much stronger, as the formulation lesson showed. If customers must be served by a single site (single-sourcing), make x_ij binary too.

flowchart LR
    Y["y_i : open site i?"] --> C1["capacity<br/>sum d_j x_ij <= u_i y_i"]
    Y --> C2["linking<br/>x_ij <= y_i"]
    X["x_ij : share of j served by i"] --> C1
    X --> C2
    X --> D["demand<br/>sum_i x_ij = 1"]
    Y --> O["cost = fixed + shipping"]
    X --> O

Step 3: Build and solve

The code generates a reproducible instance with a fixed random seed, builds the constraint matrix, solves with milp, and then verifies the answer in an independent way: for every subset of sites, solve the (easy) assignment LP and keep the best total. That brute-force check works because there are only 2^6 subsets. Always validate a new model against something simpler.

Python Capacitated facility location: model and brute-force check

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Both approaches give the same cost, which validates the model. Because the total demand (496) exceeds one site's capacity (300), the solver must open at least two sites, and it opens three: the extra fixed cost buys shorter shipping distances.

Step 4: Analyze scenarios

Models are used to ask "what if". Here are two scenarios: (1) fixed costs rising or falling (new leases, tax changes), and (2) losing a site (the lease on the best site is not renewed). For (2) you force y_i = 0 by setting its upper bound to 0.

Python What-if analysis: fixed costs and a closed site

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

You should see the network shrink from three sites to two as fixed costs grow (fewer, fuller warehouses), and a measurable penalty when one of the current sites is removed. This kind of table is what decision makers actually read.

Step 5: Extend the model

Ideas to try (each is a small change):

  1. Single sourcing. Make x_ij binary: each customer is served by exactly one warehouse. The MILP becomes harder; compare solve times.
  2. Minimum throughput. Require sum_j d_j x_ij >= L y_i so no warehouse opens for a trickle of demand.
  3. Service radius. Forbid x_ij when dist_ij > R (delete the variable or set its bound to 0). Infeasibility means the radius is too small.
  4. Cardinality limit. At most k warehouses: sum y_i <= k.
  5. Multi-period or two-echelon networks. Add plants and a second shipping stage with flow balance at warehouses; you are back in network flow territory.
  6. Robustness. Evaluate your chosen sites under demand scenarios. A good plan is not only cheapest for the forecast but also resilient.

What you practiced

  • Translating a business question into binary and continuous variables.
  • Strong linking constraints and capacity constraints.
  • Validating a MILP with an independent brute-force computation.
  • Scenario analysis, the real value of an optimization model.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Why are both the capacity constraint and x_ij <= y_i included?

    Both are valid; the disaggregated linking rows tighten the relaxation so branch and bound needs fewer nodes.
  2. 2. What does making x_ij binary model?

    With x_ij in {0, 1} and sum_i x_ij = 1, each customer picks one warehouse.
  3. 3. How was the MILP result validated in this project?

    With only 2^6 subsets, enumerating them and solving an easy LP for each gives an independent optimum.
  4. 4. How do you force site 3 to be closed in a what-if scenario?

    Fixing y_3 = 0 via its bounds removes the site; the capacity constraint then forbids shipments from it.

Summary

  • Facility location combines binary open/close decisions with continuous shipments and capacity limits.
  • Strong linking constraints x_ij <= y_i tighten the relaxation.
  • Validate every model against a simpler independent method on a small instance.
  • What-if analysis (fixed-cost changes, closed sites) turns the model into a decision tool.
  • Extensions such as single sourcing, minimum throughput and service radii are small edits to the same model.

Next: Project: Staff Rostering