Biq Mac
Solving Max-cut to optimality by intersecting semidefinite and polyhedral relaxations. We present a method for finding exact solutions of Max-Cut, the problem of finding a cut of maximum weight in a weighted graph. We use a Branch-and-Bound setting that applies a dynamic version of the bundle method as bounding procedure. This approach uses Lagrangian duality to obtain a “nearly optimal” solution of the basic semidefinite Max-Cut relaxation, strengthened by triangle inequalities. The expensive part of our bounding procedure is solving the basic semidefinite relaxation of the Max-Cut problem, which has to be done several times during the bounding process. We review other solution approaches and compare the numerical results with our method. We also extend our experiments to instances of unconstrained quadratic 0-1 optimization and to instances of the graph equipartition problem. The experiments show that our method nearly always outperforms all other approaches. In particular, for dense graphs, where linear programming-based methods fail, our method performs very well. Exact solutions are obtained in a reasonable time for any instance of size up to $n = 100$, independent of the density. For some problems of special structure, we can solve even larger problem classes. We could prove optimality for several problems of the literature where, to the best of our knowledge, no other method is able to do so.
Keywords for this software
References in zbMATH (referenced in 72 articles , 1 standard article )
Showing results 1 to 20 of 72.
Sorted by year (- Anjos, Miguel F.; Neto, José: A class of spectral bounds for max (k)-cut (2020)
- Bertsimas, Dimitris; Lamperski, Jourdain; Pauphilet, Jean: Certifiably optimal sparse inverse covariance estimation (2020)
- Gaar, Elisabeth; Rendl, Franz: A computational study of exact subgraph based SDP bounds for max-cut, stable set and coloring (2020)
- Jarre, Florian; Lieder, Felix; Liu, Ya-Feng; Lu, Cheng: Set-completely-positive representations and cuts for the max-cut polytope and the unit modulus lifting (2020)
- Kobayashi, Ken; Takano, Yuich: A branch-and-cut algorithm for solving mixed-integer semidefinite optimization problems (2020)
- Lee, Jon; Skipper, Daphne: Volume computation for sparse Boolean quadric relaxations (2020)
- Sharifov, F.; Hulianytskyi, L.: Cuts in undirected graphs. II (2020)
- Sharifov, F.; Hulianytskyi, L.: Cuts in undirected graphs. I (2020)
- Sun, Defeng; Toh, Kim-Chuan; Yuan, Yancheng; Zhao, Xin-Yuan: SDPNAL+: A Matlab software for semidefinite programming with bound constraints (version 1.0) (2020)
- Anjos, Miguel F.; Neto, José: Spectral bounds for graph partitioning with prescribed partition sizes (2019)
- Campos, Juan S.; Misener, Ruth; Parpas, Panos: A multilevel analysis of the Lasserre hierarchy (2019)
- Dickinson, Peter J. C.; Povh, Janez: A new approximation hierarchy for polynomial conic optimization (2019)
- Furini, Fabio; Traversi, Emiliano: Theoretical and computational study of several linearisation techniques for binary quadratic problems (2019)
- Furini, Fabio; Traversi, Emiliano; Belotti, Pietro; Frangioni, Antonio; Gleixner, Ambros; Gould, Nick; Liberti, Leo; Lodi, Andrea; Misener, Ruth; Mittelmann, Hans; Sahinidis, Nikolaos V.; Vigerske, Stefan; Wiegele, Angelika: QPLIB: a library of quadratic programming instances (2019)
- Grimm, Veronika; Kleinert, Thomas; Liers, Frauke; Schmidt, Martin; Zöttl, Gregor: Optimal price zones of electricity markets: a mixed-integer multilevel model and global solution approaches (2019)
- Rodrigues de Sousa, Vilmar Jefté; Anjos, Miguel F.; Le Digabel, Sébastien: Improving the linear relaxation of maximum (k)-cut with semidefinite-based constraints (2019)
- Anstreicher, Kurt M.: Maximum-entropy sampling and the Boolean quadric polytope (2018)
- Chen, Wei-An; Zhu, Zhen; Kong, Nan: A Lagrangian decomposition approach to computing feasible solutions for quadratic binary programs (2018)
- Dunning, Iain; Gupta, Swati; Silberholz, John: What works best when? A systematic evaluation of heuristics for max-cut and QUBO (2018)
- Fampa, Marcia; Nieto, Francisco Pinillos: Extensions on ellipsoid bounds for quadratic integer programming (2018)