IDEAS home Printed from https://ideas.repec.org/a/spr/joptap/v197y2023i2d10.1007_s10957-023-02195-3.html
   My bibliography  Save this article

A New Global Algorithm for Max-Cut Problem with Chordal Sparsity

Author

Listed:
  • Cheng Lu

    (North China Electric Power University)

  • Zhibin Deng

    (University of Chinese Academy of Sciences; MOE Social Science Laboratory of Digital Economic Forecasts and Policy Simulation at UCAS)

  • Shu-Cherng Fang

    (North Carolina State University)

  • Wenxun Xing

    (Tsinghua University)

Abstract

In this paper, we develop a semidefinite relaxation-based branch-and-bound algorithm that exploits the chordal sparsity patterns of the max-cut problem. We first study how the chordal sparsity pattern affects the hardness of a max-cut problem. To do this, we derive a polyhedral relaxation based on the clique decomposition of the chordal sparsity patterns and prove some sufficient conditions for the tightness of this polyhedral relaxation. The theoretical results show that the max-cut problem is easy to solve when the sparsity pattern embedded in the problem has a small treewidth and the number of vertices in the intersection of maximal cliques is small. Based on the theoretical results, we propose a new branching rule called hierarchy branching rule, which utilizes the tree decomposition of the sparsity patterns. We also analyze how the proposed branching rule affects the chordal sparsity patterns embedded in the problem, and explain why it can be effective. The numerical experiments show that the proposed algorithm is superior to those known algorithms using classical branching rules and the state-of-the-art solver BiqCrunch on most instances with sparsity patterns arisen in practical applications.

Suggested Citation

  • Cheng Lu & Zhibin Deng & Shu-Cherng Fang & Wenxun Xing, 2023. "A New Global Algorithm for Max-Cut Problem with Chordal Sparsity," Journal of Optimization Theory and Applications, Springer, vol. 197(2), pages 608-638, May.
    • Handle: RePEc:spr:joptap:v:197:y:2023:i:2:d:10.1007_s10957-023-02195-3
    DOI: 10.1007/s10957-023-02195-3
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10957-023-02195-3
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10957-023-02195-3?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
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Iain Dunning & Swati Gupta & John Silberholz, 2018. "What Works Best When? A Systematic Evaluation of Heuristics for Max-Cut and QUBO," INFORMS Journal on Computing, INFORMS, vol. 30(3), pages 608-624, August.
    2. Rafael Martí & Abraham Duarte & Manuel Laguna, 2009. "Advanced Scatter Search for the Max-Cut Problem," INFORMS Journal on Computing, INFORMS, vol. 21(1), pages 26-38, February.
    3. Florian Jarre & Felix Lieder & Ya-Feng Liu & Cheng Lu, 2020. "Set-completely-positive representations and cuts for the max-cut polytope and the unit modulus lifting," Journal of Global Optimization, Springer, vol. 76(4), pages 913-932, April.
    4. Michael Garstka & Mark Cannon & Paul Goulart, 2021. "COSMO: A Conic Operator Splitting Method for Convex Conic Problems," Journal of Optimization Theory and Applications, Springer, vol. 190(3), pages 779-810, September.
    5. Jie Wang & Victor Magron, 2022. "Exploiting Sparsity in Complex Polynomial Optimization," Journal of Optimization Theory and Applications, Springer, vol. 192(1), pages 335-359, January.
    6. Jamie Fairbrother & Adam N. Letchford & Keith Briggs, 2018. "A two-level graph partitioning problem arising in mobile wireless communications," Computational Optimization and Applications, Springer, vol. 69(3), pages 653-676, April.
    7. Francisco Barahona & Martin Grötschel & Ali Ridha Mahjoub, 1985. "Facets of the Bipartite Subgraph Polytope," Mathematics of Operations Research, INFORMS, vol. 10(2), pages 340-358, May.
    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. Cheng Lu & Zhibin Deng, 2021. "A branch-and-bound algorithm for solving max-k-cut problem," Journal of Global Optimization, Springer, vol. 81(2), pages 367-389, October.
    2. Lu, Yongliang & Benlic, Una & Wu, Qinghua, 2018. "A memetic algorithm for the Orienteering Problem with Mandatory Visits and Exclusionary Constraints," European Journal of Operational Research, Elsevier, vol. 268(1), pages 54-69.
    3. Aardal, K. & van Hoesel, C.P.M., 1995. "Polyhedral techniques in combinatorial optimization," Research Memorandum 014, Maastricht University, Maastricht Research School of Economics of Technology and Organization (METEOR).
    4. Nikitas Rontsis & Paul Goulart & Yuji Nakatsukasa, 2022. "Efficient Semidefinite Programming with Approximate ADMM," Journal of Optimization Theory and Applications, Springer, vol. 192(1), pages 292-320, January.
    5. Fred Glover & Gary Kochenberger & Rick Hennig & Yu Du, 2022. "Quantum bridge analytics I: a tutorial on formulating and using QUBO models," Annals of Operations Research, Springer, vol. 314(1), pages 141-183, July.
    6. Wenxing Zhu & Geng Lin & M. M. Ali, 2013. "Max- k -Cut by the Discrete Dynamic Convexized Method," INFORMS Journal on Computing, INFORMS, vol. 25(1), pages 27-40, February.
    7. A. D. López-Sánchez & J. Sánchez-Oro & M. Laguna, 2021. "A New Scatter Search Design for Multiobjective Combinatorial Optimization with an Application to Facility Location," INFORMS Journal on Computing, INFORMS, vol. 33(2), pages 629-642, May.
    8. F. Rendl, 2016. "Semidefinite relaxations for partitioning, assignment and ordering problems," Annals of Operations Research, Springer, vol. 240(1), pages 119-140, May.
    9. Vilmar Jefté Rodrigues de Sousa & Miguel F. Anjos & Sébastien Le Digabel, 2019. "Improving the linear relaxation of maximum k-cut with semidefinite-based constraints," EURO Journal on Computational Optimization, Springer;EURO - The Association of European Operational Research Societies, vol. 7(2), pages 123-151, June.
    10. Fuda Ma & Jin-Kao Hao, 2017. "A multiple search operator heuristic for the max-k-cut problem," Annals of Operations Research, Springer, vol. 248(1), pages 365-403, January.
    11. Wang, Yang & Lü, Zhipeng & Glover, Fred & Hao, Jin-Kao, 2012. "Path relinking for unconstrained binary quadratic programming," European Journal of Operational Research, Elsevier, vol. 223(3), pages 595-604.
    12. Iain Dunning & Swati Gupta & John Silberholz, 2018. "What Works Best When? A Systematic Evaluation of Heuristics for Max-Cut and QUBO," INFORMS Journal on Computing, INFORMS, vol. 30(3), pages 608-624, August.
    13. Aardal, K.I. & van Hoesel, S., 1995. "Polyhedral Techniques in Combinatorial Optimization," Other publications TiSEM ed028a07-eb6a-4c8d-8f21-d, Tilburg University, School of Economics and Management.
    14. Qinghua Wu & Yang Wang & Fred Glover, 2020. "Advanced Tabu Search Algorithms for Bipartite Boolean Quadratic Programs Guided by Strategic Oscillation and Path Relinking," INFORMS Journal on Computing, INFORMS, vol. 32(1), pages 74-89, January.
    15. Ricardo N. Liang & Eduardo A. J. Anacleto & Cláudio N. Meneses, 2022. "Data structures for speeding up Tabu Search when solving sparse quadratic unconstrained binary optimization problems," Journal of Heuristics, Springer, vol. 28(4), pages 433-479, August.
    16. Jesús Sánchez-Oro & Manuel Laguna & Rafael Martí & Abraham Duarte, 2016. "Scatter search for the bandpass problem," Journal of Global Optimization, Springer, vol. 66(4), pages 769-790, December.
    17. Timotej Hrga & Janez Povh, 2021. "MADAM: a parallel exact solver for max-cut based on semidefinite programming and ADMM," Computational Optimization and Applications, Springer, vol. 80(2), pages 347-375, November.
    18. Theja Tulabandhula & Deeksha Sinha & Saketh Reddy Karra & Prasoon Patidar, 2020. "Multi-Purchase Behavior: Modeling, Estimation and Optimization," Papers 2006.08055, arXiv.org, revised Aug 2023.

    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:spr:joptap:v:197:y:2023:i:2:d:10.1007_s10957-023-02195-3. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.