2020/12/22 by Samuel C. Gutekunst, David P. Williamson, Gutekunst, Samuel C. +1 · 1 citation
Engineering · #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Number Theory (math.NT) #Optimization and Control (math.OC) #Vehicle Routing Optimization Methods
paper · pdf · doi:10.48550/arxiv.2012.12363
openalex publication_date 2020/12/22 · openalex created_date 2022/07/25 · openalex updated_date 2026/08/01
Facet-defining inequalities of the symmetric Traveling Salesman Problem (TSP) polytope play a prominent role in both polyhedral TSP research and state-of-the-art TSP solvers. In this paper, we introduce a new class of facet-defining inequalities, the circlet inequalities. These inequalities were first conjectured in Gutekunst and Williamson \citeGut19b when studying Circulant TSP, and they provide a bridge between polyhedral TSP research and number-theoretic investigations of Hamiltonian cycles stemming from a conjecture due to Marco Buratti in 2017. The circlet inequalities exhibit circulant symmetry by placing the same weight on all edges of a given length; our main proof exploits this symmetry to prove the validity of the circlet inequalities. We then show that the circlet inequalities are facet-defining and compute their strength following Goemans \citeGoe95b; they achieve the same worst-case strength as the similarly circulant crown inequalities of Naddef and Rinaldi \citeNad92, but are generally stronger.