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):
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!
Please sign in to leave a comment.