{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,13]],"date-time":"2026-01-13T16:33:36Z","timestamp":1768322016542,"version":"3.49.0"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2022,3,17]],"date-time":"2022-03-17T00:00:00Z","timestamp":1647475200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,3,17]],"date-time":"2022-03-17T00:00:00Z","timestamp":1647475200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100010665","name":"H2020 Marie Sklodowska-Curie Actions","doi-asserted-by":"publisher","award":["764759"],"award-info":[{"award-number":["764759"]}],"id":[{"id":"10.13039\/100010665","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100008905","name":"University of Klagenfurt","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100008905","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Comput Optim Appl"],"published-print":{"date-parts":[[2022,5]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We study two NP-complete graph partition problems, <jats:italic>k<\/jats:italic>-equipartition problems and graph partition problems with knapsack constraints (GPKC). We introduce tight SDP relaxations with nonnegativity constraints to get lower bounds, the SDP relaxations are solved by an extended alternating direction method of multipliers (ADMM). In this way, we obtain high quality lower bounds for <jats:italic>k<\/jats:italic>-equipartition on large instances up to <jats:inline-formula><jats:alternatives><jats:tex-math>$$n =1000$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>=<\/mml:mo>\n                    <mml:mn>1000<\/mml:mn>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> vertices within as few as 5 min and for GPKC problems up to <jats:inline-formula><jats:alternatives><jats:tex-math>$$n=500$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>=<\/mml:mo>\n                    <mml:mn>500<\/mml:mn>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> vertices within as little as 1 h. On the other hand, interior point methods fail to solve instances from <jats:inline-formula><jats:alternatives><jats:tex-math>$$n=300$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>=<\/mml:mo>\n                    <mml:mn>300<\/mml:mn>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> due to memory requirements. We also design heuristics to generate upper bounds from the SDP solutions, giving us tighter upper bounds than other methods proposed in the literature with low computational expense.<\/jats:p>","DOI":"10.1007\/s10589-022-00355-1","type":"journal-article","created":{"date-parts":[[2022,3,17]],"date-time":"2022-03-17T04:38:27Z","timestamp":1647491907000},"page":"251-291","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["SDP-based bounds for graph partition via extended ADMM"],"prefix":"10.1007","volume":"82","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1670-7951","authenticated-orcid":false,"given":"Angelika","family":"Wiegele","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6352-0968","authenticated-orcid":false,"given":"Shudian","family":"Zhao","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,3,17]]},"reference":[{"key":"355_CR1","unstructured":"MOSEK ApS.: The MOSEK optimization toolbox for MATLAB manual. Version 9.1.13, 2020. http:\/\/docs.mosek.com\/9.1.13\/toolbox\/index.html"},{"key":"355_CR2","unstructured":"Dipl.-Math Armbruster.: Branch-and-Cut for a Semidefinite relaxation of large-scale minimum bisection problems. (2007)"},{"issue":"1\u20132","key":"355_CR3","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. Programm. 155(1\u20132), 57\u201379 (2016)","journal-title":"Math. Programm."},{"issue":"5","key":"355_CR4","doi-asserted-by":"publisher","first-page":"523","DOI":"10.1016\/j.orl.2018.08.003","volume":"46","author":"M De Santis","year":"2018","unstructured":"De Santis, M., Rendl, F., Wiegele, A.: Using a factored dual in augmented Lagrangian methods for semidefinite programming. Oper. Res. Lett. 46(5), 523\u2013528 (2018)","journal-title":"Oper. Res. Lett."},{"key":"355_CR5","unstructured":"de\u00a0Souza, C.C.: The graph equipartition problem: Optimal solutions, extensions and applications. PhD thesis, PhD-Thesis, Universit\u00e9 Catholique de Louvain, Louvain-la-Neuve, Belgium (1993)"},{"issue":"1","key":"355_CR6","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1007\/s10898-009-9520-1","volume":"48","author":"N Fan","year":"2010","unstructured":"Fan, N., Pardalos, P.M.: Linear and quadratic programming approaches for the general graph partitioning problem. J. Glob. Optim. 48(1), 57\u201371 (2010)","journal-title":"J. Glob. Optim."},{"key":"355_CR7","doi-asserted-by":"crossref","unstructured":"Frieze, A., Jerrum, M.: Improved approximation algorithms for MAX $$k$$-CUT and MAX bisection. In: International conference on integer programming and combinatorial optimization, pp. 1\u201313. Springer (1995)","DOI":"10.1007\/3-540-59408-6_37"},{"key":"355_CR8","doi-asserted-by":"crossref","unstructured":"Garey, M.R., Johnson, D.S., Stockmeyer, L.: Some simplified NP-complete problems. In: Proceedings of the sixth annual ACM symposium on theory of computing, pp. 47\u201363 (1974)","DOI":"10.1145\/800119.803884"},{"issue":"1","key":"355_CR9","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1007\/s10479-008-0481-4","volume":"188","author":"B Ghaddar","year":"2011","unstructured":"Ghaddar, B., Anjos, M.F., Liers, F.: A branch-and-cut algorithm based on semidefinite programming for the minimum $$k$$-partition problem. Ann. Oper. Res. 188(1), 155\u2013174 (2011)","journal-title":"Ann. Oper. Res."},{"issue":"6","key":"355_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)"},{"key":"355_CR11","doi-asserted-by":"crossref","unstructured":"Helmberg, C., Rendl, F., Weismantel, R.: Quadratic knapsack relaxations using cutting planes and semidefinite programming. In: International conference on integer programming and combinatorial optimization, pp. 175\u2013189 (1996)","DOI":"10.1007\/3-540-61310-2_14"},{"issue":"12","key":"355_CR12","doi-asserted-by":"publisher","first-page":"1519","DOI":"10.1016\/S0167-8191(00)00048-X","volume":"26","author":"B Hendrickson","year":"2000","unstructured":"Hendrickson, B., Kolda, T.G.: Graph partitioning models for parallel computing. Parallel Comput. 26(12), 1519\u20131534 (2000)","journal-title":"Parallel Comput."},{"issue":"1","key":"355_CR13","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1137\/050622870","volume":"46","author":"C Jansson","year":"2007","unstructured":"Jansson, C., Chaykin, D., Keil, C.: Rigorous error bounds for the optimal value in semidefinite programming. SIAM J. Numer. Anal. 46(1), 180\u2013200 (2007)","journal-title":"SIAM J. Numer. Anal."},{"issue":"6","key":"355_CR14","doi-asserted-by":"publisher","first-page":"865","DOI":"10.1287\/opre.37.6.865","volume":"37","author":"DS Johnson","year":"1989","unstructured":"Johnson, D.S., Aragon, C.R., McGeoch, L.A., Schevon, C.: Optimization by simulated annealing: an experimental evaluation; part i, graph partitioning. Oper. Res. 37(6), 865\u2013892 (1989)","journal-title":"Oper. Res."},{"issue":"10","key":"355_CR15","doi-asserted-by":"publisher","first-page":"2245","DOI":"10.1002\/j.1538-7305.1965.tb04146.x","volume":"44","author":"S Lin","year":"1965","unstructured":"Lin, S.: Computer solutions of the traveling salesman problem. Bell Syst. Tech. J. 44(10), 2245\u20132269 (1965)","journal-title":"Bell Syst. Tech. J."},{"issue":"1","key":"355_CR16","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1007\/s10107-002-0342-x","volume":"95","author":"A Lisser","year":"2003","unstructured":"Lisser, A., Rendl, F.: Graph partitioning using linear and semidefinite programming. Math. Programm. 95(1), 91\u2013101 (2003)","journal-title":"Math. Programm."},{"key":"355_CR17","doi-asserted-by":"crossref","unstructured":"Lorenz, D.A., Tran-Dinh, Q.: Non-stationary Douglas-Rachford and alternating direction method of multipliers: adaptive stepsizes and convergence. Comput. Optim. Appl. 74(1), 67\u201392 (2019)","DOI":"10.1007\/s10589-019-00106-9"},{"issue":"1","key":"355_CR18","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."},{"key":"355_CR19","unstructured":"Nguyen, D.P.: Contributions to graph partitioning problems under resource constraints. Doctoral dissertation, Universit\u00e9 Pierre et Marie Curie-Paris VI (2016)"},{"key":"355_CR20","unstructured":"Nishihara, R., Lessard, L., Recht, B., Packard, A., Jordan, M.: A general analysis of the convergence of ADMM. In: International conference on machine learning, pp. 343\u2013352 (2015)"},{"issue":"3","key":"355_CR21","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1016\/S0168-9274(98)00097-X","volume":"29","author":"F Rendl","year":"1999","unstructured":"Rendl, F.: Semidefinite programming and combinatorial optimization. Appl. Numer. Math. 29(3), 255\u2013281 (1999)","journal-title":"Appl. Numer. Math."},{"key":"355_CR22","doi-asserted-by":"publisher","first-page":"795","DOI":"10.1007\/978-1-4614-0769-0_27","volume-title":"Handbook on Semidefinite, Conic and Polynomial Optimization","author":"R Sotirov","year":"2012","unstructured":"Sotirov, R.: SDP relaxations for some combinatorial optimization problems. In: Anjos, M.F. (ed.) Handbook on Semidefinite, Conic and Polynomial Optimization, pp. 795\u2013819. Springer, Berlin (2012)"},{"key":"355_CR23","doi-asserted-by":"crossref","unstructured":"Sun, D., Toh, K.-C., Yuan, Y., Zhao, X.-Y.: SDPNAL+: a matlab software for semidefinite programming with bound constraints (version 1.0). Optimization Methods and Software, pp. 1\u201329 (2019)","DOI":"10.1080\/10556788.2019.1576176"}],"container-title":["Computational Optimization and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-022-00355-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10589-022-00355-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-022-00355-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,4,9]],"date-time":"2022-04-09T12:08:46Z","timestamp":1649506126000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10589-022-00355-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,3,17]]},"references-count":23,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,5]]}},"alternative-id":["355"],"URL":"https:\/\/doi.org\/10.1007\/s10589-022-00355-1","relation":{},"ISSN":["0926-6003","1573-2894"],"issn-type":[{"value":"0926-6003","type":"print"},{"value":"1573-2894","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,3,17]]},"assertion":[{"value":"19 May 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 February 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 March 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no conflicts of interest to declare that are relevant to the content of this article.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflicts of interest\/Competing interests"}},{"value":"All data can be downloaded from https:\/\/github.com\/shudianzhao\/ADMM-GP.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Availability of data and material"}},{"value":"The codes can be downloaded from https:\/\/github.com\/shudianzhao\/ADMM-GP.","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Code availability"}},{"value":"Not applicable","order":5,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethics approval"}},{"value":"Not applicable","order":6,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent to participate"}},{"value":"Not applicable","order":7,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for publication"}}]}}