A relax and cut approach using the multi-commodity flow formulation for the traveling salesman problem

Abstract

En este artículo nosotros exploramos una formulación de flujo multiproductos para el Problema del Agente Viajero Asimétrico (ATSP) en la obtención de cotas duales de este problema. El procedimiento empleado es una variante del método relax and cut propuesto en la literatura que computa los multiplicadores lagrangianos asociados a las restricciones de eliminación de subrutas preservando la optimalidad de los multiplicadores asociados a las restricciones de asignación. Los resultados obtenidos con la experimentación computacional son alentadores y muestran que el algoritmo propuesto genera buenas cotas duales con un tiempo de ejecución bajo.