Generalized formulations for the traveling salesman problem.

Abstract:  The traveling salesman problem is a widely studied classical combinatorial problem for which there are several integer linear formulations. In this work, we consider the Miller-Tucker-Zemlin (MTZ) formulation. First, we argue that the choice of some parameters of this formulation is arbitrary and, therefore, there is a family of formulations of which MTZ is a particular case. We analyze this family, noting that in general the formulations involved are not comparable to each other and there is no one that dominates the rest. Then, we study the intersection of this family, which we show to be equivalent to the well-known Circuit Inequalities formulation. Finally, we extend this approach to the Desrochers-Laporte and Single-Commodity Flow formulations, obtaining similar results.

Posted on Nov 28, 2022 in ACGO, Seminars