The Circlet Inequalities: A New, Circulant-Based, Facet-Defining Inequality for the TSP

Samuel C. Gutekunst () and David P. Williamson ()
Additional contact information
Samuel C. Gutekunst: Departments of Computer Science and of Mathematics, Bucknell University, Lewisburg, Pennsylvania 17837
David P. Williamson: School of Operations Research and Information Engineering, Cornell University, Ithaca, New York 14850

Mathematics of Operations Research, 2023, vol. 48, issue 1, 393-418

Abstract: 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 [Gutekunst SC, Williamson DP (2019) Characterizing the integrality gap of the subtour LP for the circulant traveling salesman problem. SIAM J. Discrete Math. 33(4):2452–2478] when studying the circulant TSP, and they provide a bridge between polyhedral TSP research and number-theoretic investigations of Hamiltonian cycles stemming from a conjecture from Marco Buratti in 2007. 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 [Goemans MX (1995) Worst-case comparison of valid inequalities for the TSP. Math. Programming 69:335–349]; they achieve the same worst case strength as the similarly circulant crown inequalities of Naddef and Rinaldi [Naddef D, Rinaldi G (1992) The crown inequalities for the symmetric traveling salesman polytope. Math. Oper. Res. 17(2):308–326] but are generally stronger.

Keywords: Primary: 90C27; secondary: 90C10; 05C45; 90C35; mathematics; combinatorics; sets; polyhedra; networks/graphs; traveling salesman; integer programming; algorithms; cutting plane/facet (search for similar items in EconPapers)
Date: 2023
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/moor.2022.1265 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:48:y:2023:i:1:p:393-418

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().