{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,17]],"date-time":"2026-02-17T11:54:07Z","timestamp":1771329247190,"version":"3.50.1"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2024,4,25]],"date-time":"2024-04-25T00:00:00Z","timestamp":1714003200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,4,25]],"date-time":"2024-04-25T00:00:00Z","timestamp":1714003200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100004271","name":"Sapienza Universit\u00e0 di Roma","doi-asserted-by":"publisher","award":["RM120172A2970290"],"award-info":[{"award-number":["RM120172A2970290"]}],"id":[{"id":"10.13039\/501100004271","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["4OR-Q J Oper Res"],"published-print":{"date-parts":[[2025,3]]},"DOI":"10.1007\/s10288-024-00569-5","type":"journal-article","created":{"date-parts":[[2024,4,25]],"date-time":"2024-04-25T10:02:14Z","timestamp":1714039334000},"page":"65-95","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Dealing with inequality constraints in large-scale semidefinite relaxations for graph coloring and maximum clique problems"],"prefix":"10.1007","volume":"23","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7880-1540","authenticated-orcid":false,"given":"Federico","family":"Battista","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marianna","family":"De Santis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,4,25]]},"reference":[{"key":"569_CR1","unstructured":"Battista F (2023) On semidefinite lift-and-project of combinatorial optimization problems. PhD thesis, Universit\u00e0 di Roma Sapienza"},{"issue":"2, Ser. B","key":"569_CR2","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 RDC (2003) A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization. Math Program 95(2, Ser. B):329\u2013357","journal-title":"Math Program"},{"issue":"3, Ser. A","key":"569_CR3","doi-asserted-by":"publisher","first-page":"427","DOI":"10.1007\/s10107-004-0564-1","volume":"103","author":"S Burer","year":"2005","unstructured":"Burer S, Monteiro RDC (2005) Local minima and convergence in low-rank semidefinite programming. Math Program 103(3, Ser. A):427\u2013444","journal-title":"Math Program"},{"key":"569_CR4","doi-asserted-by":"publisher","first-page":"415","DOI":"10.1007\/s10288-020-00454-x","volume":"19","author":"M Cerulli","year":"2021","unstructured":"Cerulli M, De Santis M, Gaar E, Wiegele A (2021) Improving ADMMs for solving doubly nonnegative programs through dual factorization. 4OR 19:415\u2013448","journal-title":"4OR"},{"issue":"1\u20132","key":"569_CR5","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 (2016) The direct extension of ADMM for multi-block convex minimization problems is not necessarily convergent. Math Program 155(1\u20132):57\u201379","journal-title":"Math Program"},{"issue":"5","key":"569_CR6","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 (2018) Using a factored dual in augmented Lagrangian methods for semidefinite programming. Oper Res Lett 46(5):523\u2013528","journal-title":"Oper Res Lett"},{"key":"569_CR7","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1007\/s101070100263","volume":"91","author":"ED Dolan","year":"2002","unstructured":"Dolan ED, Mor\u00e9 JJ (2002) Benchmarking optimization software with performance profiles. Math Program 91:201\u2013213","journal-title":"Math Program"},{"issue":"2","key":"569_CR8","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1016\/j.dam.2006.07.014","volume":"156","author":"I Dukanovic","year":"2008","unstructured":"Dukanovic I, Rendl F (2008) A semidefinite programming-based heuristic for graph coloring. Discret Appl Math 156(2):180\u2013189","journal-title":"Discret Appl Math"},{"key":"569_CR9","doi-asserted-by":"publisher","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 (2019) A bundle approach for SDPs with exact subgraph constraints. In: Lodi A, Nagarajan V (eds) Integer programming and combinatorial optimization. Springer International Publishing, Cham, pp 205\u2013218"},{"issue":"2","key":"569_CR10","doi-asserted-by":"publisher","first-page":"381","DOI":"10.1007\/s10107-008-0219-8","volume":"120","author":"M Giandomenico","year":"2009","unstructured":"Giandomenico M, Letchford AN, Rossi F, Smriglio S (2009) An application of the Lov\u00e1sz-Schrijver m (k, k) operator to the stable set problem. Math Program 120(2):381\u2013401","journal-title":"Math Program"},{"issue":"3","key":"569_CR11","doi-asserted-by":"publisher","first-page":"1944","DOI":"10.1137\/140966332","volume":"25","author":"M Giandomenico","year":"2015","unstructured":"Giandomenico M, Letchford AN, Rossi F, Smriglio S (2015) Ellipsoidal relaxations of the stable set problem: theory and algorithms. SIAM J Optim 25(3):1944\u20131963","journal-title":"SIAM J Optim"},{"issue":"1","key":"569_CR12","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1007\/s10107-012-0513-3","volume":"141","author":"M Giandomenico","year":"2013","unstructured":"Giandomenico M, Rossi F, Smriglio S (2013) Strong lift-and-project cutting planes for the stable set problem. Math Program 141(1):165\u2013192","journal-title":"Math Program"},{"key":"569_CR13","volume-title":"Geometric algorithms and combinatorial optimization","author":"M Gr\u00f6tschel","year":"2012","unstructured":"Gr\u00f6tschel M, Lov\u00e1sz L, Schrijver A (2012) Geometric algorithms and combinatorial optimization, vol 2. Springer Science & Business Media, New York"},{"issue":"4","key":"569_CR14","doi-asserted-by":"publisher","first-page":"1014","DOI":"10.1137\/S1052623401394092","volume":"13","author":"G Gruber","year":"2003","unstructured":"Gruber G, Rendl F (2003) Computational experience with stable set relaxations. SIAM J Optim 13(4):1014\u20131028","journal-title":"SIAM J Optim"},{"key":"569_CR15","doi-asserted-by":"crossref","unstructured":"Jansson C, Chaykin D, Keil C (2007\/08) Rigorous error bounds for the optimal value in semidefinite programming. SIAM J Numer Anal, 46(1):180\u2013200","DOI":"10.1137\/050622870"},{"key":"569_CR16","unstructured":"Johnson DJ, Trick MA (eds) (1996) Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, Workshop, October 11-13, (1993). American Mathematical Society, Providence"},{"key":"569_CR17","first-page":"393","volume-title":"Discrete optimization. Handbooks in operations research and management science","author":"M Laurent","year":"2005","unstructured":"Laurent M, Rendl F (2005) Semidefinite programming and integer programming. In: Aardal K, Nemhauser GL, Weismantel R (eds) Discrete optimization. Handbooks in operations research and management science, vol 12. Elsevier, Amsterdam, pp 393\u2013514"},{"key":"569_CR18","unstructured":"LLC Gurobi\u00a0Optimization (2022) Gurobi optimizer reference manual"},{"issue":"2","key":"569_CR19","doi-asserted-by":"publisher","first-page":"511","DOI":"10.1007\/s10107-014-0771-3","volume":"150","author":"M Locatelli","year":"2015","unstructured":"Locatelli M (2015) Improving upper bounds for the clique number by non-valid inequalities. Math Program 150(2):511\u2013525","journal-title":"Math Program"},{"issue":"1","key":"569_CR20","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1007\/s10589-019-00106-9","volume":"74","author":"DA Lorenz","year":"2019","unstructured":"Lorenz DA, Tran-Dinh Q (2019) Non-stationary Douglas\u2013Rachford and alternating direction method of multipliers: adaptive step-sizes and convergence. Comput Optim Appl 74(1):67\u201392","journal-title":"Comput Optim Appl"},{"issue":"1","key":"569_CR21","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 (1979) On the Shannon capacity of a graph. IEEE Trans Inf Theory 25(1):1\u20137","journal-title":"IEEE Trans Inf Theory"},{"issue":"1","key":"569_CR22","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 (2009) Regularization methods for semidefinite programming. SIAM J Optim 20(1):336\u2013356","journal-title":"SIAM J Optim"},{"key":"569_CR23","volume-title":"Interior-point polynomial algorithms in convex programming, volume\u00a013 of SIAM studies in applied mathematics","author":"Y Nesterov","year":"1994","unstructured":"Nesterov Y, Nemirovskii A (1994) Interior-point polynomial algorithms in convex programming, volume\u00a013 of SIAM studies in applied mathematics. Society for Industrial and Applied Mathematics (SIAM), Philadelphia"},{"key":"569_CR24","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 (2006) A boundary point method to solve semidefinite programs. Computing 78:277\u2013286","journal-title":"Computing"},{"key":"569_CR25","doi-asserted-by":"publisher","first-page":"483","DOI":"10.1007\/978-1-4614-1927-3_17","volume-title":"Mixed integer nonlinear programming","author":"F Rendl","year":"2012","unstructured":"Rendl F (2012) Matrix relaxations in combinatorial optimization. In: Lee J, Leyffer S (eds) Mixed integer nonlinear programming. Springer, New York, pp 483\u2013511"},{"key":"569_CR26","doi-asserted-by":"publisher","first-page":"882","DOI":"10.1137\/140964357","volume":"25","author":"D Sun","year":"2015","unstructured":"Sun D, Toh K-C, Yang L (2015) A convergent 3-block semiproximal alternating direction method of multipliers for conic programming with 4-type constraints. SIAM J Optim 25:882\u2013915","journal-title":"SIAM J Optim"},{"issue":"3","key":"569_CR27","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 (2010) Alternating direction augmented Lagrangian methods for semidefinite programming. Math Program Comput 2(3):203\u2013230","journal-title":"Math Program Comput"},{"issue":"1","key":"569_CR28","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1007\/s10589-022-00355-1","volume":"82","author":"A Wiegele","year":"2022","unstructured":"Wiegele A, Zhao S (2022) SDP-based bounds for graph partition via extended ADMM. Comput Optim Appl 82(1):251\u2013291","journal-title":"Comput Optim Appl"},{"issue":"3","key":"569_CR29","doi-asserted-by":"publisher","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 (2015) SDPNAL+: a majorized semismooth Newton-CG augmented Lagrangian method for semidefinite programming with nonnegative constraints. Math Program Comput 7(3):331\u2013366","journal-title":"Math Program Comput"}],"container-title":["4OR"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10288-024-00569-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10288-024-00569-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10288-024-00569-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,31]],"date-time":"2025-03-31T00:47:38Z","timestamp":1743382058000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10288-024-00569-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,4,25]]},"references-count":29,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,3]]}},"alternative-id":["569"],"URL":"https:\/\/doi.org\/10.1007\/s10288-024-00569-5","relation":{},"ISSN":["1619-4500","1614-2411"],"issn-type":[{"value":"1619-4500","type":"print"},{"value":"1614-2411","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,4,25]]},"assertion":[{"value":"13 November 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 November 2023","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 March 2024","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 April 2024","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no Conflict of interest","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}