  


Traveling Salesman Problem Formulations with $N \log N$ Number of Binary Variables
Thomas A. Pogiatzis(tp309cam.ac.uk) Abstract: Abstract This paper presents a novel formulation for the Traveling Salesman Problem (TSP), utilizing a binary list datastructure 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 tourlocations 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 integerlinear 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/2013 Modify/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  