I'm working on a linear programming project currently and I've run into some problems. The main idea of the project is to look at a section of a city and, using the schools that already exist in the area, determine the best location for a new school to be built.
I've defined 'best' as being the place that would make the maximum distance between any location to its closest school the smallest.
Each intersection is treated as a node which would hold a value of 0 if there will not be a school in that location and 1 if there will be a school in that location. I have a distance matrix where entry i,j gives the shortest path between intersection i and intersection j.
My model makes sense to me but I get problems when taking the maximum of the set of minimums, at which point all of my non-x decision variables become zero. The inner minimums seem to work correctly.
I was hoping someone who has experience with these kind of nested max/mins could shed some light on the situation.
I am implementing this in R using the lpSolve package if it matters.
I don't have the reputation to attach an image, but here is a link to my full formulation of the problem:
Notice that nothing in your model prevents $y_i=0$ for all $i$. I would recommend omitting $y_i$ and instead introducing a new binary decision variable $z_{i,j}$ that indicates whether location $i$ is served by a school at location $j$, together with constraints \begin{align} \sum_j z_{i,j} &=1 &&\text{for all $i$}\\ z_{i,j}&\le x_j &&\text{for all $i$ and $j$}\\ D&\ge d_{i,j}z_{i,j} &&\text{for all $i$ and $j$} \end{align} By the way, this variant of the facility location problem is called the $p$-center problem, where $p$ is the total number of facilities to open.
An alternative approach if the solver struggles with this formulation is to instead perform a bisection search on the set of distances. The optimal $D$ is the smallest value among these such that the constraints $\sum_{j: d_{i,j}\le D} x_j\ge 1$ for all $i$ can be satisfied.