Travelling Salesman Lazy Constraint
AnsweredHi,
I am work on a travelling salesman problem and I want to solve this by lazy constraints. This gurobi example (http://examples.gurobi.com/traveling-salesman-problem/) is very useful, but not exactly what I want. In this example they find the shortest subtour after a run and add a lazy constraint for that subtour. However, I want that after every run, all subtours of that run are added as a lazy constraint. Does anybody know how the change the example script in such a way that this is possible?
Thank you very much in advance!
-
Official comment
-
Gurobi Staff
This post is more than three years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum. Or why not try our AI Gurobot?. -
-
-
Hi Hans,
First, we modify the subtour function to return the full list of cycles, not just the shortest cycle. That is, we change
return cycles[lengths.index(min(lengths))]
to
return cycles
Then, in the subtourelim callback function, we simply add a for loop to generate a lazy constraint for every cycle:
for tour in subtour(selected):
if len(tour) < n:
# add a subtour elimination constraint
expr = 0
for i in range(len(tour)):
for j in range(i+1, len(tour)):
expr += model._vars[tour[i], tour[j]]
model.cbLazy(expr <= len(tour)-1)The last step would be to change the final assertion to instead verify that the subtour function returns a list containing a single cycle of length n:
assert len(subtour(selected)) == 1 and len(subtour(selected)[0]) == n
I hope this helps. Thanks!
Eli
0 -
-
Hi Eli,
Thank you very much for all your help, it works!!!
Kind regards,
Hans
0 -
Post is closed for comments.
Comments
3 comments