{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,17]],"date-time":"2026-02-17T11:53:52Z","timestamp":1771329232071,"version":"3.50.1"},"reference-count":37,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2012,1,21]],"date-time":"2012-01-21T00:00:00Z","timestamp":1327104000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2013,10]]},"DOI":"10.1007\/s10107-012-0513-3","type":"journal-article","created":{"date-parts":[[2012,1,20]],"date-time":"2012-01-20T02:32:37Z","timestamp":1327026757000},"page":"165-192","source":"Crossref","is-referenced-by-count":21,"title":["Strong lift-and-project cutting planes for the stable set problem"],"prefix":"10.1007","volume":"141","author":[{"given":"Monia","family":"Giandomenico","sequence":"first","affiliation":[]},{"given":"Fabrizio","family":"Rossi","sequence":"additional","affiliation":[]},{"given":"Stefano","family":"Smriglio","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2012,1,21]]},"reference":[{"key":"513_CR1","volume-title":"The Traveling Salesman Problem: A Computational Study","author":"D.L. Applegate","year":"2007","unstructured":"Applegate D.L., Bixby R.E., Chv\u00e0 \u00e0tal V., Cook W.J.: The Traveling Salesman Problem: A Computational Study. Princeton University Press, Princeton (2007)"},{"key":"513_CR2","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1007\/BF01581273","volume":"112","author":"E. Balas","year":"1993","unstructured":"Balas E., Ceria S., Cornu\u00e9jols G.: A lift-and-project cutting plane algorithm for mixed 0\u20131 programs. Math. Program. 112, 295\u2013324 (1993)","journal-title":"Math. Program."},{"key":"513_CR3","unstructured":"Balas, E., Ceria S., Cornu\u00e9jols, G.E., Pataki, G.: Polyhedral methods for the maximum clique problem. In: Johnson, D.S., Trick, M.A. (eds.) Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, October 11\u201313, 1993, Providence (1996)"},{"key":"513_CR4","doi-asserted-by":"crossref","first-page":"238","DOI":"10.1007\/BF01386316","volume":"4","author":"J.F. Benders","year":"1962","unstructured":"Benders J.F.: Partitioning procedures for solving mixed-variables programming problems. Numerische Mathematik 4, 238\u2013252 (1962)","journal-title":"Numerische Mathematik"},{"key":"513_CR5","doi-asserted-by":"crossref","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. Opt. 16, 726\u2013750 (2006)","journal-title":"SIAM J. Opt."},{"key":"513_CR6","first-page":"348","volume":"77","author":"E. Cheng","year":"1997","unstructured":"Cheng E., Cunningham S.: Wheel inequalities for stable set polytopes. Math. Program. 77, 348\u2013421 (1997)","journal-title":"Math. Program."},{"key":"513_CR7","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1007\/s101070100267","volume":"92","author":"E. Cheng","year":"2002","unstructured":"Cheng E., De Vries S.: Antiweb-wheel inequalities and their separation problems over the stable set polytopes. Math. Program. 92, 153\u2013175 (2002)","journal-title":"Math. Program."},{"key":"513_CR8","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/s10107-006-0086-0","volume":"112","author":"G. Cornu\u00e9jols","year":"2008","unstructured":"Cornu\u00e9jols G.: Valid inequalities for mixed integer linear programs. Math. Program. Ser. B 112, 3\u201344 (2008)","journal-title":"Math. Program. Ser. B"},{"key":"513_CR9","doi-asserted-by":"crossref","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, 345\u2013365 (2007)","journal-title":"Math. Program."},{"key":"513_CR10","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1007\/s10107-010-0365-7","volume":"124","author":"M. Fischetti","year":"2008","unstructured":"Fischetti M., Salvagnin D., Zanette A.: On the Selection of Benders\u2019 cuts. Math. Program. Ser. B 124, 175\u2013182 (2008)","journal-title":"Math. Program. Ser. B"},{"key":"513_CR11","doi-asserted-by":"crossref","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":"513_CR12","doi-asserted-by":"crossref","first-page":"381","DOI":"10.1007\/s10107-008-0219-8","volume":"120\/2","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. Ser. A 120\/2, 381\u2013401 (2009)","journal-title":"Math. Program. Ser. A"},{"key":"513_CR13","doi-asserted-by":"crossref","unstructured":"Giandomenico, M., Letchford, A.N., Rossi, F., Smriglio, S.: A new approach to the stable set problem based on ellipsoids. Accepted for presentation at IPCO XV (2011)","DOI":"10.1007\/978-3-642-20807-2_18"},{"key":"513_CR14","unstructured":"Giandomenico, M., Rossi, F., Smriglio, S.: Implementing separation heuristics for clique inequalities, working paper"},{"key":"513_CR15","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-97881-4","volume-title":"Geometric Algorithms and Combinatorial Optimization","author":"M. Gr\u00f6tschel","year":"1988","unstructured":"Gr\u00f6tschel M., Lov\u00e1sz L., Schrijver A.J.: Geometric Algorithms and Combinatorial Optimization. Springer, New York (1988)"},{"key":"513_CR16","doi-asserted-by":"crossref","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. Opt. 13, 1014\u20131028 (2003)","journal-title":"SIAM J. Opt."},{"key":"513_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, 105\u2013142 (1999)","journal-title":"Acta Math."},{"issue":"6","key":"513_CR18","doi-asserted-by":"crossref","first-page":"657","DOI":"10.1287\/mnsc.39.6.657","volume":"39","author":"K.L. Hoffman","year":"1993","unstructured":"Hoffman K.L., Padberg M.: Solving airline crew scheduling problems by branch-and-cut. Manage. Sci. 39(6), 657\u2013682 (1993)","journal-title":"Manage. Sci."},{"key":"513_CR19","volume-title":"Cliques, Coloring and Satisfiability: The 2nd DIMACS Implementation Challenge","year":"1996","unstructured":"Johnson, D.S., Trick, M.A. (eds.): Cliques, Coloring and Satisfiability: The 2nd DIMACS Implementation Challenge. American Mathematical Society, Providence (1996)"},{"key":"513_CR20","doi-asserted-by":"crossref","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 \u03b8 function for random graphs. Combinatorica 2, 153\u2013155 (1982)","journal-title":"Combinatorica"},{"key":"513_CR21","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. Theor. 25, 1\u20137 (1979)","journal-title":"IEEE Trans. Inf. Theor."},{"key":"513_CR22","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.J.: Cones of matrices and set-functions and 0\u20131 optimization. SIAM J. Opt. 1, 166\u2013190 (1991)","journal-title":"SIAM J. Opt."},{"key":"513_CR23","doi-asserted-by":"crossref","unstructured":"Malik, J., Pohv, J., Rendl, F., Wiegele, A.: Regularization methods for semidefinite programming. SIAM J. Opt. 20\/1 (2009)","DOI":"10.1137\/070704575"},{"key":"513_CR24","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1007\/BF01299447","volume":"3","author":"C. Mannino","year":"1994","unstructured":"Mannino C., Sassano A.: An exact algorithm for the maximum stable set problem. Comput. Optim. Appl. 3, 243\u2013258 (1994)","journal-title":"Comput. Optim. Appl."},{"key":"513_CR25","unstructured":"Mannino, C., Sassano, A.: Edge projection and the maximum cardinality stable set problem. In: Johnson, D.S., Trick, M.A. (eds.) Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, October 11\u201413, 1993, Providence (1996)"},{"key":"513_CR26","doi-asserted-by":"crossref","first-page":"443","DOI":"10.1057\/jors.1992.71","volume":"43","author":"G.L. 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, 443\u2013457 (1992)","journal-title":"J. Oper. Res. Soc."},{"key":"513_CR27","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1007\/BF01580121","volume":"5","author":"M.W. Padberg","year":"1973","unstructured":"Padberg M.W.: On the facial structure of set packing polyhedra. Math. Program. 5, 199\u2013215 (1973)","journal-title":"Math. Program."},{"key":"513_CR28","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1007\/s00607-006-0182-2","volume":"78","author":"J. Pohv","year":"2006","unstructured":"Pohv J., Rendl F., Wiegele A.: A boundary point method to solve semidefinite programs. Computing 78, 277\u2013286 (2006)","journal-title":"Computing"},{"key":"513_CR29","doi-asserted-by":"crossref","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. doi: 10.1007\/s10878-008-9175-8","DOI":"10.1007\/s10878-008-9175-8"},{"key":"513_CR30","unstructured":"Repository. ftp:\/\/dimacs.rutgers.edu\/pub\/challenge\/graph\/benchmarks\/clique"},{"issue":"2","key":"513_CR31","doi-asserted-by":"crossref","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":"4","key":"513_CR32","doi-asserted-by":"crossref","first-page":"438","DOI":"10.1287\/ijoc.10.4.438","volume":"10","author":"E.C. Sewell","year":"1998","unstructured":"Sewell E.C.: A branch and bound algorithm for the stability number of a sparse graph. INFORMS J. Comput. 10(4), 438\u2013447 (1998)","journal-title":"INFORMS J. Comput."},{"key":"513_CR33","doi-asserted-by":"crossref","first-page":"411","DOI":"10.1137\/0403036","volume":"3","author":"H.D. 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. Discret. Math. 3, 411\u2013430 (1990)","journal-title":"SIAM J. Discret. Math."},{"key":"513_CR34","doi-asserted-by":"crossref","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-bound algorithm for finding a maximum clique, with computational experiments. J. Glob. Opt. 37, 95\u2013111 (2007)","journal-title":"J. Glob. Opt."},{"key":"513_CR35","doi-asserted-by":"crossref","first-page":"373","DOI":"10.1016\/0012-365X(75)90077-1","volume":"12","author":"L.E. Trotter","year":"1975","unstructured":"Trotter L.E.: A class of facet-producing graphs for vertex packing polyhedra. Discret. Math. 12, 373\u2013388 (1975)","journal-title":"Discret. Math."},{"key":"513_CR36","unstructured":"Website. http:\/\/www.math.uni-klu.ac.at\/or\/Software\/software.html"},{"key":"513_CR37","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, Master thesis, New Mexico Institute of mining and technology (2009)"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-012-0513-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-012-0513-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-012-0513-3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,22]],"date-time":"2019-06-22T14:44:41Z","timestamp":1561214681000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-012-0513-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,1,21]]},"references-count":37,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2013,10]]}},"alternative-id":["513"],"URL":"https:\/\/doi.org\/10.1007\/s10107-012-0513-3","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,1,21]]}}}