The School Location Problem

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” 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.