A carregar...
Publicação
New Bounds for Asymmetric Travelling Salesman Problem
Autores
Orientador(es)
Resumo(s)
Recently new Lagrangean techniques for producing lower bounds have appeared in the literature: bound improvement sequences and Lagrangean decomposition. The combination of these approaches yields the Improved Lagrangean decomposition. In this work we will apply this combined approach to the Asymmetric Travelling Salesman Problem. The results obtained using the Improved Lagrangean decomposition on the r-Arborescence formulation of the (ATSP) show that these new bounds often bridge the duality gap without needing valid inequalities or Branch&Bound techniques. We also present an extended version of the subgradient method developed to speed up the computation of the bounds aforementioned. Computational experience is reported.
Descrição
Palavras-chave
Integer programming Duality gap Lagrangean relaxation Bound improvement sequences Lagrangean decomposition Integrality property X-Convexity Subgradient method
Contexto Educativo
Citação
Barros, A. I. and Bárcia, P., New Bounds for Asymmetric Travelling Salesman Problem (October, 1990). FEUNL Working Paper Series No. 158