TSP subtour elimination with DFJ vs MTZ

  • 3 November 2019
  • 2 replies
  • 577 views

Hi dear community,

 

I have a general question regarding the subtour elimination method of DFJ vs MTZ. The “CVRP” example on AIMMS website uses both methods to elinimate subtour and the result shows MTZ is faster than DFJ. However in the example, the MTZ is run together with the model while the DFJ is only used in the callback. So my question is, do we always run MTZ together with the model or it will actually give a better computation time if we use MTZ in callback just like DFJ?

 

And actually in my current project, I’m trying to get a storage assignment solution (400 items to 400 locations) with the minimum total travel distance for the pickers picking multiple batches. Each batch will include at most 5 items. So for this problem, say if we have 1000 batches, it will be 1000 TSP problems among at most 5 locations. So in this case, will there be any huge difference for me to use DFJ vs MTZ since the n is actually relatively small in each batch? 

 

Thanks in advance!


2 replies

Another question, when I tested my model with 12 items to 12 locations with 5 batches of 3-5 items, the AIMMS is possible to solve it within 5 sec with subtours. But once I run the MTZ subtour elimination together with the model, the solving time suddenly jumped to ~850s.

And if I add another batch with 5 items, the AIMMS still could solve it ~6s without MTZ. However, once I added the MTZ to run it together with the model, a solution was given after ~3 hours by CPLEX terminating the iteration itself (maybe out of memory), with 11.43% gap with best bounds. 

 

It doesn’t really make sense to me why there is such a huge difference just by adding the MTZ...I’m not sure whether it’s because I messed up something with my model or it’s just something gonna happen...could anyone also help to explain?  I’ll be glad to provide my project if anyone could help to check.

 

Thanks!

Hi @lin86 

Were you able to figure out a solution by yourself? Or do you still need some assistance?

 

Reply


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

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