🔢 mathematics

A Surface-Based Formulation of the Traveling Salesman Problem

Este artículo presenta una formulación exacta del problema del viajante de comercio basada en la construcción de una superficie de triángulos conectados que utiliza restricciones de árbol y características de Euler para garantizar la conectividad global y local, eliminando la necesidad de eliminar subrutas tradicionales.

Autores originales: Yılmaz Arslanoğlu

Publicado 2026-03-03

📖 4 min de lectura🧠 Análisis profundo

CC BY 4.0

Autores originales: Yılmaz Arslanoğlu

Artículo original bajo licencia CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta es una explicación generada por IA del artículo a continuación. No ha sido escrita ni avalada por los autores. Para mayor precisión técnica, consulte el artículo original. Leer descargo de responsabilidad completo

¡Claro que sí! Imagina que este artículo es como un nuevo manual de instrucciones para resolver el famoso Problema del Viajante de Comercio (TSP).

¿Qué es el problema original?

Imagina que eres un repartidor que debe visitar 50 ciudades diferentes y volver a casa, pasando por cada una solo una vez, pero quieres recorrer la menor distancia posible.

La forma clásica de resolver esto es como si estuvieras conectando puntos con líneas (carreteras). El ordenador prueba millones de combinaciones de líneas para ver cuál forma el mejor círculo. El problema es que, a veces, el ordenador se pierde creando "bucles pequeños" (como visitar solo 3 ciudades y volver) en lugar de un gran círculo que cubra todo. Para evitar esto, tiene que usar reglas matemáticas muy complejas y lentas.

La nueva idea: Construir una "Manta" en lugar de un "Cable"

El autor de este artículo, Yılmaz Arslanoğlu, dice: "¿Y si en lugar de dibujar líneas, construimos una superficie?".

En lugar de pensar en carreteras, piensa en triángulos de tela.

La analogía de la manta: Imagina que tienes un montón de triángulos de tela de diferentes tamaños. Tu objetivo es elegir un grupo de estos triángulos y coserlos entre sí para formar una manta continua (una superficie).
El borde es el camino: Cuando coses los triángulos, el borde exterior de esa manta es tu ruta. Si la manta está bien hecha (es una sola pieza sin agujeros ni nudos extraños), su borde será automáticamente un camino perfecto que pasa por todas las ciudades una sola vez.

¿Cómo funciona la magia? (Los 3 trucos)

El autor propone un sistema con tres reglas simples para asegurar que la "manta" sea perfecta:

La Regla de la "Unidad" (Conexión Global):
Imagina que los triángulos son personas en una fiesta. La regla dice: "Todos los triángulos seleccionados deben estar conectados entre sí, como si fueran una sola familia". No puedes tener un grupo de triángulos aquí y otro grupo aislado allá. Esto asegura que tu manta sea una sola pieza continua.
La Regla del "Tejido Sano" (Regularidad):
En una manta bien hecha, dos piezas de tela se unen por un borde, pero no tres o cuatro. El sistema prohíbe que más de dos triángulos compartan la misma línea de costura. Esto evita que la manta se deforme o se rompa en puntos extraños.
La Regla del "Nudo Perfecto" (Filtro de Euler):
Esta es la parte más inteligente. Imagina que cada ciudad es un punto donde se juntan varios triángulos. La regla dice: "Alrededor de cada ciudad, los triángulos deben formar un círculo perfecto, sin agujeros ni cruces raros".
- Si los triángulos forman un círculo alrededor de la ciudad, ¡genial! Significa que el camino pasa por ahí sin problemas.
- Si forman una forma extraña (como un lazo o un "bowtie"), el sistema lo descarta automáticamente.

¿Por qué es mejor que lo anterior?

El viejo método: Es como intentar adivinar qué líneas dibujar. A veces el ordenador se atasca pensando en bucles pequeños.
El nuevo método: Es como construir una manta. Si la manta está bien construida (es una sola pieza y no tiene agujeros), el borde ya es la solución correcta por sí solo. No necesitas buscar el camino; el camino es simplemente el borde de tu creación.

¿Funciona en la vida real?

El autor prueba esto con dos enfoques:

El enfoque "Todo lo que existe": Si usas todos los triángulos posibles, la solución es matemáticamente perfecta (exacta), pero es tan lenta que solo funciona para ciudades muy pocas (como 10 o 20). Es como intentar coser una manta con todos los retales del mundo: perfecto, pero imposible de terminar.
El enfoque "Inteligente" (Heurística): En la práctica, el autor usa solo los triángulos más lógicos (como los que se forman naturalmente en un mapa, llamados "triangulación de Delaunay").
- Resultado: ¡Funciona increíblemente rápido! En pruebas con ciudades reales (como Berlín con 52 ciudades), el nuevo método resolvió el problema casi al instante, mientras que los métodos antiguos tardaban mucho más o necesitaban miles de intentos.

En resumen

Este artículo cambia la perspectiva:

Antes: "¿Qué carreteras elijo para hacer un círculo?"
Ahora: "¿Qué triángulos coso para hacer una manta bonita?"

Al construir la manta (la superficie) correctamente, el camino (el borde) se forma solo. Es una forma más elegante y, a menudo, más rápida de resolver el rompecabezas del viajante, especialmente cuando se usa con mapas geométricos inteligentes.

La moraleja: A veces, para encontrar el camino más corto, no debes mirar el camino, sino construir el terreno por el que camina.

Resumen Técnico: Formulación Basada en Superficies del Problema del Viajante de Comercio (TSP)

Autor: Yılmaz Arslanoğlu (Investigador Independiente, Hamburgo, Alemania)
Fecha: Febrero 2026 (Prepublicación en arXiv)

1. El Problema y el Cambio de Paradigma

El Problema del Viajante de Comercio (TSP) se modela tradicionalmente como la selección de un conjunto de aristas $E' \subseteq E$ en un grafo $G=(V, E)$ para formar un ciclo hamiltoniano de peso mínimo. Los modelos existentes (como MTZ o restricciones de eliminación de subciclos) se centran en la topología 1-dimensional (ciclos).

Este artículo propone un cambio de perspectiva fundamental: en lugar de construir el tour como una secuencia de aristas, se construye una superficie 2-dimensional (un complejo simplicial) cuyo borde es exactamente el ciclo hamiltoniano. El objetivo es seleccionar un conjunto conectado de triángulos que minimice la longitud total de las aristas de su frontera.

2. Metodología y Formulación Matemática

2.1. Grafo de Incidencia Bipartito

La base combinatoria es un grafo bipartito $B = (U \cup W, A)$ :

Nodos de Triángulo ( $U$ ): Representan un conjunto candidato de triángulos $T \subseteq \binom{V}{3}$ .
Nodos de Arista ( $W$ ): Representan las aristas primales del grafo original.
Arcos ( $A$ ): Conectan un triángulo con una arista si la arista pertenece al triángulo.

2.2. Cancelación de Frontera y Peso Neto

La función objetivo se basa en un concepto de "cancelación de frontera":

Se asigna un costo a cada nodo de arista ( $c(e) = 2L_e$ , donde $L_e$ es la longitud).
Se asigna una ganancia a cada incidencia triángulo-arista ( $p(t, e) = L_e$ ).
Mecanismo: Si una arista es compartida por dos triángulos seleccionados, las ganancias de las incidencias cancelan exactamente el costo de la arista. Si una arista es parte de la frontera (solo un triángulo adyacente), su costo neto es $L_e$ .
Resultado: Minimizar el peso neto de la subgrafos activa es equivalente a minimizar la longitud del tour de frontera.

2.3. Restricciones Estructurales (MILP)

Para garantizar que la superficie seleccionada sea válida y su borde sea un único ciclo hamiltoniano, se imponen cuatro tipos de restricciones:

Conectividad Global (Árbol): La subgrafos activa en el grafo de incidencia debe formar un árbol conectado. Esto asegura que la superficie resultante sea simplemente conexa (topológicamente un disco).
Cardinalidad: Se fija el número de triángulos seleccionados a $N-2$ y el número de aristas a $2N-3$ (propiedades de una triangulación de un disco con $N$ vértices).
Regularidad de Variedad: Cada arista primal puede ser incidente a, como máximo, dos triángulos (evita solapamientos no manifiestos).
Filtro de Euler Local: Para evitar singularidades locales (como vértices tipo "lazo" o "bowtie") y asegurar que la vecindad de cada ciudad sea un camino simple, se impone que la característica de Euler local $\chi(H_v) = |V| - |E| = 1$ para cada vértice $v$ .

3. Contribuciones Clave

Equivalencia Topológica: Establece una equivalencia entre encontrar el ciclo hamiltoniano de peso mínimo en el complejo completo y encontrar un árbol dual de peso máximo en el grafo de incidencia bipartito.
Formulación MILP Exacta: Presenta un modelo de Programación Lineal Entera Mixta (MILP) que reemplaza las complejas restricciones de eliminación de subciclos por una restricción de árbol global más un filtro de Euler local.
Desacoplamiento de Entrada: El modelo es agnóstico al conjunto de triángulos candidatos $T$ . Funciona tanto con el conjunto universal (todos los triángulos posibles, garantizando optimalidad exacta pero costoso computacionalmente) como con triangulaciones geométricas dispersas (como Delaunay o Greedy), actuando como una heurística potente.

4. Resultados Computacionales y Validación

Los experimentos se realizaron utilizando el solucionador HiGHS en instancias de TSPLIB y casos sintéticos.

Comparación con Baselines (MTZ): En instancias euclidianas con entradas dispersas (triangulación de Delaunay), el modelo basado en superficies supera significativamente a la formulación estándar "Lifted-MTZ".
- Ejemplo (St70): El modelo Surface-Based-Flow resolvió en 0.20s con 1 nodo de ramificación (B&B), mientras que Lifted-MTZ requirió 14.23s y 2,936 nodos.
- Ejemplo (Pcb442): Surface-Based-Flow resolvió en 81.1s (142 nodos), mientras que Surface-Based-MTZ tardó 1656s (23,205 nodos) y falló en 3 de 10 ejecuciones.
Robustez Topológica: El modelo funciona correctamente incluso en espacios no métricos (donde no se cumple la desigualdad triangular), ya que depende puramente de la conectividad topológica y no de las propiedades métricas de las distancias.
Impacto de la Calidad de la Entrada:
- En el caso "Tnm199" (difícil), el uso de una triangulación "Greedy" en lugar de "Delaunay" redujo la brecha de optimalidad del 6.17% al 1.85%, superando al algoritmo de Christofides (5.69%).
- Limitación: En geometrías degeneradas (puntos en líneas paralelas), las triangulaciones dispersas pueden fallar catastróficamente (brechas de hasta 119%), mostrando que la calidad del conjunto candidato es crítica.

5. Significado e Implicaciones

Nueva Perspectiva: Introduce una conexión profunda entre la optimización combinatoria y la topología computacional, tratando el TSP como un problema de minimización de frontera de una superficie.
Eficiencia en Relajaciones: La restricción de árbol global (especialmente cuando se implementa mediante flujo de un solo commodity) proporciona relajaciones más fuertes que las restricciones de ordenamiento tipo MTZ, reduciendo drásticamente el tamaño del árbol de búsqueda.
Potencial Futuro: Aunque la formulación exacta (con todos los triángulos) es intratable para instancias grandes, el enfoque basado en superficies ofrece una base sólida para integrar restricciones geométricas o topológicas adicionales que serían difíciles de modelar en formulaciones basadas en aristas primales.

En conclusión, este trabajo demuestra que cambiar el espacio de decisión de "aristas" a "triángulos/superficies" puede ofrecer ventajas significativas en la eficiencia de los solucionadores MILP para instancias geométricas, siempre que se utilice un conjunto candidato de triángulos de alta calidad.