Abstract This paper presents a novel formulation for the Traveling Salesman Problem (TSP), utilizing a binary list data-structure allocating cities to its leaves to form sequentially the tour of the problem. The structure allows the elimination of subtours from the formulation and at the same time reducing the number of binary variables to ${\cal O}(N\log_{2}N)$. The expense is the increase in the constraint set cardinality measuring at ${\cal O}(N^{2}\log_{2}N)$, and in the introduction of at most ${\cal O}(N^{2}\log_{2}N)$ continuous variables. The value of the proposed original formulation is that for the first time a minimal number of binary degrees of freedom is recognized for the TSP. Although computationally the resulting TSP formulation is not competitive, this work presents a new methodology of structuring the information describing the problem which may lead to future developments exploiting it. The scheme is equivalent to binary expansion of tour-locations which may be applicable to other standard TSP formulations, thus allowing there also the same reduction in the number of binary variables.
Citation
Department of Chemical Engineering and Biotechnology, University of Cambridge, Pembroke Street, Cambridge CB2 3RA, UK. Manuscript first version produced: 20 May 2012
Article
View Traveling Salesman Problem Formulations with log N$ Number of Binary Variables