A Surface-Based Formulation of the Traveling Salesman Problem

Resumo Técnico: Uma Formulação Baseada em Superfície para o Problema do Caixeiro Viajante (TSP)

1. O Problema

O Problema do Caixeiro Viajante (TSP) é classicamente modelado como a seleção de um conjunto de arestas em um grafo $G=(V, E)$ para formar um ciclo hamiltoniano de peso mínimo. As formulações exatas tradicionais (como Branch-and-Cut) dependem de restrições de eliminação de sub-tours, que são exponenciais em número, ou de formulações compactas (como MTZ ou baseadas em fluxo) que, embora menores, podem ter relaxações mais fracas.

O artigo propõe uma mudança de paradigma fundamental: em vez de construir o tour como uma sequência 1-dimensional de arestas, o modelo constrói uma superfície 2-dimensional (um complexo simplicial) cujas bordas formam o ciclo hamiltoniano. O objetivo é selecionar um conjunto conectado de triângulos tal que a fronteira resultante minimize o comprimento total.

2. Metodologia

A abordagem baseia-se em topologia combinatória e teoria dos grafos bipartidos.

• Grafo de Incidência Bipartido:
  O autor define um grafo bipartido $B = (U \cup W, A)$, onde:

  • $U$: Nós de triângulos (candidatos).
  • $W$: Nós de arestas primais (arestas do grafo original).
  • $A$: Arestas de incidência conectando um triângulo às suas três arestas constituintes.

• Cancelamento de Fronteira (Objetivo):
  A função objetivo é formulada para maximizar o "peso líquido" da sub-estrutura ativa. Atribui-se um custo às arestas primais e um lucro às incidências triângulo-aresta.

  • Arestas internas (compartilhadas por dois triângulos selecionados) têm seus custos cancelados pelos lucros das incidências.
  • Arestas de fronteira (pertencentes a apenas um triângulo) contribuem com seu comprimento total.
  • Assim, minimizar o comprimento da fronteira é equivalente a maximizar o peso líquido do subgrafo ativo.

• Restrições de Topologia (MILP):
  Para garantir que a superfície selecionada seja um disco topológico válido (cuja fronteira seja um único ciclo hamiltoniano), o modelo impõe quatro restrições estruturais:

  1. Conectividade Global (Árvore): O subgrafo ativo no grafo de incidência deve formar uma única árvore conectada. Isso garante que a superfície seja simplesmente conexa (topologicamente um disco).
  2. Cardinalidade: Restrições de contagem fixas para garantir que o complexo seja uma triangulação de um disco com $N$ vértices ($N-2$ triângulos e $2N-3$ arestas).
  3. Regularidade de Variedade (Manifold): Cada aresta primal deve ser incidente a no máximo dois triângulos (evitando arestas não-manifold).
  4. Filtro de Euler Local: Para evitar singularidades locais (como vértices em forma de "laço" ou bowties), a característica de Euler local de cada cidade $v$ no subgrafo de incidência deve ser igual a 1 ($\chi(H_v) = 1$). Isso garante que o entorno de cada vértice seja um caminho simples conectado.

• Abordagem Híbrida (Heurística vs. Exata):

  • Caso Exato: Se o conjunto de triângulos candidatos $T$ for o complexo completo ($K_{All}$), a formulação é exata, mas computacionalmente intratável para $N$ grande.
  • Caso Prático (Heurística): Ao restringir $T$ a uma triangulação esparsa (ex: Triangulação de Delaunay), o modelo torna-se um MILP compacto e eficiente, funcionando como uma heurística poderosa.

3. Contribuições Principais

1. Equivalência Topológica: Estabelece uma equivalência entre ciclos hamiltonianos de peso mínimo no complexo completo e árvores duais de peso máximo no grafo de incidência bipartido.
2. Formulação MILP sem Eliminação de Sub-tours: Substitui as complexas restrições de eliminação de sub-tours por uma combinação de restrição de árvore global e filtro de Euler local, garantindo a validade topológica do ciclo.
3. Desacoplamento de Entrada: A formulação trata o conjunto de triângulos candidatos como uma "caixa preta". Ela funciona igualmente bem no conjunto universal (exato) ou em triangulações esparsas (heurística), permitindo a integração de diferentes geometrias (Delaunay, Greedy, etc.).

4. Resultados Computacionais

Os experimentos foram realizados utilizando o solver HiGHS em instâncias do TSPLIB e casos degenerados.

• Desempenho em Instâncias Euclidianas (Delaunay):

  • Em instâncias como berlin52, st70 e ch130, o modelo baseado em superfície (com restrição de fluxo de árvore) resolveu os problemas na raiz da árvore de Branch-and-Bound (1 nó), enquanto a baseline Lifted-MTZ exigiu milhares de nós (ex: 16.058 nós para ch130).
  • O modelo baseado em fluxo superou consistentemente as versões baseadas em MTZ à medida que o tamanho da instância aumentava.

• Robustez em Espaços Não-Métricos:

  • O modelo foi validado em instâncias onde a desigualdade triangular não é satisfeita, demonstrando que a formulação depende apenas da conectividade topológica e não de propriedades métricas estritas.

• Análise de Instâncias Difíceis e Degeneradas:

  • Tnm199 (Instância Difícil): O uso de uma triangulação "Greedy" como entrada permitiu que o modelo encontrasse uma solução com gap de 1,85%, superando a triangulação de Delaunay (6,17%) e o heurístico de Christofides (5,69%).
  • p100 (Degeneração de Linhas Paralelas): O modelo mostrou vulnerabilidade quando a triangulação esparsa (Delaunay ou Greedy) falha em capturar a geometria correta em configurações degeneradas, resultando em gaps altos (até 119% para Greedy), destacando a dependência da qualidade do conjunto de candidatos esparsos.

5. Significado e Conclusão

A formulação baseada em superfície oferece uma nova perspectiva para o TSP, transformando um problema de otimização de ciclo 1D em um problema de otimização de superfície 2D.

• Vantagens: Gera relaxações mais fortes do que formulações compactas tradicionais (como MTZ) em entradas esparsas, reduzindo drasticamente o esforço de Branch-and-Bound.
• Limitações: A versão exata (com todos os triângulos) é computacionalmente inviável para grandes $N$. O desempenho prático depende criticamente da qualidade da triangulação esparsa de entrada; se a triangulação não contiver o tour ótimo, o modelo não conseguirá encontrá-lo.
• Impacto Futuro: O trabalho sugere que a abordagem topológica é uma base promissora para integrar restrições geométricas ou topológicas adicionais que seriam difíceis de modelar em formulações baseadas em arestas, abrindo caminho para novos híbridos entre topologia computacional e otimização combinatória.

Em suma, o artigo demonstra que "construir superfícies" em vez de "selecionar arestas" pode levar a formulações matemáticas mais robustas e eficientes para o TSP, especialmente quando combinado com triangulações geométricas inteligentes.