CirCut swMATH ID: 4782 Software Authors: Burer, Samuel; Monteiro, Renato D. C.; Zhang, Yin Description: Rank-two relaxation heuristics for MAX-CUT and other binary quadratic programs The Goemans–Williamson randomized algorithm guarantees a high-quality approximation to the MAX-CUT problem, but the cost associated with such an approximation can be excessively high for large-scale problems due to the need for solving an expensive semidefinite relaxation. In order to achieve better practical performance, we propose an alternative, rank-two relaxation and develop a specialized version of the Goemans–Williamson technique. The proposed approach leads to continuous optimization heuristics applicable to MAX-CUT as well as other binary quadratic programs, for example the MAX-BISECTION problem.par A computer code based on the rank-two relaxation heuristics is compared with two state-of-the-art semidefinite programming codes that implement the Goemans–Williamson randomized algorithm, as well as with a purely heuristic code for effectively solving a particular MAX-CUT problem arising in physics. Computational results show that the proposed approach is fast and scalable and, more importantly, attains a higher approximation quality in practice than that of the Goemans–Williamson randomized algorithm. An extension to MAX-BISECTION is also discussed, as is an important difference between the proposed approach and the Goemans–Williamson algorithm; namely, that the new approach does not guarantee an upper bound on the MAX-CUT optimal value. Homepage: http://www.caam.rice.edu/~zhang/circut/ Keywords: binary quadratic programs; MAX-CUT and MAX-BISECTION; semidefinite relaxation; rank-two relaxation; continuous optimization heuristics Related Software: Outward rotations; SDPLR; Tabu search; COL; SeDuMi; Biq Mac; SDPpack; DIMACS; SDPA; Max-AO; SDPT3; TTTPLOTS; Scatter Search; PERL; GRASP; OR-Library; BARON; Benchmarks for Optimization Software; NOA; LaGO Cited in: 42 Publications Standard Articles 1 Publication describing the Software, including 1 Publication in zbMATH Year Rank-two relaxation heuristics for MAX-CUT and other binary quadratic programs. Zbl 1152.90532Burer, Samuel; Monteiro, Renato D. C.; Zhang, Yin 2001 all top 5 Cited by 79 Authors 5 Hao, Jin-Kao 5 Xu, Chengxian 4 Xu, Fengmin 3 Burer, Samuel 3 Glover, Fred W. 3 Ling, Aifan 3 Monteiro, Renato D. C. 3 Wang, Yang 2 Festa, Paola 2 Krishnan, Kartik 2 Lü, Zhipeng 2 Luo, Zhi-Quan 2 Ma, Fuda 2 Nowak, Ivo 2 Pardalos, Panos M. 2 Rendl, Franz 2 Zhang, Yin 1 Adler, Ilan 1 Alperin, Hernán 1 Balasundaram, Balabhaskar 1 Boros, Endre 1 Boumal, Nicolas 1 Butenko, Sergiy I. 1 Chang, Kung-Ching 1 Chen, Jein-Shan 1 De Santis, Marianna 1 Duarte, Abraham 1 Erementchouk, Mikhail 1 Fan, Neng 1 Fischer, Ilse 1 Gruber, Gerald 1 Grygiel, Krzysztof 1 Hammer, Peter Ladislaw 1 He, Xiaoliang 1 Jiang, Yuxi 1 Kisialiou, Mikalai 1 Laguna, Manuel 1 Lee, Jon 1 Li, Guoquan 1 Li, Jingfan 1 Li, Xingsi 1 Lin, Geng 1 Liu, Wenlong 1 Liuzzi, Giampaolo 1 Lucidi, Stefano 1 Martí, Rafael 1 Mazumder, Pinaki 1 Mitchell, John E. 1 Mu, Xuewen 1 Pan, Shaohua 1 Quan, Jing 1 Resende, Mauricio G. C. 1 Ribeiro, Celso Carneiro 1 Rinaldi, Francesco 1 Rinaldi, Giovanni 1 Sergiyenko, Ivan Vasyl’ovych 1 Shao, Sihong 1 Sherali, Hanif D. 1 Shukla, Aditya 1 Shylo, Oleg V. 1 Shylo, Vladimir P. 1 Śliwa, Izabela 1 Smith, J. Cole 1 Sotirov, Renata 1 Sun, Richard 1 Szlachetka, P. 1 Tan, Tao 1 Tavares, Gabriel 1 Terlaky, Tamás 1 Trick, Michael A. 1 Wiegele, Angelika 1 Wu, Jia 1 Wu, Qinghua 1 Wu, Zhiyou 1 Xia, Yong 1 Xu, Zi 1 Yildiz, Hakan 1 Zhang, Dong 1 Zhu, Wenxing all top 5 Cited in 25 Serials 5 Mathematical Programming. Series A. Series B 4 Computers & Operations Research 3 SIAM Journal on Optimization 2 Journal of Global Optimization 2 European Journal of Operational Research 2 Cybernetics and Systems Analysis 2 Optimization Methods & Software 2 Optimization Letters 1 Indian Journal of Pure & Applied Mathematics 1 Applied Mathematics and Computation 1 Journal of Computational and Applied Mathematics 1 Mathematics of Operations Research 1 Journal of Computational Mathematics 1 Physica D 1 Annals of Operations Research 1 Numerical Algorithms 1 Computational Optimization and Applications 1 Journal of Heuristics 1 Nonlinear Dynamics 1 Acta Mathematica Sinica. English Series 1 Discrete Optimization 1 ISNM. International Series of Numerical Mathematics 1 Mathematical Programming Computation 1 Science China. Mathematics 1 Journal of the Operations Research Society of China all top 5 Cited in 8 Fields 40 Operations research, mathematical programming (90-XX) 6 Numerical analysis (65-XX) 3 Combinatorics (05-XX) 3 Computer science (68-XX) 1 Global analysis, analysis on manifolds (58-XX) 1 Mechanics of particles and systems (70-XX) 1 Statistical mechanics, structure of matter (82-XX) 1 Information and communication theory, circuits (94-XX) Citations by Year