Optimization Online


Lower bounding procedure for the Asymmetric Quadratic Traveling Salesman Problem

Borzou Rostami(brostami***at***mathematik.tu-dortmund.de)
Federico Malucelli(federico.malucelli***at***polimi.it)
Pietro Belotti(pietrobelotti***at***fico.com)
Stefano Gualandi(stefano.gualandi***at***gmail.com)

Abstract: In this paper we consider the Asymmetric Quadratic Traveling Salesman Problem. Given a directed graph and a function that maps every pair of consecutive arcs to a cost, the problem consists in finding a cycle that visits every vertex exactly once and such that the sum of the costs is minimum. We propose an extended Linear Programming formulation that has a variable for each cycle in the graph. Since the number of cycles is exponential in the graph size, we propose a column generation approach. We compare the bounds resulting from this new formulation with those obtained by some linearization techniques for 0-1 quadratic optimization or specifically proposed for the QTSP. Computational results on some set of benchmarks used in the literature show that the column generation approach is very promising.

Keywords: Traveling salesman, Quadratic Traveling Salesman Problem, Column Generation, Lower bound, Cycle cover

Category 1: Combinatorial Optimization

Category 2: Nonlinear Optimization (Quadratic Programming )

Category 3: Integer Programming ((Mixed) Integer Linear Programming )


Download: [PDF]

Entry Submitted: 02/04/2015
Entry Accepted: 02/07/2015
Entry Last Modified: 02/04/2015

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