•  Gurobi Staff

Here is one another idea. Let $$I$$ be the set of cities, and let $$C_i$$ be the set of cities that are not "close enough" to city $$i \in I$$. If city $$i \in I$$ is in the group, all cities that are not close enough to city $$i$$ should not be in the group. Mathematically:

\begin{align*}\sum_{j \in C_i} x_j \leq |C_i| \cdot (1 - x_i) \qquad \forall i \in I.\end{align*}

If $$x_i$$ equals $$1$$, then $$x_j$$ equals $$0$$ for all $$j \in C_i$$. If $$x_i$$ equals $$0$$, the constraint does not restrict $$x_j$$ for any $$j \in C_i$$.

The constraints you described are the disaggregated version of this formulation:

\begin{align*}x_j \leq 1 - x_i \qquad \forall i \in I,\ j \in C_i.\end{align*}

I recommend testing both formulations to see which performs better. The root relaxation bound of your disaggregated formulation should be at least as good as that of the aggregated formulation, but at the cost of potentially introducing many more constraints into the model.

•   Thank you very much for the idea! And sorry for very late reply.