Skip to main content

Is there an easier way to solve this problem in Gurobi?




  • Eli Towle
    Gurobi Staff 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.

  • Aleksandrs Smilgins

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


Please sign in to leave a comment.