{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,26]],"date-time":"2026-05-26T14:07:08Z","timestamp":1779804428718,"version":"3.53.1"},"reference-count":69,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2025,12,6]],"date-time":"2025-12-06T00:00:00Z","timestamp":1764979200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,12,6]],"date-time":"2025-12-06T00:00:00Z","timestamp":1764979200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Prog. Comp."],"published-print":{"date-parts":[[2026,6]]},"abstract":"Abstract<\/jats:title>\n \n The Lov\u00e1sz theta function\n \n \n $$\\theta (G)$$<\/jats:tex-math>\n \n \n \u03b8<\/mml:mi>\n (<\/mml:mo>\n G<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n provides a very good upper bound on the stability number of a graph\n G<\/jats:italic>\n . It can be computed in polynomial time by solving a semidefinite program (SDP), which also turns out to be fairly tractable in practice. Consequently,\n \n \n $$\\theta (G)$$<\/jats:tex-math>\n \n \n \u03b8<\/mml:mi>\n (<\/mml:mo>\n G<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n achieves a hard-to-beat trade-off between computational effort and strength of the bound. Indeed, several attempts to improve the theta bound are documented, mainly based on playing around the application of the\n \n \n $$N_+(\\cdot )$$<\/jats:tex-math>\n \n \n \n N<\/mml:mi>\n +<\/mml:mo>\n <\/mml:msub>\n \n (<\/mml:mo>\n \u00b7<\/mml:mo>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n lifting operator of Lov\u00e1sz and Schrijver to the classical formulation of the maximum stable set problem (SSP). Experience shows that solving such SDPs often struggles against practical intractability and requires highly specialized methods. We investigate the application of such an operator to two different linear formulations of the SSP based on clique and nodal inequalities, respectively. These two formulations are described by fewer inequalities than the natural formulation based on edge inequalities, yet they guarantee that the resulting SDP bound is at least as strong as\n \n \n $$\\theta (G)$$<\/jats:tex-math>\n \n \n \u03b8<\/mml:mi>\n (<\/mml:mo>\n G<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n . Our computational experience, including larger graphs than those previously documented, shows that upper bounds stronger than\n \n \n $$\\theta (G)$$<\/jats:tex-math>\n \n \n \u03b8<\/mml:mi>\n (<\/mml:mo>\n G<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n can be accessed by a reasonable additional effort using the clique-based formulation on sparse graphs and the nodal-based one on dense graphs.\n <\/jats:p>","DOI":"10.1007\/s12532-025-00298-8","type":"journal-article","created":{"date-parts":[[2025,12,6]],"date-time":"2025-12-06T07:13:20Z","timestamp":1765005200000},"page":"443-480","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Application of the Lov\u00e1sz-Schrijver Operator to Compact Stable Set Integer Programs"],"prefix":"10.1007","volume":"18","author":[{"given":"Federico","family":"Battista","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Fabrizio","family":"Rossi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Stefano","family":"Smriglio","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2025,12,6]]},"reference":[{"key":"298_CR1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-024-02093-0","author":"YH Au","year":"2024","unstructured":"Au, Y.H., Tun\u00e7el, L.: Stable set polytopes with high lift-and-project ranks for the Lov\u00e1sz-Schrijver SDP operator. Math. Program. ser. A (2024). https:\/\/doi.org\/10.1007\/s10107-024-02093-0","journal-title":"Math. Program. ser. A"},{"issue":"4","key":"298_CR2","first-page":"710","volume":"18","author":"E Balas","year":"1976","unstructured":"Balas, E., Padberg, M.W.: Set partitioning: A survey. SIAM review 18(4), 710\u2013760 (1976)","journal-title":"Set partitioning: A survey. SIAM review"},{"key":"298_CR3","doi-asserted-by":"crossref","unstructured":"Balas, E., Ceria, S., Cornuejols, G., Pataki, G.: Polyhedral methods for the maximum clique problem. DIMACS, Ser. Discrete Math. Theor. Comput. Sci. (1994)","DOI":"10.21236\/ADA298925"},{"key":"298_CR4","unstructured":"Battista, F.: On semidefinite lift-and-project of combinatorial optimization problems. PhD thesis, Universit\u00e0 di Roma Sapienza, (2023)"},{"key":"298_CR5","doi-asserted-by":"publisher","unstructured":"Battista, F., De\u00a0Santis, M.: Dealing with inequality constraints in large-scale semidefinite relaxations for graph coloring and maximum clique problems. 4OR. A Quarterly Journal of Operations Research, pages 1\u201331, (2024). https:\/\/doi.org\/10.1007\/s10288-024-00569-5","DOI":"10.1007\/s10288-024-00569-5"},{"key":"298_CR6","doi-asserted-by":"publisher","unstructured":"Bianchi, S.M., Escalante, M., Nasini, G.L., Tun\u00e7el, L.: Some advances on Lov\u00e1sz\u2013Schrijver semidefinite programming relaxations of the fractional stable set polytope. Discrete Applied Mathematics, 164: 460\u2013469, Feb. (2014). ISSN 0166-218X. https:\/\/doi.org\/10.1016\/j.dam.2013.03.028. https:\/\/www.sciencedirect.com\/science\/article\/pii\/S0166218X13001765","DOI":"10.1016\/j.dam.2013.03.028"},{"key":"298_CR7","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1007\/s10107-016-1035-1","volume":"162","author":"SM Bianchi","year":"2017","unstructured":"Bianchi, S.M., Escalante, M., Nasini, G.L., Tun\u00e7el, L.: Lov\u00e1sz-Schrijver SDP-operator, near-perfect graphs and near-bipartite graphs. Math. Program. 162, 201\u2013223 (2017)","journal-title":"Math. Program."},{"key":"298_CR8","doi-asserted-by":"publisher","first-page":"70","DOI":"10.1016\/j.dam.2023.01.012","volume":"332","author":"SM Bianchi","year":"2023","unstructured":"Bianchi, S.M., Escalante, M.S., Nasini, G.L., Wagler, A.K.: Lov\u00e1sz-Schrijver PSD-operator and the stable set polytope of claw-free graphs. Discret. Appl. Math. 332, 70\u201386 (2023)","journal-title":"Discret. Appl. Math."},{"issue":"2","key":"298_CR9","doi-asserted-by":"publisher","first-page":"420","DOI":"10.1016\/j.ejor.2016.07.057","volume":"257","author":"M Bodur","year":"2017","unstructured":"Bodur, M., Dash, S., G\u00fcnl\u00fck, O.: A new lift-and-project operator. Eur. J. Oper. Res. 257(2), 420\u2013428 (2017)","journal-title":"Eur. J. Oper. Res."},{"key":"298_CR10","doi-asserted-by":"crossref","unstructured":"Bomze, I.M., Budinich, M., Pardalos, P.M., Pelillo, M.: The maximum clique problem. Handbook of Combinatorial Optimization: Supplement Volume A, pages 1\u201374, (1999)","DOI":"10.1007\/978-1-4757-3023-4_1"},{"key":"298_CR11","unstructured":"Bornd\u00f6rfer, R.: Aspects of set packing, partitioning, and covering. PhD thesis, Technischen Universit\u00e4t Berlin, (1998)"},{"issue":"3","key":"298_CR12","doi-asserted-by":"publisher","first-page":"726","DOI":"10.1137\/040609574","volume":"16","author":"S Burer","year":"2006","unstructured":"Burer, S., Vandenbussche, D.: Solving lift-and-project relaxations of binary integer programs. SIAM J. Optim. 16(3), 726\u2013750 (2006)","journal-title":"SIAM J. Optim."},{"issue":"4","key":"298_CR13","doi-asserted-by":"publisher","first-page":"460","DOI":"10.1016\/j.disc.2006.01.004","volume":"306","author":"S Busygin","year":"2006","unstructured":"Busygin, S., Pasechnik, D.V.: On NP-hardness of the clique partition-independence number gap recognition and related problems. Discret. Math. 306(4), 460\u2013463 (2006)","journal-title":"Discret. Math."},{"issue":"4","key":"298_CR14","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.112.040401","volume":"112","author":"A Cabello","year":"2014","unstructured":"Cabello, A., Severini, S., Winter, A.: Graph-theoretic approach to quantum correlations. Phys. Rev. Lett. 112(4), 040401 (2014)","journal-title":"Phys. Rev. Lett."},{"issue":"4","key":"298_CR15","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1016\/S0167-6377(00)00056-0","volume":"27","author":"L C\u00e1novas","year":"2000","unstructured":"C\u00e1novas, L., Landete, M., Mar\u0131N, A.: New facets for the set packing polytope. Oper. Res. Lett. 27(4), 153\u2013161 (2000)","journal-title":"Oper. Res. Lett."},{"issue":"2\u20133","key":"298_CR16","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/S0166-218X(99)00050-5","volume":"92","author":"A Caprara","year":"1999","unstructured":"Caprara, A., Gonz\u00e1lez, J.J.S.: Separating lifted odd-hole inequalities to solve the index selection problem. Discret. Appl. Math. 92(2\u20133), 111\u2013134 (1999)","journal-title":"Discret. Appl. Math."},{"key":"298_CR17","first-page":"415","volume":"19","author":"M Cerulli","year":"2021","unstructured":"Cerulli, M., De Santis, M., Gaar, E., Wiegele, A.: Improving ADMMs for solving doubly nonnegative programs through dual factorization. 4OR. A Quarterly Journal of Operations Research 19, 415\u2013448 (2021)","journal-title":"A Quarterly Journal of Operations Research"},{"key":"298_CR18","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-11008-0","volume-title":"Integer programming models","author":"M Conforti","year":"2014","unstructured":"Conforti, M., Cornu\u00e9jols, G., Zambelli, G., Conforti, M., Cornu\u00e9jols, G., Zambelli, G.: Integer programming models. Springer, Heidelberg (2014)"},{"issue":"2","key":"298_CR19","doi-asserted-by":"publisher","first-page":"1006","DOI":"10.1287\/ijoc.2021.1115","volume":"34","author":"S Coniglio","year":"2022","unstructured":"Coniglio, S., Gualandi, S.: Optimizing over the closure of rank inequalities with a small right-hand side for the maximum stable set problem via bilevel programming. INFORMS J. Comput. 34(2), 1006\u20131023 (2022)","journal-title":"INFORMS J. Comput."},{"key":"298_CR20","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1016\/j.dam.2017.02.005","volume":"245","author":"RC Corr\u00eaa","year":"2018","unstructured":"Corr\u00eaa, R.C., Delle Donne, D., Koch, I., Marenco, J.: General cut-generating procedures for the stable set polytope. Discrete Applied Mathematics 245, 28\u201341 (2018)","journal-title":"Discrete Applied Mathematics"},{"key":"298_CR21","volume-title":"On the matrix cuts of Lov\u00e1sz and Schrijver and their use in Integer Programming","author":"S Dash","year":"2001","unstructured":"Dash, S.: On the matrix cuts of Lov\u00e1sz and Schrijver and their use in Integer Programming. Rice University, Houston, TX (2001)"},{"issue":"3","key":"298_CR22","doi-asserted-by":"publisher","first-page":"555","DOI":"10.1016\/0377-2217(94)90252-6","volume":"73","author":"F Della Croce","year":"1994","unstructured":"Della Croce, F., Tadei, R.: A multi-KP modeling for the maximum-clique problem. Eur. J. Oper. Res. 73(3), 555\u2013561 (1994)","journal-title":"Eur. J. Oper. Res."},{"issue":"2\u20133","key":"298_CR23","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1007\/s10107-006-0026-z","volume":"109","author":"I Dukanovic","year":"2007","unstructured":"Dukanovic, I., Rendl, F.: Semidefinite programming relaxations for graph coloring and maximal clique problems. Math. Program. 109(2\u20133), 345\u2013365 (2007)","journal-title":"Math. Program."},{"issue":"1\u20132","key":"298_CR24","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1007\/s10107-020-01512-2","volume":"183","author":"E Gaar","year":"2020","unstructured":"Gaar, E., Rendl, F.: A computational study of exact subgraph based SDP bounds for Max-Cut, stable set and coloring. Math. Program. 183(1\u20132), 283\u2013308 (2020)","journal-title":"Math. Program."},{"issue":"1","key":"298_CR25","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1007\/s00186-022-00773-1","volume":"95","author":"E Gaar","year":"2022","unstructured":"Gaar, E., Siebenhofer, M., Wiegele, A.: An SDP-based approach for computing the stability number of a graph. Math. Methods Oper. Res. 95(1), 141\u2013161 (2022)","journal-title":"Math. Methods Oper. Res."},{"key":"298_CR26","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1016\/j.disopt.2017.04.001","volume":"25","author":"L Galli","year":"2017","unstructured":"Galli, L., Letchford, A.N.: On the lov\u00e1sz theta function and some variants. Discret. Optim. 25, 159\u2013174 (2017)","journal-title":"Discret. Optim."},{"key":"298_CR27","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1007\/s10107-005-0604-5","volume":"106","author":"M Giandomenico","year":"2006","unstructured":"Giandomenico, M., Letchford, A.N.: Exploring the relationship between max-cut and stable set relaxations. Math. Program. 106, 159\u2013175 (2006)","journal-title":"Math. Program."},{"key":"298_CR28","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, A.N., Rossi, F., Smriglio, S.: An application of the Lov\u00e1sz-Schrijver $$M(K, K)$$ operator to the stable set problem. Math. Program. 120, 381\u2013401 (2009)","journal-title":"Math. Program."},{"key":"298_CR29","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1016\/j.endm.2013.05.088","volume":"41","author":"M Giandomenico","year":"2013","unstructured":"Giandomenico, M., Letchford, A.N., Rossi, F., Smriglio, S.: Approximating the Lov\u00e1sz $$\\theta $$ function with the subgradient method. Electron. Notes Discret. Math. 41, 157\u2013164 (2013)","journal-title":"Electron. Notes Discret. Math."},{"key":"298_CR30","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.: Strong lift-and-project cutting planes for the stable set problem. Math. Program. 141, 165\u2013192 (2013)","journal-title":"Math. Program."},{"issue":"3","key":"298_CR31","doi-asserted-by":"publisher","first-page":"1944","DOI":"10.1137\/140966332","volume":"25","author":"M Giandomenico","year":"2015","unstructured":"Giandomenico, M., Letchford, A.N., Rossi, F., Smriglio, S.: Ellipsoidal relaxations of the stable set problem: theory and algorithms. SIAM J. Optim. 25(3), 1944\u20131963 (2015)","journal-title":"SIAM J. Optim."},{"issue":"26","key":"298_CR32","doi-asserted-by":"publisher","first-page":"796","DOI":"10.1287\/moor.26.4.796.10012","volume":"4","author":"MX Goemans","year":"2001","unstructured":"Goemans, M.X., Tuncel, L.: When does the positive semidefiniteness constraint help in lifting procedures? Math. Oper. Res. 4(26), 796\u2013815 (2001)","journal-title":"Math. Oper. Res."},{"key":"298_CR33","volume-title":"Geometric algorithms and combinatorial optimization","author":"M Gr\u00f6tschel","year":"2012","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: Geometric algorithms and combinatorial optimization, vol. 2. Springer Science & Business Media, Heidelberg (2012)"},{"issue":"4","key":"298_CR34","doi-asserted-by":"publisher","first-page":"1014","DOI":"10.1137\/S1052623401394092","volume":"13","author":"G Gruber","year":"2003","unstructured":"Gruber, G., Rendl, F.: Computational experience with stable set relaxations. SIAM J. Optim. 13(4), 1014\u20131028 (2003)","journal-title":"SIAM J. Optim."},{"key":"298_CR35","doi-asserted-by":"crossref","unstructured":"Hastad, J.: Clique is hard to approximate within $$n^{1-\\epsilon }$$. In Proceedings of 37th Conference on Foundations of Computer Science, pages 627\u2013636. IEEE, (1996)","DOI":"10.1109\/SFCS.1996.548522"},{"issue":"1","key":"298_CR36","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1137\/050622870","volume":"46","author":"C Jansson","year":"2008","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 (2008)","journal-title":"SIAM J. Numer. Anal."},{"key":"298_CR37","doi-asserted-by":"crossref","DOI":"10.1090\/dimacs\/026","volume-title":"Cliques, coloring, and satisfiability: second DIMACS implementation challenge, October 11\u201313, 1993","author":"DS Johnson","year":"1996","unstructured":"Johnson, D.S., Trick, M.A.: Cliques, coloring, and satisfiability: second DIMACS implementation challenge, October 11\u201313, 1993, vol. 26. American Mathematical Soc, Providence, RI (1996)"},{"issue":"2","key":"298_CR38","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1007\/BF02579314","volume":"2","author":"F Juh\u00e1sz","year":"1982","unstructured":"Juh\u00e1sz, F.: The asymptotic behaviour of Lov\u00e1sz\u2019 $$\\theta $$ function for random graphs. Combinatorica 2(2), 153\u2013155 (1982)","journal-title":"Combinatorica"},{"key":"298_CR39","doi-asserted-by":"crossref","unstructured":"Letchford, A.N., Marzi, F., Rossi, F., Smriglio, S.: Strengthening Chv\u00e1tal-Gomory cuts for the stable set problem. In International Symposium on Combinatorial Optimization, pages 201\u2013212. Springer, (2016)","DOI":"10.1007\/978-3-319-45587-7_18"},{"key":"298_CR40","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2020.105024","volume":"123","author":"AN Letchford","year":"2020","unstructured":"Letchford, A.N., Rossi, F., Smriglio, S.: The stable set problem: Clique and nodal inequalities revisited. Comput. Oper. Res. 123, 105024 (2020)","journal-title":"Comput. Oper. Res."},{"key":"298_CR41","doi-asserted-by":"publisher","first-page":"511","DOI":"10.1007\/s10107-014-0771-3","volume":"150","author":"M Locatelli","year":"2015","unstructured":"Locatelli, M.: Improving upper bounds for the clique number by non-valid inequalities. Math. Program. 150, 511\u2013525 (2015)","journal-title":"Math. Program."},{"issue":"1","key":"298_CR42","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"},{"issue":"2","key":"298_CR43","doi-asserted-by":"publisher","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\u20131 optimization. SIAM J. Optim. 1(2), 166\u2013190 (1991)","journal-title":"SIAM J. Optim."},{"issue":"1","key":"298_CR44","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":"9","key":"298_CR45","doi-asserted-by":"publisher","first-page":"3013","DOI":"10.1007\/s00500-019-03769-y","volume":"23","author":"F Marzi","year":"2019","unstructured":"Marzi, F., Rossi, F., Smriglio, S.: Computational study of separation algorithms for clique inequalities. Soft. Comput. 23(9), 3013\u20133027 (2019)","journal-title":"Soft. Comput."},{"issue":"1","key":"298_CR46","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1007\/BF01580665","volume":"10","author":"GP McCormick","year":"1976","unstructured":"McCormick, G.P.: Computability of global solutions to factorable nonconvex programs: Part I-Convex underestimating problems. Math. Program. 10(1), 147\u2013175 (1976)","journal-title":"Math. Program."},{"key":"298_CR47","unstructured":"MOSEK. The mosek optimization toolbox for matlab manual. version 9.0, (2019). http:\/\/docs.mosek.com\/9.0\/toolbox\/index.html"},{"issue":"3","key":"298_CR48","doi-asserted-by":"publisher","first-page":"598","DOI":"10.1016\/S0377-2217(96)00175-0","volume":"101","author":"AT Murray","year":"1997","unstructured":"Murray, A.T., Church, R.L.: Facets for node packing. Eur. J. Oper. Res. 101(3), 598\u2013608 (1997)","journal-title":"Eur. J. Oper. Res."},{"issue":"5","key":"298_CR49","doi-asserted-by":"publisher","first-page":"443","DOI":"10.1057\/jors.1992.71","volume":"43","author":"GL Nemhauser","year":"1992","unstructured":"Nemhauser, G.L., Sigismondi, G.: A strong cutting plane\/branch-and-bound algorithm for node packing. J. Oper. Res. Soc. 43(5), 443\u2013457 (1992)","journal-title":"J. Oper. Res. Soc."},{"key":"298_CR50","volume-title":"Integer and combinatorial optimization","author":"GL Nemhauser","year":"1999","unstructured":"Nemhauser, G.L., Wolsey, L.A.: Integer and combinatorial optimization, vol. 55. John Wiley & Sons, Hoboken, NJ (1999)"},{"key":"298_CR51","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611970791","volume-title":"Interior-point polynomial algorithms in convex programming","author":"Y Nesterov","year":"1994","unstructured":"Nesterov, Y., Nemirovskii, A.: Interior-point polynomial algorithms in convex programming. SIAM, Philadelphia, PA (1994)"},{"issue":"1\u20133","key":"298_CR52","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1016\/S0166-218X(01)00290-6","volume":"120","author":"PR \u00d6sterg\u00e5rd","year":"2002","unstructured":"\u00d6sterg\u00e5rd, P.R.: A fast algorithm for the maximum clique problem. Discret. Appl. Math. 120(1\u20133), 197\u2013207 (2002)","journal-title":"Discret. Appl. Math."},{"issue":"1","key":"298_CR53","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1007\/BF01580121","volume":"5","author":"MW Padberg","year":"1973","unstructured":"Padberg, M.W.: On the facial structure of set packing polyhedra. Math. Program. 5(1), 199\u2013215 (1973)","journal-title":"Math. Program."},{"key":"298_CR54","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, 277\u2013286 (2006)","journal-title":"Computing"},{"key":"298_CR55","doi-asserted-by":"publisher","first-page":"434","DOI":"10.1007\/s10878-009-9264-3","volume":"21","author":"S Rebennack","year":"2011","unstructured":"Rebennack, S., Oswald, M., Theis, D.O., Seitz, H., Reinelt, G., Pardalos, P.M.: A branch and cut solver for the maximum stable set problem. J. Comb. Optim. 21, 434\u2013457 (2011)","journal-title":"J. Comb. Optim."},{"issue":"2","key":"298_CR56","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1016\/S0167-6377(00)00060-2","volume":"28","author":"F Rossi","year":"2001","unstructured":"Rossi, F., Smriglio, S.: A branch-and-cut algorithm for the maximum cardinality stable set problem. Oper. Res. Lett. 28(2), 63\u201374 (2001)","journal-title":"Oper. Res. Lett."},{"issue":"2","key":"298_CR57","doi-asserted-by":"publisher","first-page":"400","DOI":"10.1016\/S0377-2217(00)00064-3","volume":"131","author":"F Rossi","year":"2001","unstructured":"Rossi, F., Smriglio, S.: A set packing model for the ground holding problem in congested networks. Eur. J. Oper. Res. 131(2), 400\u2013416 (2001)","journal-title":"Eur. J. Oper. Res."},{"issue":"2","key":"298_CR58","doi-asserted-by":"publisher","first-page":"571","DOI":"10.1016\/j.cor.2010.07.019","volume":"38","author":"P San Segundo","year":"2011","unstructured":"San Segundo, P., Rodr\u00edguez-Losada, D., Jim\u00e9nez, A.: An exact bit-parallel algorithm for the maximum clique problem. Comput. Oper. Res. 38(2), 571\u2013581 (2011)","journal-title":"Comput. Oper. Res."},{"issue":"4","key":"298_CR59","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1109\/TIT.1979.1056072","volume":"25","author":"A Schrijver","year":"1979","unstructured":"Schrijver, A.: A comparison of the Delsarte and Lov\u00e1sz bounds. IEEE Trans. Inf. Theory 25(4), 425\u2013429 (1979)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"1\u20134","key":"298_CR60","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). https:\/\/doi.org\/10.1080\/10556789908805766","journal-title":"Optim. Methods Softw."},{"issue":"1","key":"298_CR61","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1080\/10556788.2019.1576176","volume":"35","author":"D Sun","year":"2020","unstructured":"Sun, D., Toh, K.-C., Yuan, Y., Zhao, X.-Y.: SDPNAL+: A Matlab software for semidefinite programming with bound constraints. Optim. Methods Softw. 35(1), 87\u2013115 (2020)","journal-title":"Optim. Methods Softw."},{"key":"298_CR62","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1007\/s10898-006-9039-7","volume":"37","author":"E Tomita","year":"2007","unstructured":"Tomita, E., Kameda, T.: An efficient branch-and-bond algorithm for finding a maximum clique with computational experiments. J. Global Optim. 37, 95\u2013111 (2007)","journal-title":"J. Global Optim."},{"issue":"4","key":"298_CR63","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1016\/0012-365X(75)90077-1","volume":"12","author":"LE Trotter Jr","year":"1975","unstructured":"Trotter, L.E., Jr.: A class of facet producing graphs for vertex packing polyhedra. Discret. Math. 12(4), 373\u2013388 (1975)","journal-title":"Discret. Math."},{"key":"298_CR64","doi-asserted-by":"publisher","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, 189\u2013217 (2003)","journal-title":"Math. Program."},{"issue":"3","key":"298_CR65","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), 203\u2013230 (2010)","journal-title":"Math. Program. Comput."},{"issue":"1","key":"298_CR66","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.: Sdp-based bounds for graph partition via extended admm. Comput. Optim. Appl. 82(1), 251\u2013291 (2022)","journal-title":"Comput. Optim. Appl."},{"key":"298_CR67","unstructured":"Wilson, A.T.: Applying the boundary point method to an SDP relaxation of the maximum independent set problem for a branch and bound algorithm. PhD thesis, New Mexico Institute of Mining and Technology, (2009)"},{"issue":"3","key":"298_CR68","doi-asserted-by":"publisher","first-page":"693","DOI":"10.1016\/j.ejor.2014.09.064","volume":"242","author":"Q Wu","year":"2015","unstructured":"Wu, Q., Hao, J.-K.: A review on algorithms for maximum clique problems. Eur. J. Oper. Res. 242(3), 693\u2013709 (2015)","journal-title":"Eur. J. Oper. Res."},{"issue":"2\u20133","key":"298_CR69","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1007\/s10589-005-3060-5","volume":"33","author":"EA Yildirim","year":"2006","unstructured":"Yildirim, E.A., Fan-Orzechowski, X.: On extracting maximum stable sets in perfect graphs using Lov\u00e1sz\u2019s theta function. Comput. Optim. Appl. 33(2\u20133), 229\u2013247 (2006)","journal-title":"Comput. Optim. Appl."}],"container-title":["Mathematical Programming Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s12532-025-00298-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s12532-025-00298-8","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s12532-025-00298-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,26]],"date-time":"2026-05-26T13:02:35Z","timestamp":1779800555000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s12532-025-00298-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,12,6]]},"references-count":69,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,6]]}},"alternative-id":["298"],"URL":"https:\/\/doi.org\/10.1007\/s12532-025-00298-8","relation":{},"ISSN":["1867-2949","1867-2957"],"issn-type":[{"value":"1867-2949","type":"print"},{"value":"1867-2957","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,12,6]]},"assertion":[{"value":"1 July 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 November 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 December 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 February 2026","order":5,"name":"change_date","label":"Change Date","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Update","order":6,"name":"change_type","label":"Change Type","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"In this article, there were several spacing and alignment errors. This has been corrected.","order":7,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflicts of Interest"}}]}}