{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,26]],"date-time":"2026-06-26T02:43:47Z","timestamp":1782441827345,"version":"3.54.5"},"reference-count":44,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2008,7,22]],"date-time":"2008-07-22T00:00:00Z","timestamp":1216684800000},"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":[[2010,2]]},"DOI":"10.1007\/s10107-008-0235-8","type":"journal-article","created":{"date-parts":[[2008,7,21]],"date-time":"2008-07-21T10:29:04Z","timestamp":1216636144000},"page":"307-335","source":"Crossref","is-referenced-by-count":208,"title":["Solving Max-Cut to optimality by intersecting semidefinite and polyhedral relaxations"],"prefix":"10.1007","volume":"121","author":[{"given":"Franz","family":"Rendl","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Giovanni","family":"Rinaldi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Angelika","family":"Wiegele","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2008,7,22]]},"reference":[{"key":"235_CR1","unstructured":"Achterberg, T.: Constraint integer programming. PhD thesis, Technische Universit\u00e4t Berlin. http:\/\/opus.kobv.de\/tuberlin\/volltexte\/2007\/1611\/ (2007)"},{"issue":"1","key":"235_CR2","doi-asserted-by":"crossref","first-page":"42","DOI":"10.1016\/j.orl.2004.04.002","volume":"33","author":"T. Achterberg","year":"2005","unstructured":"Achterberg T., Koch T., Martin A.: Branching rules revisited. Oper. Res. Lett. 33(1), 42\u201354 (2005)","journal-title":"Oper. Res. Lett."},{"key":"235_CR3","unstructured":"Armbruster, M.: Branch-and-Cut for a semidefinite relaxation of the minimum bisection problem. PhD thesis, University of Technology Chemnitz (2007)"},{"issue":"1","key":"235_CR4","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1051\/ro:2006010","volume":"40","author":"F. Barahona","year":"2006","unstructured":"Barahona F., Lad\u00e1nyi L.: Branch and cut based on the volume algorithm: Steiner trees in graphs and max-cut. RAIRO Oper. Res. 40(1), 53\u201373 (2006)","journal-title":"RAIRO Oper. Res."},{"issue":"2","key":"235_CR5","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1007\/BF02592023","volume":"36","author":"F. Barahona","year":"1986","unstructured":"Barahona F., Mahjoub A.R.: On the cut polytope. Math. Program. 36(2), 157\u2013173 (1986)","journal-title":"Math. Program."},{"issue":"2, (Ser. A)","key":"235_CR6","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1007\/BF01587084","volume":"44","author":"F. Barahona","year":"1989","unstructured":"Barahona F., J\u00fcnger M., Reinelt G.: Experiments in quadratic 0\u20131 programming. Math. Program. 44(2, (Ser. A)), 127\u2013137 (1989)","journal-title":"Math. Program."},{"issue":"11","key":"235_CR7","doi-asserted-by":"crossref","first-page":"1069","DOI":"10.1057\/jors.1990.166","volume":"41","author":"J.E. Beasley","year":"1990","unstructured":"Beasley J.E.: Or-library: distributing test problems by electronic mail. J. Oper. Res. Soc. 41(11), 1069\u20131072 (1990)","journal-title":"J. Oper. Res. Soc."},{"key":"235_CR8","unstructured":"Beasley, J.E.: Or-library. http:\/\/people.brunel.ac.uk\/~mastjjb\/jeb\/info.html (1990)"},{"key":"235_CR9","unstructured":"Beasley, J.E.: Heuristic algorithms for the unconstrained binary quadratic programming problem. Technical report, The Management School, Imperial College, London SW7 2AZ, England (1998)"},{"key":"235_CR10","doi-asserted-by":"crossref","unstructured":"Benson, S.J., Ye, Y., Zhang, X.: Solving large-scale sparse semidefinite programs for combinatorial optimization. SIAM J. Optim. 10(2), 443\u2013461 (2000, electronic)","DOI":"10.1137\/S1052623497328008"},{"issue":"1, Ser. A","key":"235_CR11","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1007\/s10107-005-0637-9","volume":"109","author":"A. Billionnet","year":"2007","unstructured":"Billionnet A., Elloumi S.: Using a mixed integer quadratic programming solver for the unconstrained quadratic 0\u20131 problem. Math. Program. 109(1, Ser. A), 55\u201368 (2007)","journal-title":"Math. Program."},{"key":"235_CR12","unstructured":"Boros, E., Hammer, P.L., Tavares, G.: The pseudo-boolean optimization. http:\/\/rutcor.rutgers.edu\/~pbo\/ (2005)"},{"issue":"2","key":"235_CR13","doi-asserted-by":"crossref","first-page":"501","DOI":"10.1016\/j.disopt.2007.02.001","volume":"5","author":"E. Boros","year":"2008","unstructured":"Boros E., Hammer P.L., Sun R., Tavares G.: A max-flow approach to improved lower bounds for quadratic unconstrained binary optimization (QUBO). Discrete Optim. 5(2), 501\u2013529 (2008)","journal-title":"Discrete Optim."},{"key":"235_CR14","doi-asserted-by":"crossref","unstructured":"Burer, S., Monteiro, R.D., Zhang, Y.: Rank-two relaxation heuristics for max-cut and other binary quadratic programs. SIAM J. Optim. 12(2), 503\u2013521 (2001\/2002, electronic)","DOI":"10.1137\/S1052623400382467"},{"issue":"1\u20132","key":"235_CR15","doi-asserted-by":"crossref","first-page":"487","DOI":"10.1007\/BF02178370","volume":"80","author":"C. De Simone","year":"1995","unstructured":"De Simone C., Diehl M., J\u00fcnger M., Mutzel P., Reinelt G., Rinaldi G.: Exact ground states of Ising spin glasses: new experimental results with a branch-and-cut algorithm. J. Stat. Phys. 80(1\u20132), 487\u2013496 (1995)","journal-title":"J. Stat. Phys."},{"issue":"3, Ser. A","key":"235_CR16","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. Program. 62(3, Ser. A), 557\u2013574 (1993)","journal-title":"Math. Program."},{"key":"235_CR17","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-04295-9","volume-title":"Geometry of Cuts and Metrics. In: Algorithms and Combinatorics, vol. 15","author":"M.M. Deza","year":"1997","unstructured":"Deza M.M., Laurent M.: Geometry of Cuts and Metrics. In: Algorithms and Combinatorics, vol. 15. Springer, Berlin (1997)"},{"key":"235_CR18","doi-asserted-by":"crossref","unstructured":"Elf, M., Gutwenger, C., J\u00fcnger, M., Rinaldi, G.: Branch-and-Cut Algorithms for Combinatorial Optimization and Their Implementation in ABACUS. In: Lecture Notes in Computer Science, vol. 2241, pp. 157\u2013222. Springer, Heidelberg (2001)","DOI":"10.1007\/3-540-45586-8_5"},{"issue":"2\u20133, Ser. B","key":"235_CR19","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":"2\u20133, Ser. B","key":"235_CR20","doi-asserted-by":"crossref","first-page":"375","DOI":"10.1007\/s10107-005-0620-5","volume":"104","author":"A. Frangioni","year":"2005","unstructured":"Frangioni A., Lodi A., Rinaldi G.: New approaches for optimizing over the semimetric polytope. Math. Program. 104(2\u20133, Ser. B), 375\u2013388 (2005)","journal-title":"Math. Program."},{"issue":"3","key":"235_CR21","doi-asserted-by":"crossref","first-page":"336","DOI":"10.1287\/mnsc.44.3.336","volume":"44","author":"F. Glover","year":"1998","unstructured":"Glover F., Kochenberger G., Alidaee B.: Adaptative memory tabu search for binary quadratic programs. Manage. Sci. 44(3), 336\u2013345 (1998)","journal-title":"Manage. Sci."},{"key":"235_CR22","doi-asserted-by":"crossref","unstructured":"Goemans, M.X., Williamson, D.P.: .878-approximation algorithms for max cut and max 2sat. In: Proceedings of the Twenty-Sixth Annual ACM Symposium on the Theory of Computing, pp. 422\u2013431. Montreal, Quebec, Canada (1994)","DOI":"10.1145\/195058.195216"},{"key":"235_CR23","doi-asserted-by":"crossref","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, preliminary version see [22]","DOI":"10.1145\/227683.227684"},{"key":"235_CR24","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/S0167-5060(08)70343-1","volume":"5","author":"P. Hansen","year":"1979","unstructured":"Hansen P.: Methods of nonlinear 0\u20131 programming. Ann. Discrete Math. 5, 53\u201370 (1979)","journal-title":"Ann. Discrete Math."},{"key":"235_CR25","doi-asserted-by":"crossref","unstructured":"Helmberg, C.: Fixing variables in semidefinite relaxations. SIAM J. Matrix Anal. Appl. 21(3), 952\u2013969 (2000, electronic)","DOI":"10.1137\/S089547989631442X"},{"key":"235_CR26","doi-asserted-by":"crossref","unstructured":"Helmberg, C.: A cutting plane algorithm for large scale semidefinite relaxations. In: The Sharpest Cut, MPS\/SIAM Ser. Optim., pp. 233\u2013256. SIAM, Philadelphia, PA (2004)","DOI":"10.1137\/1.9780898718805.ch15"},{"issue":"3, Ser. A","key":"235_CR27","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1007\/BF01580072","volume":"82","author":"C. Helmberg","year":"1998","unstructured":"Helmberg C., Rendl F.: Solving quadratic (0,1)-problems by semidefinite programs and cutting planes. Math. Program. 82(3, Ser. A), 291\u2013315 (1998)","journal-title":"Math. Program."},{"issue":"2","key":"235_CR28","doi-asserted-by":"crossref","first-page":"342","DOI":"10.1137\/0806020","volume":"6","author":"C. Helmberg","year":"1996","unstructured":"Helmberg C., Rendl F., Vanderbei R.J., Wolkowicz H.: An interior-point method for semidefinite programming. SIAM J. Optim. 6(2), 342\u2013361 (1996)","journal-title":"SIAM J. Optim."},{"issue":"6","key":"235_CR29","doi-asserted-by":"crossref","first-page":"865","DOI":"10.1287\/opre.37.6.865","volume":"37","author":"D.S. 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."},{"key":"235_CR30","unstructured":"J\u00fcnger, M., Reinelt, G., Rinaldi, G.: Lifting and separation procedures for the cut polytope. Technical report, Universit\u00e4t zu K\u00f6ln (2006, in preparation)"},{"key":"235_CR31","doi-asserted-by":"crossref","unstructured":"Karisch, S.E., Rendl, F.: Semidefinite programming and graph equipartition. In: Topics in semidefinite and interior-point methods (Toronto, ON, 1996). In: Fields Inst. Commun., vol. 18, pp. 77\u201395. American Mathematical Society, Providence (1998)","DOI":"10.1090\/fic\/018\/06"},{"issue":"3-4","key":"235_CR32","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1080\/10556780108805819","volume":"15","author":"S. Kim","year":"2001","unstructured":"Kim S., Kojima M.: Second order cone programming relaxation of nonconvex quadratic optimization problems. Optim. Methods Softw. 15(3-4), 201\u2013224 (2001)","journal-title":"Optim. Methods Softw."},{"key":"235_CR33","first-page":"241","volume-title":"Annotated Bibliographies in Combinatorial Optimization","author":"M. Laurent","year":"1997","unstructured":"Laurent M.: The max-cut problem. In: Dell\u2019Amico, M., Maffioli, F., Martello, S.(eds) Annotated Bibliographies in Combinatorial Optimization, pp. 241\u2013259. Wiley, Chichester (1997)"},{"key":"235_CR34","unstructured":"Liers, F.: Contributions to determining exact ground-states of Ising spin-glasses and to their physics. PhD thesis, Universit\u00e4t zu K\u00f6ln (2004)"},{"key":"235_CR35","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1002\/3527603794.ch4","volume-title":"New Optimization Algorithms in Physics","author":"F. Liers","year":"2004","unstructured":"Liers F., J\u00fcnger M., Reinelt G., Rinaldi G.: Computing exact ground states of hard Ising spin glass problems by branch-and-cut. In: Hartmann, A., Rieger, H.(eds) New Optimization Algorithms in Physics, pp. 47\u201368. Wiley, London (2004)"},{"issue":"2","key":"235_CR36","doi-asserted-by":"crossref","first-page":"164","DOI":"10.15807\/jorsj.46.164","volume":"46","author":"M. Muramatsu","year":"2003","unstructured":"Muramatsu M., Suzuki T.: A new second-order cone programming relaxation for MAX-CUT problems. J. Oper. Res. Soc. Jpn 46(2), 164\u2013177 (2003)","journal-title":"J. Oper. Res. Soc. Jpn"},{"issue":"2","key":"235_CR37","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1007\/BF02247879","volume":"45","author":"P.M. Pardalos","year":"1990","unstructured":"Pardalos P.M., Rodgers G.P.: Computational aspects of a branch and bound algorithm for quadratic zero-one programming. Computing 45(2), 131\u2013144 (1990)","journal-title":"Computing"},{"issue":"1\u20134","key":"235_CR38","doi-asserted-by":"crossref","first-page":"271","DOI":"10.1007\/BF02023057","volume":"22","author":"P.M. Pardalos","year":"1990","unstructured":"Pardalos P.M., Rodgers G.P.: Parallel branch and bound algorithms for quadratic zero-one programs on the hypercube architecture. Ann. Oper. Res. 22(1\u20134), 271\u2013292 (1990)","journal-title":"Ann. Oper. Res."},{"issue":"1\u20133","key":"235_CR39","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1016\/0166-218X(94)00155-7","volume":"62","author":"S. Poljak","year":"1995","unstructured":"Poljak S., Rendl F.: Solving the max-cut problem using eigenvalues. Discrete Appl. Math. 62(1\u20133), 249\u2013278 (1995)","journal-title":"Discrete Appl. Math."},{"issue":"3","key":"235_CR40","doi-asserted-by":"crossref","first-page":"467","DOI":"10.1137\/0805024","volume":"5","author":"S. Poljak","year":"1995","unstructured":"Poljak S., Rendl F.: Nonpolyhedral relaxations of graph-bisection problems. SIAM J. Optim. 5(3), 467\u2013487 (1995)","journal-title":"SIAM J. Optim."},{"issue":"3","key":"235_CR41","doi-asserted-by":"crossref","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":"235_CR42","doi-asserted-by":"crossref","unstructured":"Rendl, F., Rinaldi, G., Wiegele, A.: A branch and bound algorithm for Max-Cut based on combining semidefinite and polyhedral relaxations. In: Integer programming and combinatorial optimization. Lecture Notes in Computer Science, vol. 4513, pp. 295\u2013309. Springer, Berlin (2007)","DOI":"10.1007\/978-3-540-72792-7_23"},{"key":"235_CR43","unstructured":"Rinaldi, G.: Rudy. http:\/\/www-user.tu-chemnitz.de\/~helmberg\/rudy.tar.gz (1998)"},{"key":"235_CR44","unstructured":"Wiegele, A.: Nonlinear optimization techniques applied to combinatorial optimization problems. PhD thesis, Alpen-Adria-Universit\u00e4t Klagenfurt (2006)"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-008-0235-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-008-0235-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-008-0235-8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,2,28]],"date-time":"2024-02-28T13:59:02Z","timestamp":1709128742000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-008-0235-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,7,22]]},"references-count":44,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2010,2]]}},"alternative-id":["235"],"URL":"https:\/\/doi.org\/10.1007\/s10107-008-0235-8","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,7,22]]}}}