Symmetric traveling salesman problem and flows in hypergraphs: New algorithmic possibilities

Tiru S Arthanari


The traveling salesperson problem (TSP) is a very well-known NP-hard combinatorial optimization problem. Many different integer programming formulations are known for the TSP. Some of them are “compact”, in the sense of having a polynomially-bounded number of variables and constraints. We focus on one compact formulation for the symmetric TSP, known as the “multistage insertion” formulation [T. S. Arthanari, Discrete Mathematics 306, 1474 (2006)], and show that its linear programming (LP) relaxation can be viewed as a minimum-cost flow problem in a hypergraph. Using some ideas of R. Cambini, G. Gallo and M. G. Scutellà [University of Pisa, TR-1/92 (1992)] on flows in hypergraphs, we propose new algorithms to solve the LP relaxation. We also exploit the Leontief structure of a certain subproblem, to provide additional algorithms for solving the LP relaxation. Some bounds on the running time are also derived.


pedigree polytope, multistage insertion formulation, symmetric traveling salesman problem, minimum cost hypergraph flow problem, Leontief substitution flow problem, Lagrangean relaxation, Lagrangean decomposition

Full Text:



Copyright (c) 2019 Tiru S Arthanari

Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.