Optimization Online


Traveling Salesman Problem Formulations with $N \log N$ Number of Binary Variables

Thomas A. Pogiatzis(tp309***at***cam.ac.uk)
Vassilios S. Vassiliadis(vsv20***at***cam.ac.uk)
Raul Conejeros(rconejer***at***ucv.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/2013
Entry Accepted: 02/13/2013
Entry Last Modified: 02/13/2013

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society