{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,27]],"date-time":"2026-05-27T16:09:06Z","timestamp":1779898146103,"version":"3.53.1"},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2020,5,25]],"date-time":"2020-05-25T00:00:00Z","timestamp":1590364800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,5,25]],"date-time":"2020-05-25T00:00:00Z","timestamp":1590364800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Austrian Science Fund","award":["I 3199-N31"],"award-info":[{"award-number":["I 3199-N31"]}]},{"name":"Austrian Science Fund","award":["P 28008-N35"],"award-info":[{"award-number":["P 28008-N35"]}]},{"name":"H2020 Marie Sklodowska-Curie Actions","award":["764759"],"award-info":[{"award-number":["764759"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2020,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The \u201cexact subgraph\u201d approach was recently introduced as a hierarchical scheme to get increasingly tight semidefinite programming relaxations of several NP-hard graph optimization problems. Solving these relaxations is a computational challenge because of the potentially large number of violated subgraph constraints. We introduce a computational framework for these relaxations designed to cope with these difficulties. We suggest a partial Lagrangian dual, and exploit the fact that its evaluation decomposes into several independent subproblems. This opens the way to use the bundle method from non-smooth optimization to minimize the dual function. Finally computational experiments on the Max-Cut, stable set and coloring problem show the excellent quality of the bounds obtained with this approach.<\/jats:p>","DOI":"10.1007\/s10107-020-01512-2","type":"journal-article","created":{"date-parts":[[2020,5,25]],"date-time":"2020-05-25T20:03:07Z","timestamp":1590436987000},"page":"283-308","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["A computational study of exact subgraph based SDP bounds for Max-Cut, stable set and coloring"],"prefix":"10.1007","volume":"183","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1643-6066","authenticated-orcid":false,"given":"Elisabeth","family":"Gaar","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1578-9414","authenticated-orcid":false,"given":"Franz","family":"Rendl","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2020,5,25]]},"reference":[{"issue":"1","key":"1512_CR1","first-page":"40","volume":"53","author":"E Adams","year":"2015","unstructured":"Adams, E., Anjos, M.F., Rendl, F., Wiegele, A.: A Hierarchy of subgraph projection-based semidefinite relaxations for some NP-hard graph optimization problems. INFOR Inf. Syst. Oper. Res. 53(1), 40\u201347 (2015)","journal-title":"INFOR Inf. Syst. Oper. Res."},{"key":"1512_CR2","doi-asserted-by":"crossref","unstructured":"Alizadeh, F., Goldfarb, D.: Second-order cone programming. Math. Program. 95(1, Ser. B), 3\u201351, iSMP 2000, Part 3. Atlanta, GA (2003)","DOI":"10.1007\/s10107-002-0339-5"},{"key":"1512_CR3","unstructured":"Biq Mac Library: http:\/\/biqmac.aau.at\/. Last accessed 15 May 2019"},{"key":"1512_CR4","volume-title":"Numerical Optimization: Theoretical and Practical Aspects","author":"JF Bonnans","year":"2006","unstructured":"Bonnans, J.F., Gilbert, J.C., Lemar\u00e9chal, C., Sagastiz\u00e1bal, C.A.: Numerical Optimization: Theoretical and Practical Aspects. Springer, Secaucus (2006)"},{"issue":"2","key":"1512_CR5","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1016\/0167-6377(90)90044-6","volume":"9","author":"E Boros","year":"1990","unstructured":"Boros, E., Crama, Y., Hammer, P.L.: Upper-bounds for quadratic $$0$$-$$1$$ maximization. Oper. Res. Lett. 9(2), 73\u201379 (1990)","journal-title":"Oper. Res. Lett."},{"key":"1512_CR6","first-page":"2","volume":"98","author":"S Dash","year":"2015","unstructured":"Dash, S., Puget, J.F.: On quadratic unconstrained binary optimization problems defined on Chimera graphs. Optima 98, 2 (2015)","journal-title":"Optima"},{"key":"1512_CR7","doi-asserted-by":"crossref","unstructured":"De Santis, M., Rendl, F., Wiegele, A.: Using a Factored Dual in Augmented Lagrangian Methods for Semidefinite Programming. ArXiv e-prints (Oct 2017)","DOI":"10.1016\/j.orl.2018.08.003"},{"issue":"3, Ser. A","key":"1512_CR8","doi-asserted-by":"crossref","first-page":"557","DOI":"10.1007\/BF01585184","volume":"62","author":"C Delorme","year":"1993","unstructured":"Delorme, C., Poljak, S.: Laplacian eigenvalues and the maximum cut problem. Math. Progr 62(3, Ser. A), 557\u2013574 (1993)","journal-title":"Math. Progr"},{"key":"1512_CR9","unstructured":"DIMACS Implementation Challenges: http:\/\/dimacs.rutgers.edu\/Challenges\/ (1992). Last accessed 15 May 2019"},{"issue":"2\u20133, Ser. B","key":"1512_CR10","doi-asserted-by":"crossref","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, Ser. B), 451\u2013469 (2006)","journal-title":"Math. Program."},{"issue":"1","key":"1512_CR11","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1007\/s10107-013-0642-3","volume":"145","author":"A Frangioni","year":"2014","unstructured":"Frangioni, A., Gorgone, E.: Bundle methods for sum-functions with \u201ceasy\u201d components: applications to multicommodity network design. Math. Program. 145(1), 133\u2013161 (2014)","journal-title":"Math. Program."},{"key":"1512_CR12","unstructured":"Gaar, E.: Efficient Implementation of SDP Relaxations for the Stable Set Problem. Ph.D. thesis, Alpen-Adria-Universit\u00e4t Klagenfurt (2018)"},{"key":"1512_CR13","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1007\/978-3-030-17953-3_16","volume-title":"Integer Programming and Combinatorial Optimization","author":"E Gaar","year":"2019","unstructured":"Gaar, E., Rendl, F.: A bundle approach for SDPs with exact subgraph constraints. In: Lodi, A., Nagarajan, V. (eds.) Integer Programming and Combinatorial Optimization, pp. 205\u2013218. Springer, Berlin (2019)"},{"issue":"6","key":"1512_CR14","doi-asserted-by":"crossref","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. Assoc. Comput. Mach. 42(6), 1115\u20131145 (1995)","journal-title":"J. Assoc. Comput. Mach."},{"key":"1512_CR15","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-97881-4","volume-title":"Geometric Algorithms and Combinatorial Optimization, Algorithms and Combinatorics: Study and Research Texts","author":"M Gr\u00f6tschel","year":"1988","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization, Algorithms and Combinatorics: Study and Research Texts, vol. 2. Springer, Berlin (1988)"},{"issue":"1","key":"1512_CR16","doi-asserted-by":"crossref","first-page":"30","DOI":"10.1137\/S0895480100376794","volume":"18","author":"V Guruswami","year":"2004","unstructured":"Guruswami, V., Khanna, S.: On the hardness of 4-coloring a 3-colorable graph. SIAM J. Discrete Math. 18(1), 30\u201340 (2004)","journal-title":"SIAM J. Discrete Math."},{"issue":"1","key":"1512_CR17","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1007\/BF02392825","volume":"182","author":"J H\u00e5stad","year":"1999","unstructured":"H\u00e5stad, J.: Clique is hard to approximate within $$n^{1-\\epsilon }$$. Acta Math. 182(1), 105\u2013142 (1999)","journal-title":"Acta Math."},{"issue":"3","key":"1512_CR18","doi-asserted-by":"crossref","first-page":"673","DOI":"10.1137\/S1052623497328987","volume":"10","author":"C Helmberg","year":"2000","unstructured":"Helmberg, C., Rendl, F.: A spectral bundle method for semidefinite programming. SIAM J. Optim. 10(3), 673\u2013696 (2000)","journal-title":"SIAM J. Optim."},{"key":"1512_CR19","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-06409-2","volume-title":"Convex Analysis and Minimization Algorithms II: Advanced Theory and Bundle Methods","author":"JB Hiriart-Urruty","year":"1993","unstructured":"Hiriart-Urruty, J.B., Lemar\u00e9chal, C.: Convex Analysis and Minimization Algorithms II: Advanced Theory and Bundle Methods. Springer, Berlin (1993)"},{"key":"1512_CR20","doi-asserted-by":"crossref","unstructured":"Khot, S.: Improved inapproximability results for MaxClique, chromatic number and approximate graph coloring. In: 42nd IEEE Symposium on Foundations of Computer Science (Las Vegas, NV, 2001), pp. 600\u2013609. IEEE Computer Society, Los Alamitos, CA (2001)","DOI":"10.1109\/SFCS.2001.959936"},{"issue":"1","key":"1512_CR21","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1007\/BF01585731","volume":"46","author":"KC Kiwiel","year":"1990","unstructured":"Kiwiel, K.C.: Proximity control in bundle methods for convex nondifferentiable minimization. Math. Program. 46(1), 105\u2013122 (1990)","journal-title":"Math. Program."},{"key":"1512_CR22","doi-asserted-by":"crossref","unstructured":"Lasserre, J.B.: An explicit exact SDP relaxation for nonlinear 0-1 programs. In: Integer programming and combinatorial optimization (Utrecht, 2001), Lecture Notes in Compututer Science, vol.\u00a02081, pp. 293\u2013303. Springer, Berlin (2001)","DOI":"10.1007\/3-540-45535-3_23"},{"key":"1512_CR23","first-page":"247","volume-title":"Integer Programming and Combinatorial Optimization","author":"M Laurent","year":"1992","unstructured":"Laurent, M., Poljak, S.: The metric polytope. In: Balas, E., Cornuejols, G., Kannan, R. (eds.) Integer Programming and Combinatorial Optimization, pp. 247\u2013286. Springers, Berlin (1992)"},{"issue":"1","key":"1512_CR24","doi-asserted-by":"crossref","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"},{"issue":"2","key":"1512_CR25","doi-asserted-by":"crossref","first-page":"166","DOI":"10.1137\/0801013","volume":"1","author":"L Lov\u00e1sz","year":"1991","unstructured":"Lov\u00e1sz, L., Schrijver, A.: Cones of matrices and set-functions and $$0$$-$$1$$ optimization. SIAM J. Optim. 1(2), 166\u2013190 (1991)","journal-title":"SIAM J. Optim."},{"key":"1512_CR26","unstructured":"MOSEK ApS: The MOSEK optimization toolbox for MATLAB manual. Version 8.0. (2017). http:\/\/docs.mosek.com\/8.0\/toolbox\/index.html"},{"key":"1512_CR27","unstructured":"Nguyen, T.H., Bui, T.: Graph coloring benchmark instances. https:\/\/turing.cs.hbg.psu.edu\/txn131\/graphcoloring.html. Last accessed 15 May 2019"},{"issue":"2, Ser. A","key":"1512_CR28","doi-asserted-by":"crossref","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, Ser. A), 307\u2013335 (2010)","journal-title":"Math. Program."},{"issue":"2\u20133, Ser. B","key":"1512_CR29","doi-asserted-by":"crossref","first-page":"505","DOI":"10.1007\/s10107-006-0038-8","volume":"109","author":"F Rendl","year":"2007","unstructured":"Rendl, F., Sotirov, R.: Bounds for the quadratic assignment problem using the bundle method. Math. Program. 109(2\u20133, Ser. B), 505\u2013524 (2007)","journal-title":"Math. Program."},{"key":"1512_CR30","doi-asserted-by":"crossref","first-page":"435","DOI":"10.1016\/S0294-1449(17)30033-1","volume":"S6","author":"SM Robinson","year":"1989","unstructured":"Robinson, S.M.: Bundle-based decomposition: conditions for convergence. Ann. l\u2019I.H.P. Anal. non lin\u00e9aire S6, 435\u2013447 (1989)","journal-title":"Ann. l\u2019I.H.P. Anal. non lin\u00e9aire"},{"key":"1512_CR31","volume-title":"Convex Analysis. Princeton Mathematical Series, No. 28","author":"RT Rockafellar","year":"1970","unstructured":"Rockafellar, R.T.: Convex Analysis. Princeton Mathematical Series, No. 28. Princeton University Press, Princeton (1970)"},{"issue":"3","key":"1512_CR32","doi-asserted-by":"crossref","first-page":"411","DOI":"10.1137\/0403036","volume":"3","author":"HD Sherali","year":"1990","unstructured":"Sherali, H.D., Adams, W.P.: A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems. SIAM J. Discrete Math. 3(3), 411\u2013430 (1990)","journal-title":"SIAM J. Discrete Math."},{"issue":"1\u20134","key":"1512_CR33","first-page":"545","volume":"11\/12","author":"KC Toh","year":"1999","unstructured":"Toh, K.C., Todd, M.J., T\u00fct\u00fcnc\u00fc, R.H.: SDPT3\u2014a MATLAB software package for semidefinite programming, version 1.3. Optim. Methods Softw. 11\/12(1\u20134), 545\u2013581 (1999)","journal-title":"Methods Softw."},{"issue":"2, Ser. B","key":"1512_CR34","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1007\/s10107-002-0347-5","volume":"95","author":"RH T\u00fct\u00fcnc\u00fc","year":"2003","unstructured":"T\u00fct\u00fcnc\u00fc, R.H., Toh, K.C., Todd, M.J.: Solving semidefinite-quadratic-linear programs using SDPT3. Math. Program. 95(2, Ser. B), 189\u2013217 (2003)","journal-title":"Math. Program."},{"issue":"3","key":"1512_CR35","doi-asserted-by":"crossref","first-page":"331","DOI":"10.1007\/s12532-015-0082-6","volume":"7","author":"L Yang","year":"2015","unstructured":"Yang, L., Sun, D., Toh, K.C.: $${\\rm SDPNAL}+$$: a majorized semismooth Newton-CG augmented Lagrangian method for semidefinite programming with nonnegative constraints. Math. Program. Comput. 7(3), 331\u2013366 (2015)","journal-title":"Math. Program. Comput."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-020-01512-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-020-01512-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-020-01512-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,24]],"date-time":"2021-05-24T23:51:23Z","timestamp":1621900283000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-020-01512-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,5,25]]},"references-count":35,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2020,9]]}},"alternative-id":["1512"],"URL":"https:\/\/doi.org\/10.1007\/s10107-020-01512-2","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,5,25]]},"assertion":[{"value":"31 May 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 April 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 May 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}