Euler characteristic

A Surface-Based Formulation of the Traveling Salesman Problem

  • Yılmaz Arslanoğlu
    • Categories (Mixed) Integer Linear Programming, Other Topics Tags , , , ,

    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 … Read more

    A Structural Equivalence of Symmetric TSP to a Constrained Group Steiner Tree Problem

  • Yılmaz Arslanoğlu
    • Categories (Mixed) Integer Linear Programming, Approximation Algorithms Tags , , , ,

    We present a brief structural equivalence between the symmetric TSP and a constrained Group Steiner Tree Problem (cGSTP) defined on a simplicial incidence graph. Given the complete weighted graph on the city set V, we form the bipartite incidence graph between triangles and edges. Selecting an admissible, disk-like set of triangles induces a unique boundary … Read more