La combinatoria poliédrica y el problema del viajante. Aplicación al caso de ciento tres ciudades españolas.

Título inglés	Polyhedral combinatorics and the travelling salesman problem: application to the case of hundred and three Spanish towns.
Título español	La combinatoria poliédrica y el problema del viajante. Aplicación al caso de ciento tres ciudades españolas.
Autor/es	Alvarez Valdés, Ramón ; Corberán Salvador, Angel ; Tamarit Goerlich, José Manuel
Organización	Dep. Estad. Invest. Oper. Fac. Mat. Univ. Valencia, Valencia, España
Revista	0210-8054
Publicación	1985, 9 (3): 199-213, 16 Ref.
Tipo de documento	articulo
Idioma	Español
Resumen español	El trabajo resume los resultados de la aplicación de la Combinatoria Poliédrica al Problema del Viajante (TSP): definición del poliedro, dimensión, desigualdades válidas, facetas. Estos resultados se aplican al caso concreto de encontrar el circuito para el TSP de coste mínimo que recorre ciento tres ciudades españolas. Se trata de un proceso interactivo en el que, para cada solución de la relajación lineal del problema, obtenida mediante la aplicación de un código comercial de Programación lineal, se identifican las restricciones violadas y se incorporan manualmente al problema relajado en la iteración siguiente. En nuestro caso, la séptima resolución del problema lineal, al que se habían incorporado 68 nuevas restricciones, proporcionó la solución óptima.
Clasificación UNESCO	120709
Palabras clave español	Programación lineal ; Problemas combinatorios ; Problema del viajante ; Algoritmos ; Corte
Código MathReviews	MR0891854
Acceso al artículo completo