A new integer programming formulation of the graphical traveling salesman problem

• 成果类型: Article
• 署名作者: Carr, Robert; Ravi, R.; Simonetti, Neil
• 署名单位: University of New Mexico; Carnegie Mellon University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-022-01849-w
• 发表日期: 2023
• 页码: 877-902
• 关键词: shortest complete cycle

摘要

In the Traveling Salesman Problem (TSP), a salesman wants to visit a set of cities and return home. There is a cost c(ij) of traveling from city i to city j, which is the same in either direction for the Symmetric TSP. The objective is to visit each city exactly once, minimizing total travel costs. In the Graphical TSP, a city may be visited more than once, which may be necessary on a sparse graph. We present a new integer programming formulation for the Graphical TSP requiring only two classes of polynomial-sized constraints while addressing an open question proposed by Denis Naddef. We generalize one of these classes, and present promising preliminary computational results.