Is there an easier way to solve this problem in Gurobi?
Answered
Hi,
I am looking into the following problem, and I am wondering whether there is an easy way to solve this in Gurobi (which has so many nice features).
Suppose we have 4 cities that need to be combined in a group. For example, each city could have an associated saving, and the objective is to maximize the total saving in a group. Then a solution, say x^t=(1,1,0,1) would mean that cities 1,2 and 4 should be in a group.
But suppose there is the distance constraint - the distance between any two cities in a group cannot be larger than, say, 10 km. Suppose we have a distance matrix which shows the distance between the city in the row and the city in the column (symmetric):
D=
0 15 9 20
15 0 8 5
9 8 0 12
20 5 12 0
So, here cities 1 and 2 cannot be together in a group since the distance is larger than 10. But for example 1 and 3 can be in a group because the distance is less than 10. One way to solve this would be to include all pairs of cities that cannot be combined. Here this would be:
1 and 3 is not allowed
1 and 4 is not allowed
3 and 4 is not allowed
Then the constraints would be:
(1 0 1 0) * x <1
(1 0 0 1) * x <1
(0 0 1 1) * x <1
But then if the problem becomes bigger, there is a very large number of constraints that should be added. Is there an easier way to put a constraint of max-distance? I am using Python. Thanks in advance!
-
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.
1 -
Thank you very much for the idea! And sorry for very late reply.
0
Please sign in to leave a comment.
Comments
2 comments