Article ID: | iaor2007463 |
Country: | Netherlands |
Volume: | 3 |
Issue: | 1 |
Start Page Number: | 78 |
End Page Number: | 85 |
Publication Date: | Mar 2006 |
Journal: | Discrete Optimization |
Authors: | Orlin James B., Ergun zlem |
Keywords: | programming: dynamic, heuristics |
We consider the standard dynamic program to solve the TSP. We then obtain exponentially large neighborhoods by selecting a polynomially bounded number of states, and restricting the dynamic program to those states only. We show how the Balas and Simonetti neighborhood and the insertion dynasearch neighborhood can be viewed in this manner. We also show that one of the dynasearch neighborhoods can be derived directly from the 2-exchange neighborhood using this approach.