Solve the facility location problem in Python

Facility location — decide which facilities (warehouses, plants, servers, hubs) to open and how to route demand to them so the total of fixed opening costs plus service costs is smallest — is a workhorse MILP. The tricky part is the coupling: a facility may only serve demand if it is open. With quicopt it is a compact model in Python.

The naive approach

Enumerating every open/closed combination is 2^F facilities, and each choice still needs a shipping plan solved underneath. Greedily opening the cheapest facilities ignores capacity and distance. Model the two decisions together.

Model it as a MILP

Binary open[f] opens a facility; continuous ship[f][c] sends demand from f to customer c. Every customer is fully served, a facility can ship only up to its capacity and only if open (that single constraint encodes the coupling), and we minimize fixed + transport cost:

from ortools.math_opt.python import mathopt
from quicopt import Client
F, C = 4, 8
fixed_cost = [100.0, 120.0, 90.0, 150.0]
capacity   = [60.0, 80.0, 50.0, 100.0]
demand     = [10.0, 15.0, 8.0, 12.0, 20.0, 9.0, 14.0, 11.0]
trans = [[4.0 + ((f * 7 + c * 3) % 11) for c in range(C)] for f in range(F)]
model = mathopt.Model(name="facility_location")
y = [model.add_binary_variable(name=f"open_{f}") for f in range(F)]
x = [[model.add_variable(lb=0.0, name=f"ship_{f}_{c}") for c in range(C)] for f in range(F)]
for c in range(C):
    model.add_linear_constraint(sum(x[f][c] for f in range(F)) == demand[c])
for f in range(F):
    model.add_linear_constraint(sum(x[f][c] for c in range(C)) <= capacity[f] * y[f])
model.minimize(sum(fixed_cost[f]*y[f] for f in range(F))
               + sum(trans[f][c]*x[f][c] for f in range(F) for c in range(C)))
print(Client("https://try.quicoptapi.pgi.fz-juelich.de").solve(model).display)

├── status:     optimal
├── feasible:   true
├── objective:  863.0
├── x:          open_0=1, open_1=1, open_2=1, open_3=0, ship_0_0=10, ship_0_1=15, …  (36 variables)
└── solve_time: 0.0341 s

What you get

status: optimal means total cost 863 is proven best — open facilities 0, 1 and 2, leave the expensive facility 3 closed, and ship as the ship_f_c values show. The coupling constraint guarantees no closed facility ever ships, so the open/serve trade-off is solved as one problem, not two.

The same 36-variable shape extends to more facilities and customers, and k-median or capacity variants are small edits. This compact model uses an aggregated capacity coupling; on large networks a tighter (disaggregated) coupling formulation solves faster — you change the data, not the method.

Next

• The problem class behind this: Mixed-integer linear (MILP)
• A runnable model for every supported class: Examples
• Set up the client and solve your first model: Getting started

Reference: M. L. Balinski, Integer Programming: Methods, Uses, Computation, Management Science, 1965.