IDEAS home Printed from https://ideas.repec.org/a/inm/ormoor/v48y2023i1p393-418.html
   My bibliography  Save this article

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

Author

Listed:
  • 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)

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.

Suggested Citation

  • Samuel C. Gutekunst & David P. Williamson, 2023. "The Circlet Inequalities: A New, Circulant-Based, Facet-Defining Inequality for the TSP," Mathematics of Operations Research, INFORMS, vol. 48(1), pages 393-418, February.
    • Handle: RePEc:inm:ormoor:v:48:y:2023:i:1:p:393-418
    DOI: 10.1287/moor.2022.1265
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/moor.2022.1265
    Download Restriction: no
    File URL: https://libkey.io/10.1287/moor.2022.1265?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:ormoor:v:48:y:2023:i:1:p:393-418. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    We have no bibliographic references for this item. You can help adding them by using this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.