{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,7,17]],"date-time":"2024-07-17T17:17:16Z","timestamp":1721236636010},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2021,8,26]],"date-time":"2021-08-26T00:00:00Z","timestamp":1629936000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,8,26]],"date-time":"2021-08-26T00:00:00Z","timestamp":1629936000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100004329","name":"Javna Agencija za Raziskovalno Dejavnost RS","doi-asserted-by":"publisher","award":["N1-0057"],"id":[{"id":"10.13039\/501100004329","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Comput Optim Appl"],"published-print":{"date-parts":[[2021,11]]},"abstract":"Abstract<\/jats:title>We present , a parallel semidefinite-based exact solver for Max-Cut, a problem of finding the cut with the maximum weight in a given graph. The algorithm uses the branch and bound paradigm that applies the alternating direction method of multipliers as the bounding routine to solve the basic semidefinite relaxation strengthened by a subset of hypermetric inequalities. The benefit of the new approach is a less computationally expensive update rule for the dual variable with respect to the inequality constraints. We provide a theoretical convergence of the algorithm as well as extensive computational experiments with this method, to show that our algorithm outperforms state-of-the-art approaches. Furthermore, by combining algorithmic ingredients from the serial algorithm, we develop an efficient distributed parallel solver based on MPI.<\/jats:p>","DOI":"10.1007\/s10589-021-00310-6","type":"journal-article","created":{"date-parts":[[2021,8,26]],"date-time":"2021-08-26T23:59:14Z","timestamp":1630022354000},"page":"347-375","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["MADAM: a parallel exact solver for max-cut based on semidefinite programming and ADMM"],"prefix":"10.1007","volume":"80","author":[{"ORCID":"http:\/\/orcid.org\/0000-0002-4852-1986","authenticated-orcid":false,"given":"Timotej","family":"Hrga","sequence":"first","affiliation":[]},{"given":"Janez","family":"Povh","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,8,26]]},"reference":[{"key":"310_CR1","unstructured":"Garey, M.R., Johnson, D.S.: Computers and intractability, volume\u00a029. wh freeman New York, (2002)"},{"key":"310_CR2","doi-asserted-by":"crossref","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Complexity of computer computations, pp. 85\u2013103. Springer (1972)","DOI":"10.1007\/978-1-4684-2001-2_9"},{"issue":"1\u20132","key":"310_CR3","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1007\/s10107-012-0594-z","volume":"143","author":"N Krislock","year":"2014","unstructured":"Krislock, N., Malick, J., Roupin, F.: Improved semidefinite bounding procedure for solving max-cut problems to optimality. Math. Program. 143(1\u20132), 61\u201386 (2014)","journal-title":"Math. Program."},{"issue":"47\u201368","key":"310_CR4","first-page":"6","volume":"50","author":"F Liers","year":"2004","unstructured":"Liers, F., J\u00fcnger, M., Reinelt, G., Rinaldi, G.: Computing exact ground states of hard ising spin glass problems by branch-and-cut. New Optim. Algorithms Phys. 50(47\u201368), 6 (2004)","journal-title":"New Optim. Algorithms Phys."},{"issue":"2","key":"310_CR5","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1007\/s10107-008-0235-8","volume":"121","author":"F Rendl","year":"2010","unstructured":"Rendl, F., Rinaldi, G., Wiegele, A.: Solving max-cut to optimality by intersecting semidefinite and polyhedral relaxations. Math. Program. 121(2), 307 (2010)","journal-title":"Math. Program."},{"issue":"4","key":"310_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3005345","volume":"43","author":"N Krislock","year":"2017","unstructured":"Krislock, N., Malick, J., Roupin, F.: BiqCrunch: A semidefinite branch-and-bound method for solving binary quadratic problems. ACM Trans. Math. Softw. (TOMS) 43(4), 1\u201323 (2017)","journal-title":"ACM Trans. Math. Softw. (TOMS)"},{"issue":"2","key":"310_CR7","doi-asserted-by":"publisher","first-page":"158","DOI":"10.1016\/j.orl.2015.12.014","volume":"44","author":"JB Lasserre","year":"2016","unstructured":"Lasserre, J.B.: A MAX-CUT formulation of 0\/1 programs. Oper. Res. Lett. 44(2), 158\u2013164 (2016)","journal-title":"Oper. Res. Lett."},{"key":"310_CR8","unstructured":"Gusmeroli, N., Wiegele, A.: EXPEDIS: An Exact Penalty Method over Discrete Sets. arXiv preprintarXiv:1912.09739, (2019)"},{"issue":"3","key":"310_CR9","doi-asserted-by":"publisher","first-page":"608","DOI":"10.1287\/ijoc.2017.0798","volume":"30","author":"I Dunning","year":"2018","unstructured":"Dunning, I., Gupta, S., Silberholz, J.: What works best when? A systematic evaluation of heuristics for Max-Cut and QUBO. INFORMS J. Comput. 30(3), 608\u2013624 (2018)","journal-title":"INFORMS J. Comput."},{"issue":"6","key":"310_CR10","doi-asserted-by":"publisher","first-page":"1115","DOI":"10.1145\/227683.227684","volume":"42","author":"MX Goemans","year":"1995","unstructured":"Goemans, M.X., Williamson, D.P.: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM (JACM) 42(6), 1115\u20131145 (1995)","journal-title":"J. ACM (JACM)"},{"issue":"1\u20133","key":"310_CR11","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1080\/10556789408805564","volume":"3","author":"C De Simone","year":"1994","unstructured":"De Simone, C., Rinaldi, G.: A cutting plane algorithm for the max-cut problem. Optim. Methods Softw. 3(1\u20133), 195\u2013214 (1994)","journal-title":"Optim. Methods Softw."},{"issue":"3","key":"310_CR12","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1007\/BF01580072","volume":"82","author":"C Helmberg","year":"1998","unstructured":"Helmberg, C., Rendl, F.: Solving quadratic $$(0, 1)$$-problems by semidefinite programs and cutting planes. Math. Program. 82(3), 291\u2013315 (1998)","journal-title":"Math. Program."},{"key":"310_CR13","doi-asserted-by":"crossref","unstructured":"Palagi, L., Piccialli, V., Rendl, F., Rinaldi, G., Wiegele, A. (eds.): : Computational approaches to max-cut. In: Handbook on semidefinite, conic and polynomial optimization, pp. 821\u2013847. Springer (2012)","DOI":"10.1007\/978-1-4614-0769-0_28"},{"key":"310_CR14","unstructured":"Gusmeroli, N., Hrga, T., Lu\u017ear, B., Povh, J., Siebenhofer, M., Wiegele, A.: BiqBin: a parallel branch-and-bound solver for binary quadratic problems with linear constraints. arXiv preprintarXiv:2009.06240, (2020)"},{"issue":"3\u20134","key":"310_CR15","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1007\/s12532-010-0017-1","volume":"2","author":"Z Wen","year":"2010","unstructured":"Wen, Z., Goldfarb, D., Yin, W.: Alternating direction augmented lagrangian methods for semidefinite programming. Math. Program. Comput. 2(3\u20134), 203\u2013230 (2010)","journal-title":"Math. Program. Comput."},{"key":"310_CR16","unstructured":"Wolkowicz, H., Saigal, R., Vandenberghe, L.: Handbook of semidefinite programming: theory, algorithms, and applications, vol. 27. Springer Science & Business Media (2012)"},{"issue":"1\u20134","key":"310_CR17","doi-asserted-by":"publisher","first-page":"613","DOI":"10.1080\/10556789908805765","volume":"11","author":"B Borchers","year":"1999","unstructured":"Borchers, B.: CSDP, A C library for semidefinite programming. Optim. Methods Softw. 11(1\u20134), 613\u2013623 (1999)","journal-title":"Optim. Methods Softw."},{"key":"310_CR18","unstructured":"ApS, M.: The MOSEK optimization toolbox for MATLAB manual, (2015)"},{"issue":"1\u20134","key":"310_CR19","doi-asserted-by":"publisher","first-page":"625","DOI":"10.1080\/10556789908805766","volume":"11","author":"JF Sturm","year":"1999","unstructured":"Sturm, J.F.: Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones. Optim. Methods Softw. 11(1\u20134), 625\u2013653 (1999)","journal-title":"Optim. Methods Softw."},{"issue":"1\u20134","key":"310_CR20","doi-asserted-by":"publisher","first-page":"545","DOI":"10.1080\/10556789908805762","volume":"11","author":"KC Toh","year":"1999","unstructured":"Toh, K.C., Todd, M.J., T\u00fct\u00fcnc\u00fc, R.H.: SDPT3-a MATLAB software package for semidefinite programming, version 1.3. Optim. Methods Softw. 11(1\u20134), 545\u2013581 (1999)","journal-title":"Optim. Methods Softw."},{"issue":"2","key":"310_CR21","doi-asserted-by":"publisher","first-page":"342","DOI":"10.1137\/0806020","volume":"6","author":"C Helmberg","year":"1996","unstructured":"Helmberg, C., Rendl, F., Vanderbei, R.J., Wolkowicz, H.: An interior-point method for semidefinite programming. SIAM J. Optim. 6(2), 342\u2013361 (1996)","journal-title":"SIAM J. Optim."},{"issue":"6","key":"310_CR22","first-page":"263","volume":"6","author":"KC Kiwiel","year":"1989","unstructured":"Kiwiel, K.C.: A survey of bundle methods for nondifferentiable optimization. Math. Appl. Jan. Ser. 6(6), 263\u2013282 (1989)","journal-title":"Math. Appl. Jan. Ser."},{"issue":"5","key":"310_CR23","doi-asserted-by":"publisher","first-page":"1190","DOI":"10.1137\/0916069","volume":"16","author":"RH Byrd","year":"1995","unstructured":"Byrd, R.H., Peihuang, L., Nocedal, J., Zhu, C.: A limited memory algorithm for bound constrained optimization. SIAM J. Sci. Comput. 16(5), 1190\u20131208 (1995)","journal-title":"SIAM J. Sci. Comput."},{"issue":"2","key":"310_CR24","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1007\/s10107-002-0352-8","volume":"95","author":"S Burer","year":"2003","unstructured":"Burer, S., Monteiro, R.D.C.: A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization. Math. Program. 95(2), 329\u2013357 (2003)","journal-title":"Math. Program."},{"issue":"2\u20133","key":"310_CR25","doi-asserted-by":"publisher","first-page":"451","DOI":"10.1007\/s10107-005-0661-9","volume":"105","author":"I Fischer","year":"2006","unstructured":"Fischer, I., Gruber, G., Rendl, F., Sotirov, R.: Computational experience with a bundle approach for semidefinite cutting plane relaxations of max-cut and equipartition. Math. Program. 105(2\u20133), 451\u2013469 (2006)","journal-title":"Math. Program."},{"issue":"1","key":"310_CR26","doi-asserted-by":"publisher","first-page":"336","DOI":"10.1137\/070704575","volume":"20","author":"J Malick","year":"2009","unstructured":"Malick, J., Povh, J., Rendl, F., Wiegele, A.: Regularization methods for semidefinite programming. SIAM J. Optim. 20(1), 336\u2013356 (2009)","journal-title":"SIAM J. Optim."},{"issue":"1","key":"310_CR27","first-page":"1","volume":"3","author":"S Boyd","year":"2011","unstructured":"Boyd, S., Parikh, N., Chu, E., Peleato, B., Eckstein, J., et al.: Distributed optimization and statistical learning via the alternating direction method of multipliers. Found. Trends\u00ae Mach. Learn. 3(1), 1\u2013122 (2011)","journal-title":"Found. Trends\u00ae Mach. Learn."},{"issue":"3","key":"310_CR28","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1007\/s00607-006-0182-2","volume":"78","author":"J Povh","year":"2006","unstructured":"Povh, J., Rendl, F., Wiegele, A.: A boundary point method to solve semidefinite programs. Computing 78(3), 277\u2013286 (2006)","journal-title":"Computing"},{"issue":"1","key":"310_CR29","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1109\/TIT.1979.1055985","volume":"25","author":"L Lov\u00e1sz","year":"1979","unstructured":"Lov\u00e1sz, L.: On the shannon capacity of a graph. IEEE Trans. Inf. Theory 25(1), 1\u20137 (1979)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"310_CR30","doi-asserted-by":"crossref","unstructured":"Anderson, E., Bai, Z., Bischof, C., Blackford, L.S., Demmel, J., Dongarra, J., Du Croz, J., Greenbaum, A., Hammarling, S., McKenney, A., et\u00a0al.: LAPACK Users\u2019 guide. SIAM, (1999)","DOI":"10.1137\/1.9780898719604"},{"issue":"3","key":"310_CR31","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1391989.1391995","volume":"35","author":"Y Chen","year":"2008","unstructured":"Chen, Y., Davis, T.A., Hager, W.W., Rajamanickam, S.: Algorithm 887: CHOLMOD, supernodal sparse Cholesky factorization and update\/downdate. ACM Trans. Math. Softw. (TOMS) 35(3), 1\u201314 (2008)","journal-title":"ACM Trans. Math. Softw. (TOMS)"},{"issue":"1","key":"310_CR32","first-page":"1","volume":"38","author":"TA Davis","year":"2011","unstructured":"Davis, T.A., Yifan, H.: The University of Florida sparse matrix collection. ACM Trans. Math. Softw. (TOMS) 38(1), 1\u201325 (2011)","journal-title":"ACM Trans. Math. Softw. (TOMS)"},{"issue":"1\u20132","key":"310_CR33","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1007\/s10107-014-0826-5","volume":"155","author":"C Chen","year":"2016","unstructured":"Chen, C., He, B., Ye, Y., Yuan, X.: The direct extension of ADMM for multi-block convex minimization problems is not necessarily convergent. Math. Program. 155(1\u20132), 57\u201379 (2016)","journal-title":"Math. Program."},{"key":"310_CR34","unstructured":"Wiegele, A.: Biq Mac Library - A collection of Max-Cut and quadratic $$0-1$$ programming instances of medium size. Preprint (2007)"},{"key":"310_CR35","first-page":"46","volume":"1","author":"L Dagum","year":"1998","unstructured":"Dagum, L., Menon, R.: OpenMP: an industry-standard API for shared-memory programming. Comput. Sci. Eng. 1, 46\u201355 (1998)","journal-title":"Comput. Sci. Eng."},{"key":"310_CR36","unstructured":"Forum, M.P.: MPI.: A Message-Passing Interface Standard. Technical report. , Knoxville, TN, USA (1994)"},{"key":"310_CR37","unstructured":"Rinaldi, G.: Rudy, 1998. http:\/\/www-user.tu-chemnitz.de\/$$^{\\sim }$$helmberg\/rudy.tar.gz"},{"key":"310_CR38","unstructured":"Wiegele, A.: Nonlinear optimization techniques applied to combinatorial optimization problems (2006)"}],"container-title":["Computational Optimization and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-021-00310-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10589-021-00310-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-021-00310-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,9,23]],"date-time":"2021-09-23T12:45:04Z","timestamp":1632401104000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10589-021-00310-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,8,26]]},"references-count":38,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,11]]}},"alternative-id":["310"],"URL":"https:\/\/doi.org\/10.1007\/s10589-021-00310-6","relation":{},"ISSN":["0926-6003","1573-2894"],"issn-type":[{"value":"0926-6003","type":"print"},{"value":"1573-2894","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,8,26]]},"assertion":[{"value":"11 September 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 August 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 August 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}