I’ve spent a few days thinking about a facility location problem that we might call the school location problem. The goal is to place \(n\) schools to serve \(m\) families, such that the furthest distance between any family and their nearest school is minimized. This problem is almost a \(k\)-means or ellipsoid fitting problem, but its unusual “minimin” form makes it computationally challenging.

In the video below, and associated Jupyter notebook (GitHub, HTML viewer), I discuss the formulation of this problem, show to express it as a mixed-integer second-order convex program, and then solve a small instance using the Julia/JuMP/Juniper/SCS stack.

Here’s the video link.