A Surface-Based Formulation of the Traveling Salesman Problem

1. Problem Statement

The paper addresses the Symmetric Traveling Salesman Problem (TSP), which seeks the minimum-weight Hamiltonian cycle in a graph $G=(V, E)$.

• Traditional Approach: Conventional models view TSP as a 1-dimensional edge-selection problem. They select a subset of edges to form a cycle, requiring complex constraints (like subtour elimination) to ensure global connectivity and prevent disjoint cycles.
• The Challenge: While compact formulations (e.g., MTZ) exist, they often suffer from weak relaxations. Stronger formulations (e.g., Branch-and-Cut with subtour elimination) are computationally expensive due to exponential constraint sets.
• The Proposed Shift: The author proposes a paradigm shift from selecting edges to constructing a 2-dimensional surface. The goal is to select a connected set of triangles such that the boundary of this surface forms the optimal Hamiltonian tour.

2. Methodology

The core methodology relies on computational topology and mixed-integer linear programming (MILP).

A. The Incidence Graph Structure

Instead of a standard graph, the model constructs a bipartite triangle–edge incidence graph $B = (U \cup W, A)$:

• Triangle Nodes ($U$): Represent candidate triangles ($t \in \mathcal{T}$).
• Edge Nodes ($W$): Represent primal edges ($e \in E$).
• Arcs ($A$): Connect a triangle node to an edge node if the edge is part of the triangle.

B. Objective Function: Boundary Cancellation

The objective is to minimize the total length of the induced boundary. This is achieved through a "net weight" formulation:

• Cost: Each selected edge node $e$ incurs a cost of $2L_e$ (where $L_e$ is the edge length).
• Profit: Each selected incidence $(t, e)$ (triangle $t$ containing edge $e$) yields a profit of $L_e$.
• Mechanism:
  • Internal Edges: Shared by two selected triangles. They incur $2L_e$ cost but generate $2 \times L_e$ profit (one for each triangle), resulting in a net cost of 0.
  • Boundary Edges: Shared by only one selected triangle. They incur $2L_e$ cost but generate only $1 \times L_e$ profit, resulting in a net cost of $L_e$.
• Result: Minimizing the net weight is mathematically equivalent to minimizing the length of the boundary tour.

C. Topological Constraints

To ensure the selected triangles form a valid surface whose boundary is a single Hamiltonian cycle, the model enforces four structural constraints:

1. Global Tree Connectivity: The selected subgraph in the incidence graph must form a single connected tree. This ensures the surface is simply connected (topologically a disk).
2. Cardinality Constraints:
   • Number of triangles: $N - 2$.
   • Number of edges: $2N - 3$.
   • These counts are derived from the Euler characteristic for a triangulated disk.
3. Manifold Regularity: Every primal edge is incident to at most two triangles (preventing non-manifold edges).
4. Local Connectivity (Euler Filter): To prevent singularities (e.g., "bowtie" vertices where the surface pinches), the local Euler characteristic $\chi(H_v)$ for the neighborhood of every vertex $v$ is enforced to be 1. This ensures the local neighborhood forms a simple path.

D. Input Flexibility

The formulation is input-decoupled. It treats the set of candidate triangles $\mathcal{T}$ as a black box:

• Exact Mode: If $\mathcal{T}$ is the set of all possible triangles ($K_{All}$), the formulation is exact.
• Heuristic Mode: If $\mathcal{T}$ is a sparse set (e.g., Delaunay or Greedy triangulation), the model acts as a powerful heuristic.

3. Key Contributions

1. Topological Equivalence: Establishes an equivalence between finding a min-weight Hamiltonian cycle in the complete complex and finding a max-weight dual tree in the bipartite incidence graph.
2. Novel MILP Formulation: Replaces traditional subtour elimination constraints with a combination of a global tree constraint and local Euler characteristic filters.
3. Decoupled Framework: Demonstrates a formulation that works identically on dense (all triangles) and sparse (geometric triangulations) inputs, allowing for flexible trade-offs between exactness and computational tractability.
4. Planar Simplification: For planar triangulations (like Delaunay), the model can be simplified by removing explicit edge nodes, collapsing the bipartite graph into a standard dual graph, significantly reducing variable counts.

4. Computational Results

The author validated the model using the HiGHS solver on various TSPLIB instances and synthetic data.

• Small Instances (N ≤ 130):
  • The Surface-Based-Flow model (using single-commodity flow for connectivity) solved instances like berlin52, st70, and ch130 at the root node (0 branch-and-bound nodes) when using Delaunay triangulation.
  • In contrast, the standard Lifted-MTZ baseline required thousands of nodes (e.g., 16,058 nodes for ch130).
• Large Instances (N = 280 to 657):
  • For A280, the Surface-Based-Flow model solved in 5.68s, while Lifted-MTZ failed to solve within the time limit.
  • For pcb442, the Surface-Based-Flow model solved in 81.1s with only 142 nodes, whereas the MTZ variant struggled significantly.
• Non-Metric Spaces: The model successfully solved random non-metric instances (where triangle inequality is violated), proving its reliance is purely topological, not geometric.
• Hard/Degenerate Instances:
  • Tnm199: Using a Greedy triangulation (richer candidate set) reduced the optimality gap to 1.85%, outperforming both Delaunay (6.17%) and the Christofides heuristic (5.69%).
  • p100 (Parallel Lines): The model highlighted a limitation: on degenerate geometries where sparse triangulations fail to capture the optimal path, the gap widened significantly (up to 119% for Greedy), indicating that the quality of the candidate set $\mathcal{T}$ is critical.

5. Significance and Conclusion

• Theoretical Impact: The paper provides a rigorous topological alternative to graph-theoretic TSP formulations, proving that enforcing surface admissibility (disk topology) is sufficient to guarantee a Hamiltonian cycle.
• Practical Utility: While the "all triangles" approach is computationally intractable for large $N$, the sparse candidate set approach (e.g., Delaunay) yields a highly effective heuristic. It offers significantly tighter relaxations and faster convergence than standard compact formulations (like MTZ) for Euclidean TSP instances.
• Future Directions: The formulation serves as a foundation for integrating complex geometric or topological constraints that are difficult to model in primal edge formulations, without altering the core model structure.

In summary, Arslanoğlu presents a surface-based MILP that transforms the TSP from an edge-selection problem into a surface-minimization problem. By leveraging topological constraints (Euler characteristic) and boundary cancellation, it achieves superior performance on sparse geometric inputs compared to traditional methods, offering a new perspective on solving one of the most famous problems in combinatorial optimization.