Solved

Subtour elimination in TSP

  • 30 October 2019
  • 3 replies
  • 263 views

Hi dear community,

 

I’m trying to add this subtour elimination constraint into my AIMMS project. 

 

sum( (k,l) | k<>l and k in SubsetofLocations and l in SubsetofLocations, y(b,k,l)) <= |SubsetofLocations| - 1

where y(b,k,l) = 1 indicating the picker will go from location k to location l while picking items in batch b. 

My questions are:

  1. How can I generate all of the subsets that are required to be used here? I checked the TSP example on AIMMS website and it seems like these subsets are generated automatically? If it’s not, how should I set it up?
  2. How can I get the number of locations in a subset(the |SubsetofLocations|) when it is generated everytime? 
  3. I want to add this as a lazy constraint with the callback function. But I’ve been quite lost about how to set it up. I know how to add it in the MainExecution (I just followed the TSP example) but I’m not quite sure about what else will I need. Should I just ignore the entire “Declaration Network” part(since I don’t need to show the routes) and copy the “CB_Lazy(ThisSession)” , “DetermineSubtours(ThisSession)”, “ResetCase” into my project? 

 I’m quite new to AIMMS so any help will be appreciated! 

icon

Best answer by Chris Kuip 31 October 2019, 14:01

Hello,

 

  1. All subsets of a given set can be created using a simple loop, as illustrated in the attached example. I assume you are aware that there are exponentially many subsets of a set. 
  2. You can use the card function, see AIMMS The Function Reference for details.
  3. Indeed, using a lazy constraint is the way to go. 
    The declaration section "declaration network“ is for display purposes only and can be ignored if you are interested in the algorithm itself.
    On the other hand, the CB_Lazy and DetermineSubtours procedures are essential to the algorithm.
View original

3 replies

Userlevel 3

Hello,

 

  1. All subsets of a given set can be created using a simple loop, as illustrated in the attached example. I assume you are aware that there are exponentially many subsets of a set. 
  2. You can use the card function, see AIMMS The Function Reference for details.
  3. Indeed, using a lazy constraint is the way to go. 
    The declaration section "declaration network“ is for display purposes only and can be ignored if you are interested in the algorithm itself.
    On the other hand, the CB_Lazy and DetermineSubtours procedures are essential to the algorithm.
Userlevel 4

Hi @lin86 , hope you were able to get familiar with Chris’ instructions, did it work out as expected?

Thanks for the helpful example @Chris Kuip! Now it starts to make sense of how this works...Though I believe I still need to dig it more before I really get it to work, your answer just makes it easier since I have the right direction now :) Thank you so much!

 

 

Reply


Didn't find what you were looking for? Try searching on our documentation pages:

AIMMS Developer & PRO | AIMMS How-To | AIMMS SC Navigator