Odd-Cycle Separation for Maximum Cut and Binary Quadratic Optimization

Authors Michael Jünger, Sven Mallach



PDF
Thumbnail PDF

File

LIPIcs.ESA.2019.63.pdf
  • Filesize: 0.75 MB
  • 13 pages

Document Identifiers

Author Details

Michael Jünger
  • University of Cologne, Germany
Sven Mallach
  • University of Cologne, Germany

Cite AsGet BibTex

Michael Jünger and Sven Mallach. Odd-Cycle Separation for Maximum Cut and Binary Quadratic Optimization. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 63:1-63:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ESA.2019.63

Abstract

Solving the NP-hard Maximum Cut or Binary Quadratic Optimization Problem to optimality is important in many applications including Physics, Chemistry, Neuroscience, and Circuit Layout. The leading approaches based on linear/semidefinite programming require the separation of so-called odd-cycle inequalities for solving relaxations within their associated branch-and-cut frameworks. In their groundbreaking work, F. Barahona and A.R. Mahjoub have given an informal description of a polynomial-time separation procedure for the odd-cycle inequalities. Since then, the odd-cycle separation problem has broadly been considered solved. However, as we reveal, a straightforward implementation is likely to generate inequalities that are not facet-defining and have further undesired properties. Here, we present a more detailed analysis, along with enhancements to overcome the associated issues efficiently. In a corresponding experimental study, it turns out that these are worthwhile, and may speed up the solution process significantly.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Combinatorial optimization
  • Mathematics of computing → Linear programming
  • Mathematics of computing → Integer programming
Keywords
  • Maximum cut
  • Binary quadratic optimization
  • Integer linear programming

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Francisco Barahona, Michael Jünger, and Gerhard Reinelt. Experiments in quadratic 0-1 programming. Mathematical Programming, 44(1):127-137, May 1989. URL: https://doi.org/10.1007/BF01587084.
  2. Francisco Barahona and Ali Ridha Mahjoub. On the cut polytope. Mathematical Programming, 36(2):157-173, June 1986. URL: https://doi.org/10.1007/BF02592023.
  3. Caterina De Simone, Martin Diehl, Michael Jünger, Petra Mutzel, Gerhard Reinelt, and Giovanni Rinaldi. Exact ground states of Ising spin glasses: New experimental results with a branch-and-cut algorithm. Journal of Statistical Physics, 80(1-2):487-496, 1995. Google Scholar
  4. Caterina De Simone, Martin Diehl, Michael Jünger, Petra Mutzel, Gerhard Reinelt, and Giovanni Rinaldi. Exact ground states of two-dimensional ±J Ising spin glasses. Journal of Statistical Physics, 84(5):1363-1371, September 1996. URL: https://doi.org/10.1007/BF02174135.
  5. Franz Rendl, Giovanni Rinaldi, and Angelika Wiegele. A Branch and Bound Algorithm for Max-Cut Based on Combining Semidefinite and Polyhedral Relaxations. In Matteo Fischetti and David P. Williamson, editors, Integer Programming and Combinatorial Optimization, pages 295-309, Berlin, Heidelberg, 2007. Springer. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail