IDEAS home Printed from https://ideas.repec.org/a/inm/orijoc/v34y2022i4p1970-1986.html
   My bibliography  Save this article

Exact Solution Algorithms for the Chordless Cycle Problem

Author

Listed:
  • Dilson Lucas Pereira

    (Departamento de Computação Aplicada, Universidade Federal de Lavras, Lavras, Caixa 3037, CEP 37200-900, Brazil)

  • Abilio Lucena

    (Programa de Engenharia de Sistemas e Computação, Universidade Federal do Rio de Janeiro, Rio de Janeiro, Caixa 68511, CEP 21941-972, Brazil)

  • Alexandre Salles da Cunha

    (Departamento de Ciência da Computação, Universidade Federal de Minas Gerais, Belo Horizonte, CEP 31270-901 Brazil)

  • Luidi Simonetti

    (Programa de Engenharia de Sistemas e Computação, Universidade Federal do Rio de Janeiro, Rio de Janeiro, Caixa 68511, CEP 21941-972, Brazil)

Abstract

A formulation, a heuristic, and branch-and-cut algorithms are investigated for the chordless cycle problem. This is the problem of finding a largest simple cycle for a given graph so that no edge between nonimmediately subsequent cycle vertices is contained in the graph. Leaving aside procedures based on complete enumeration, no previous exact solution algorithm appears to exist for the problem, which is relevant both in theoretical and practical terms. Extensive computational results are reported here for randomly generated graphs and for graphs originating from the literature. Under acceptable CPU times, certified optimal solutions are presented for graphs with as many as 100 vertices. Summary of Contribution: Finding chordless cycles of a graph, also known as holes, is relevant, among others, to graph theory, to the design of polyhedral based exact solution algorithms to integer programming (IP) problems, and to the practical applications that benefit from these algorithms. For instance, perfect graphs do not contain odd holes. Additionally, odd hole inequalities are valid for strengthening the formulations to numerous problems that are directly defined over graphs. Furthermore, these inequalites, in association with applicable conflict graphs, are used by all modern IP solvers to preprocess and strengthen virtually any IP formulation submitted to them.

Suggested Citation

  • Dilson Lucas Pereira & Abilio Lucena & Alexandre Salles da Cunha & Luidi Simonetti, 2022. "Exact Solution Algorithms for the Chordless Cycle Problem," INFORMS Journal on Computing, INFORMS, vol. 34(4), pages 1970-1986, July.
    • Handle: RePEc:inm:orijoc:v:34:y:2022:i:4:p:1970-1986
    DOI: 10.1287/ijoc.2022.1164
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/ijoc.2022.1164
    Download Restriction: no
    File URL: https://libkey.io/10.1287/ijoc.2022.1164?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
    ---><---

    References listed on IDEAS

    as
    1. Betül Ahat & T?naz Ekim & Z. Caner Taşkın, 2018. "Integer Programming Formulations and Benders Decomposition for the Maximum Induced Matching Problem," INFORMS Journal on Computing, INFORMS, vol. 30(1), pages 43-56, February.
    2. Petra Bauer, 1997. "The Circuit Polytope: Facets," Mathematics of Operations Research, INFORMS, vol. 22(1), pages 110-145, February.
    3. Park, Kyungchul & Lee, Kyungsik & Park, Sungsoo, 1996. "An extended formulation approach to the edge-weighted maximal clique problem," European Journal of Operational Research, Elsevier, vol. 95(3), pages 671-682, December.
    4. Atamturk, Alper & Nemhauser, George L. & Savelsbergh, Martin W. P., 2000. "Conflict graphs in solving integer programming problems," European Journal of Operational Research, Elsevier, vol. 121(1), pages 40-55, February.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Seyedmohammadhossein Hosseinian & Dalila B. M. M. Fontes & Sergiy Butenko, 2020. "A Lagrangian Bound on the Clique Number and an Exact Algorithm for the Maximum Edge Weight Clique Problem," INFORMS Journal on Computing, INFORMS, vol. 32(3), pages 747-762, July.
    2. Wei-Kun Chen & Liang Chen & Mu-Ming Yang & Yu-Hong Dai, 2018. "Generalized coefficient strengthening cuts for mixed integer programming," Journal of Global Optimization, Springer, vol. 70(1), pages 289-306, January.
    3. Macambira, Elder Magalhaes & de Souza, Cid Carvalho, 2000. "The edge-weighted clique problem: Valid inequalities, facets and polyhedral computations," European Journal of Operational Research, Elsevier, vol. 123(2), pages 346-371, June.
    4. Avella, Pasquale & D'Auria, Bernardo & Salerno, Saverio, 2006. "A LP-based heuristic for a time-constrained routing problem," European Journal of Operational Research, Elsevier, vol. 173(1), pages 120-124, August.
    5. Müller, R.J. & Gui, H. & Vohra, R., 2004. "Dominant strategy mechanisms with multidimensional types," Research Memorandum 046, Maastricht University, Maastricht Research School of Economics of Technology and Organization (METEOR).
    6. Carvalho, Filipa D. & Almeida, M. Teresa, 2011. "Upper bounds and heuristics for the 2-club problem," European Journal of Operational Research, Elsevier, vol. 210(3), pages 489-494, May.
    7. Kobeaga, Gorka & Rojas-Delgado, Jairo & Merino, María & Lozano, Jose A., 2024. "A revisited branch-and-cut algorithm for large-scale orienteering problems," European Journal of Operational Research, Elsevier, vol. 313(1), pages 44-68.
    8. Zwaneveld, P. & Verweij, G. & van Hoesel, S., 2018. "Safe dike heights at minimal costs: An integer programming approach," European Journal of Operational Research, Elsevier, vol. 270(1), pages 294-301.
    9. Sorensen, Michael M., 2004. "New facets and a branch-and-cut algorithm for the weighted clique problem," European Journal of Operational Research, Elsevier, vol. 154(1), pages 57-70, April.
    10. J Renaud & F F Boctor & G Laporte, 2004. "Efficient heuristics for Median Cycle Problems," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 55(2), pages 179-186, February.
    11. Álvaro Porras & Concepción Domínguez & Juan Miguel Morales & Salvador Pineda, 2023. "Tight and Compact Sample Average Approximation for Joint Chance-Constrained Problems with Applications to Optimal Power Flow," INFORMS Journal on Computing, INFORMS, vol. 35(6), pages 1454-1469, November.
    12. J. Paul Brooks & Eva K. Lee, 2014. "Solving a Multigroup Mixed-Integer Programming-Based Constrained Discrimination Model," INFORMS Journal on Computing, INFORMS, vol. 26(3), pages 567-585, August.
    13. Dominique Feillet & Pierre Dejax & Michel Gendreau, 2005. "Traveling Salesman Problems with Profits," Transportation Science, INFORMS, vol. 39(2), pages 188-205, May.
    14. Hunting, Marcel & Faigle, Ulrich & Kern, Walter, 2001. "A Lagrangian relaxation approach to the edge-weighted clique problem," European Journal of Operational Research, Elsevier, vol. 131(1), pages 119-131, May.
    15. San Segundo, Pablo & Coniglio, Stefano & Furini, Fabio & Ljubić, Ivana, 2019. "A new branch-and-bound algorithm for the maximum edge-weighted clique problem," European Journal of Operational Research, Elsevier, vol. 278(1), pages 76-90.
    16. W. David Pisinger & Anders Bo Rasmussen & Rune Sandvik, 2007. "Solution of Large Quadratic Knapsack Problems Through Aggressive Reduction," INFORMS Journal on Computing, INFORMS, vol. 19(2), pages 280-290, May.
    17. Wei, Ningji & Walteros, Jose L., 2022. "Integer programming methods for solving binary interdiction games," European Journal of Operational Research, Elsevier, vol. 302(2), pages 456-469.
    18. Lourenco, Lidia Lampreia & Pato, Margarida Vaz, 2007. "The effect of strengthened linear formulations on improving the lower bounds for the part families with precedence constraints problem," European Journal of Operational Research, Elsevier, vol. 183(1), pages 181-196, November.
    19. Glaydston Mattos Ribeiro & Miguel Fragoso Constantino & Luiz Antonio Nogueira Lorena, 2010. "Strong formulation for the spot 5 daily photograph scheduling problem," Journal of Combinatorial Optimization, Springer, vol. 20(4), pages 385-398, November.
    20. Perraudat, Antoine & Dauzère-Pérès, Stéphane & Vialletelle, Philippe, 2022. "Robust tactical qualification decisions in flexible manufacturing systems," Omega, Elsevier, vol. 106(C).

    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:orijoc:v:34:y:2022:i:4:p:1970-1986. 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.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with 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.