A Surface-Based Formulation of the Traveling Salesman Problem
We present an exact formulation of the symmetric Traveling Salesman Problem (TSP) that replaces the classical edge-selection view with a surface-building approach. Instead of selecting edges to form a cycle, the model selects a set of connected triangles where the boundary of the resulting surface forms the tour. This method yields a mixed-integer linear programming (MILP) formulation where a tree constraint enforces global connectivity, while local connectivity at each vertex is guaranteed via Euler characteristic constraints, replacing the need for subtour elimination. The formulation is…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2603.00075
curl -X POST /api/v1/records/arxiv/2603.00075/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2603.00075/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'