Travelling Salesman Lazy Constraint

回答済み

Hans Worst

2019年12月19日 21:11

• 
• 
• 

Hi,

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!

1

• 正式なコメント

  

  Simranjit Kaur

  • Gurobi Staff

  2025年06月23日 03:19 編集済み

  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?.
• 

  Eli Towle

  • Gurobi Staff

  2019年12月20日 19:56

  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
• 

  Hans Worst

  2019年12月22日 09:16 編集済み

  • 
  • 
  • 

  Hi Eli,

  Thank you very much for all your help, it works!!!

  Kind regards,

  Hans

  0

投稿コメントは受け付けていません。