Groupe d’études et de recherche en analyse des décisions

G-2002-73

A Bilevel Programming Approach to the Travelling Salesman Problem

, et

The Travelling Salesman Problem (TSP) is a well-researched problem whose interest lies well beyond the Icosian game or the Knight's tour puzzle. In this paper, we show that the TSP is polynomially reducible to the Toll Optimization Problem (TOP), a special instance of bilevel program. Based on natural bilevel programming techniques, we recover the lifted version of the Miller-Tucker-Zemlin constraints obtained by Desrochers and Laporte. Pursuing the analysis, we obtain an O(n2) multi-commodity extension whose LP relaxation upper bound is qualitatively comparable to the bound provided by the exponential formulation of Dantzig, Fulkerson and Johnson.

, 16 pages