Linear facility location problem for large size problems (police station)

Question

Considering a set of $m$ existing weighted demand points (very large) and $n$ different-sized facilities, what is the best approach for locating new facilities to maximise coverage? I have used the Weber problem, which is non-linear (quadratic). I used the $\ell_p$-metric method to measure distance but it is not accurate. (For example, where to locate a new police station to cover the demand points, or which of the existing facilities can be shifted to maximize the coverage).

---

Update: I found a very similar model to what do I mean here. Sorry if my question was not clear. So put simply, referring to the provided link my main questions are as below:

1. How to solve such this model for large cases?
2. This model is nonlinear. How to linearize it?
3. What if there are already some facility established? How to locate the new facilities by considering them?

Answer 1

You may have a look at our recent work based on Benders decomposition, for the discrete Maximum Coverage Facility Location problem. It works very well if the number of facilities is relatively small, but the number of customers can run in millions…

J.F. Cordeau, F. Furini, I. Ljubic: Benders Decomposition for Very Large Scale Partial Set Covering and Maximal Covering Problems, European Journal of Operational Research 275(3):882-896, 2019

You can donwload the preprint from here.

The code is open-source.

Answer 2

It sounds like you are describing either the set covering location problem (SCLP) (Wikipedia entry; canonical citation) or the maximal coverage location problem (MCLP) (Wikipedia entry; canonical citation). The SCLP minimizes the number of facilities subject to a constraint that every demand node is covered; the MCLP maximizes the number of covered demands subject to a constraint on the number of facilities to be located.

Your question specifies weighted demand points, which suggests the MCLP to me, since the weights don't matter in the SCLP (you have to cover everyone). You also say different-sized facilities and I'm not sure what you mean by that. If you mean that the coverage radius is different for different facilities, that's an easy modification. If you mean that the facilities have capacities, and the capacity is different for each facility, that's harder. The SCLP and MCLP assume the facilities are uncapacitated. You could add capacity constraints, but depending on how you are solving the problem, it may add computational difficulties.

Standard MIP formulations of both the SCLP and MCLP usually have very tight LP relaxations, which means you can often just solve them with a commercial solver. Other good algorithms exist, for example using Lagrangian relaxation or metaheuristics.

I wrote a book chapter on covering problems a while back; maybe that will be useful.

To answer your main questions:

1. The SCLP and MCLP can be solved for large instances using off-the-shelf MIP solvers. By large, I mean 1000s of nodes, at least. If you need larger, you may have to look at specialized algorithms, e.g., the one mentioned in @IvanaLjubic’s answer. But if $m$ is large and $n$ is not, you can often reduce the size simply by aggregating the demand nodes, e.g., by postal code or some other grouping.

2. The SCLP and MCLP are linear. The p-center problem is also linear, although the variant of it in the answer you linked to happens to be nonlinear.

3. Easy, just set their fixed cost to 0, either in the objective function of the SCLP, or don’t include it in the LHS of the “open p facilities” constraint of the MCLP.