- Traveling Salesman Problem Formulations with $N \log N$ Number of Binary Variables Thomas A. Pogiatzis(tp309cam.ac.uk) Vassilios S. Vassiliadis(vsv20cam.ac.uk) Raul Conejeros(rconejerucv.cl) Abstract: 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. Keywords: Keywords: Traveling Salesman Problem, mixed integer-linear programming, binary list, subtour elimination Category 1: Integer Programming ((Mixed) Integer Linear Programming ) Category 2: Applications -- OR and Management Sciences (Transportation ) Citation: Department of Chemical Engineering and Biotechnology, University of Cambridge, Pembroke Street, Cambridge CB2 3RA, UK. Manuscript first version produced: 20 May 2012 Download: [PDF]Entry Submitted: 02/13/2013Entry Accepted: 02/13/2013Entry Last Modified: 02/13/2013Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Optmization Society.