Biq Mac swMATH ID: 10532 Software Authors: Rendl, Franz; Rinaldi, Giovanni; Wiegele, Angelika Description: 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. Homepage: http://biqmac.uni-klu.ac.at/ Keywords: cut polytope; unconstrained binary quadratic optimization Related Software: BiqMac; CPLEX; SDPT3; SCIP; SeDuMi; CSDP; Gurobi; DIMACS; SDPLR; Mosek; Matlab; SDPNAL+; Rudy; OR-Library; COL; YALMIP; SDPA; Concorde; BiqCrunch; QAPLIB Cited in: 93 Publications Standard Articles 1 Publication describing the Software, including 1 Publication in zbMATH Year Solving Max-cut to optimality by intersecting semidefinite and polyhedral relaxations. Zbl 1184.90118Rendl, Franz; Rinaldi, Giovanni; Wiegele, Angelika 2010 all top 5 Cited by 181 Authors 10 Anjos, Miguel F. 7 Wiegele, Angelika 5 Toh, Kim Chuan 4 Kim, Sunyoung 4 Kojima, Masakazu 4 Rendl, Franz 4 Rinaldi, Giovanni 3 Engau, Alexander 3 Fampa, Marcia Helena C. 3 Hungerländer, Philipp 3 Le Digabel, Sébastien 3 Lee, Jon 3 Letchford, Adam N. 3 Li, Duan 3 Liers, Frauke 3 Lodi, Andrea 3 Misener, Ruth 3 Neto, José 3 Rodrigues de Sousa, Vilmar Jefté 3 Traversi, Emiliano 2 Bertsimas, Dimitris John 2 Bonato, Thorsten 2 Chen, Liang 2 Furini, Fabio 2 Jarre, Florian 2 Jünger, Michael 2 Kaparis, Konstantinos 2 Létocart, Lucas 2 Lieder, Felix 2 Liu, Chunli 2 Lu, Cheng 2 Palagi, Laura 2 Pauphilet, Jean 2 Piccialli, Veronica 2 Povh, Janez 2 Sun, Defeng 2 Sun, Xiaoling 2 Vannelli, Anthony 2 Xia, Yong 1 Afsharnejad, Zahra 1 Al-Homidan, Suliman S. 1 Allouche, David 1 André, Isabelle 1 Anstreicher, Kurt M. 1 Armbruster, Michael 1 Barbe, Sophie 1 Belotti, Pietro 1 Ben-Ameur, Walid 1 Billionnet, Alain 1 Bomze, Immanuel M. 1 Boukouvala, Fani 1 Buchheim, Christoph 1 Burer, Samuel 1 Campos, Juan S. 1 Ceselli, Alberto 1 Chen, Jing 1 Chen, Wei-An 1 Chimani, Markus 1 Ciré, André Augusto 1 Cory-Wright, Ryan 1 Davies, Jessica 1 de Givry, Simon 1 Delling, Daniel 1 Deng, Zhibin 1 Dey, Santanu Subhas 1 Dickinson, Peter J. C. 1 Dolatabadi, Mohammad 1 Dong, Hongbo 1 Dunning, Iain 1 Fleischman, Daniel 1 Floudas, Christodoulos Achilleus 1 Frangioni, Antonio 1 Friberg, Henrik A. 1 Fügenschuh, Marzena 1 Gaar, Elisabeth 1 Gally, Tristan M. 1 Gao, Jianjun 1 Ghaddar, Bissan 1 Gleixner, Ambros M. 1 Glorieux, Antoine 1 Goldberg, Andrew V. 1 Goldberg, Noam 1 Goldfarb, Donald 1 Gould, Nick I. M. 1 Grimm, Veronika 1 Grippo, Luigi 1 Grossmann, Ignacio E. 1 Gu, Shenshen 1 Gupta, Swati 1 Gusmeroli, Nicoló 1 Hager, William W. 1 Hao, Jin-Kao 1 Helmberg, Christoph 1 Hooker, John N. jun. 1 Hrga, Timotej 1 Huang, Yakui 1 Hupp, Lena 1 Jiao, Hongwei 1 John, Maximilian 1 Karrenbauer, Andreas ...and 81 more Authors all top 5 Cited in 29 Serials 13 Mathematical Programming. Series A. Series B 7 Journal of Global Optimization 7 Computational Optimization and Applications 6 Mathematical Programming Computation 5 Optimization Methods & Software 4 Annals of Operations Research 4 SIAM Journal on Optimization 4 Discrete Optimization 3 Discrete Applied Mathematics 3 Computers & Operations Research 3 Optimization Letters 2 Operations Research Letters 2 European Journal of Operational Research 2 Cybernetics and Systems Analysis 2 International Transactions in Operational Research 2 INFORMS Journal on Computing 2 EURO Journal on Computational Optimization 1 Artificial Intelligence 1 Journal of Statistical Physics 1 Journal of Computational and Applied Mathematics 1 Mathematics of Operations Research 1 Applied Mathematical Modelling 1 Linear Algebra and its Applications 1 Filomat 1 Mathematical Methods of Operations Research 1 Journal of Applied Mathematics 1 4OR 1 ACM Journal of Experimental Algorithmics 1 Journal of the Operations Research Society of China all top 5 Cited in 14 Fields 90 Operations research, mathematical programming (90-XX) 10 Combinatorics (05-XX) 5 Numerical analysis (65-XX) 5 Computer science (68-XX) 3 Statistics (62-XX) 3 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 2 Calculus of variations and optimal control; optimization (49-XX) 2 Convex and discrete geometry (52-XX) 2 Statistical mechanics, structure of matter (82-XX) 2 Biology and other natural sciences (92-XX) 1 Number theory (11-XX) 1 Commutative algebra (13-XX) 1 Algebraic geometry (14-XX) 1 Information and communication theory, circuits (94-XX) Citations by Year