K-Median constraints - FLP Linear Programming

Question

I'm attempting to solve a problem using linear programming. I have been using this resource (k-median problem midway down the page) as a reference.

I have successfully implemented a first attempt using Python and the PuLP library, however as I develop the model I would like to understand the meaning of the constraints more clearly.

I have provided screenshots of the problem described on the page linked above, with annotations of my understanding of each constraint.

Image 1: Problem description
Image 2: Problem constraints with my understanding

Could anyone tell me what the purpose of the final constraint is? My understanding of the formula is that the sum of customers being served by a single site can only be ≤ 1, and therefore each site can only serve at most one customer - but that's clearly not the case.

Any help would be appreciated. Thanks

Answer 1

I think the linked page has some text missing, as well as a typo in the constraint. I suspect that before the last constraint, the intended text was something like the following:

As an alternative formulation, you can replace the $x_{ij} \le y_j$ constraints with the aggregated constraints $\sum_{i=1}^n x_{ij} \le n y_j$.

Note the $n$ coefficient.

Although this aggregated formulation does yield a weaker formulation, state-of-the-art solvers will generate the stronger constraints dynamically as needed.

Answer 2

The last constraint (which probably has a typo) is not necessary, it is redundant with respect to

\begin{align} x_{ij}&\le y_j \quad &(1) \\ \sum_{j}x_{ij}&=1 \quad &(2) \end{align}

You can remove it. It might have an impact on computation times.