Antecedentes
El problema del vendedor ambulante (TSP) solicita el circuito más corto que visita una determinada colección de ciudades. A los fines de esta pregunta, las ciudades serán puntos en el plano y las distancias entre ellas serán las distancias euclidianas habituales (redondeadas al número entero más cercano). El circuito debe ser de "ida y vuelta", lo que significa que debe regresar a la ciudad inicial.
El solucionador Concorde TSP puede resolver casos del problema del vendedor ambulante euclidiano, exactamente y mucho más rápido de lo que cabría esperar. Por ejemplo, Concorde pudo resolver una instancia de 85,900 puntos exactamente, partes de las cuales se ven así:
Sin embargo, algunas instancias de TSP tardan demasiado, incluso para Concorde. Por ejemplo, nadie ha podido resolver esta instancia de 100,000 puntos basada en la Mona Lisa . (¡Se puede ofrecer un premio de $ 1,000 si puede resolverlo!)
Concorde está disponible para descargar como código fuente o como ejecutable. Por defecto, utiliza el solucionador de programas lineal (LP) incorporado QSopt , pero también puede utilizar mejores solucionadores de LP como CPLEX.
El reto
¿Cuál es la instancia de TSP más pequeña que puede generar que le tome a Concorde más de cinco minutos para resolver?
Puede escribir un programa para generar la instancia o utilizar cualquier otro método que desee.
Puntuación
Cuantos menos puntos en la instancia, mejor. Los empates se romperán por el tamaño del archivo de la instancia (ver más abajo).
Estandarización
Las diferentes computadoras funcionan más rápido o más lento, por lo que utilizaremos el servidor NEOS para Concorde como el estándar de medición para el tiempo de ejecución. Puede enviar una lista de puntos en el siguiente formulario de coordenadas 2D simple:
#cities
x_0 y_0
x_1 y_1
.
.
.
x_n-1 y_n-1
Las configuraciones que se deben usar en NEOS son "Datos de Concorde (archivo de lista xy, norma L2)", "Algoritmo: Concorde (QSopt)" y "Semilla aleatoria: fija".
Base
La instancia rl1889.tsp
de 1,889 puntos de TSPLIB toma "Tiempo total de ejecución: 871.18 (segundos)", que es más de cinco minutos. Se parece a esto:
Respuestas:
88 ciudades, 341 segundos de tiempo de ejecución en NEOS
En un artículo reciente construimos una familia de instancias de TSP euclidianas difíciles de resolver. Puede descargar las instancias de esta familia, así como el código para generarlas aquí:
http://www.or.uni-bonn.de/%7Ehougardy/HardTSPInstances.html
La instancia de 88 ciudades de esta familia lleva a Concorde en el servidor NEOS más de 5 minutos. La instancia de 178 ciudades de esta familia lleva ya más de un día en resolverse.
fuente
77 ciudades, 7.24 minutos (434.4 segundos) de tiempo de ejecución promedio en NEOS
Llego un poco tarde a la fiesta, pero me gustaría contribuir con una instancia de 77 nodos, weruSnowflake77.
Creé esta instancia mientras intentaba comprender qué características locales y globales imponen una presión al alza sobre la cantidad de tiempo que concorde toma para igualar su mejor límite inferior con la duración de su recorrido más corto encontrado.
Para construir esta instancia, comencé con un gráfico base (13 x 13 cuadrados), y luego introduje sistemáticamente nuevos puntos o puntos viejos traducidos, conservando los ajustes que parecían hacer que el concorde se adentrara más en sus ramas en promedio antes de cortar.
La técnica es similar a la forma en que un algoritmo genético muta los recorridos existentes y retiene recorridos más cortos para la próxima generación de mutaciones, excepto que el gráfico en sí está siendo mutado y se retienen los gráficos más difíciles de resolver. También es similar a la forma en que mutamos gráficos usando relajaciones para ayudar a construir buenos límites inferiores, excepto que voy en sentido contrario, mutando un gráfico existente para construir un gráfico con límites inferiores difíciles de encontrar.
En el proceso, he encontrado algunos gráficos más pequeños que tardan minutos en resolver, pero este es el primer gráfico pequeño que he encontrado que toma un mínimo de 5 minutos.
Con 10 ejecuciones de prueba en NEOS utilizando la semilla fija y QSopt, el tiempo de ejecución promedio fue de 7.24 minutos (434.531 segundos). El tiempo de ejecución mínimo fue de 5,6 minutos (336,64 segundos). El tiempo de ejecución máximo fue de 8,6 minutos (515,80 segundos). No se descartaron ensayos. Tabla de referencia completa a continuación:
Resultados de referencia en más de 10 carreras:
weruSnowflake77 (lista xy, norma L2):
Repositorio
Problema de archivos del repositorio:
fuente
Python 3, 911 ciudades, 1418 segundos de tiempo de ejecución en NEOS
El siguiente script Python 3.x genera las coordenadas de 911 ciudades. A NEOS le tomó 1418 segundos calcular la ruta más corta de 47739.
Aquí hay una foto de ti camino más corto (gracias a A. Rex):
El código / algoritmo se basa en la bifurcación de Feigenbaum , que utilicé para generar una serie de valores, que utilicé como base para generar las coordenadas de las ciudades. Experimenté con los parámetros hasta que encontré varias ciudades por debajo de 1000 que le tomaron a NEOS una cantidad sorprendente de tiempo (muy por encima de los 5 minutos requeridos).
PD: Tengo un script ejecutándose en busca de un menor número de ciudades que también toman> 5 minutos en NEOS. Los publicaré en esta respuesta si encuentro alguno.
PD: ¡Maldita sea! Ejecutar este script con l parámetro 1811 en lugar de 1301 da como resultado 1156 ciudades con un tiempo de ejecución en NEOS de poco más de 4 horas , que es mucho más que otros casos con parámetros similares ...
fuente