{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,13]],"date-time":"2025-10-13T19:45:21Z","timestamp":1760384721209},"publisher-location":"Berlin, Heidelberg","reference-count":31,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540727910"},{"type":"electronic","value":"9783540727927"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-72792-7_23","type":"book-chapter","created":{"date-parts":[[2007,6,25]],"date-time":"2007-06-25T12:07:11Z","timestamp":1182773231000},"page":"295-309","source":"Crossref","is-referenced-by-count":29,"title":["A Branch and Bound Algorithm for Max-Cut Based on Combining Semidefinite and Polyhedral Relaxations"],"prefix":"10.1007","author":[{"given":"Franz","family":"Rendl","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Giovanni","family":"Rinaldi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Angelika","family":"Wiegele","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"1","key":"23_CR1","doi-asserted-by":"publisher","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.\u00a040(1), 53\u201373 (2006)","journal-title":"RAIRO Oper. Res."},{"key":"23_CR2","doi-asserted-by":"crossref","first-page":"493","DOI":"10.1287\/opre.36.3.493","volume":"36","author":"F. Barahona","year":"1988","unstructured":"Barahona, F., Gr\u00f6tschel, M., J\u00fcnger, M., Reinelt, G.: An application of combinatorial optimization to statistical physics and circuit layout design. Operations Research\u00a036, 493\u2013513 (1988)","journal-title":"Operations Research"},{"issue":"2","key":"23_CR3","doi-asserted-by":"publisher","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-1 programming. Math. Programming, Ser. A\u00a044(2), 127\u2013137 (1989)","journal-title":"Math. Programming, Ser. A"},{"issue":"11","key":"23_CR4","doi-asserted-by":"publisher","first-page":"1069","DOI":"10.1038\/sj\/jors\/0411109","volume":"41","author":"J.E. Beasley","year":"1990","unstructured":"Beasley, J.E.: Or-library: distributing test problems by electronic mail. J. Oper. Res. Soc.\u00a041(11), 1069\u20131072 (1990)","journal-title":"J. Oper. Res. Soc."},{"key":"23_CR5","unstructured":"Beasley, J.E.: Or-library (1990), http:\/\/people.brunel.ac.uk\/~mastjjb\/jeb\/info.html"},{"key":"23_CR6","unstructured":"Beasley, J.E.: Heuristic algorithms for the unconstrained binary quadratic programming problem. Technical report, The Management School, Imperial College, London, England (1998)"},{"issue":"1","key":"23_CR7","doi-asserted-by":"publisher","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-1 problem. Math. Programming, Ser. A\u00a0109(1), 55\u201368 (2007)","journal-title":"Math. Programming, Ser. A"},{"key":"23_CR8","unstructured":"Boros, E., Hammer, P.L., Tavares, G.: The pseudo-boolean optimization website (2005), http:\/\/rutcor.rutgers.edu\/~pbo\/"},{"issue":"1-2","key":"23_CR9","doi-asserted-by":"publisher","first-page":"487","DOI":"10.1007\/BF02178370","volume":"80","author":"C. Simone De","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. Statist. Phys.\u00a080(1-2), 487\u2013496 (1995)","journal-title":"J. Statist. Phys."},{"issue":"3","key":"23_CR10","doi-asserted-by":"publisher","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. Programming, Ser. A\u00a062(3), 557\u2013574 (1993)","journal-title":"Math. Programming, Ser. A"},{"key":"23_CR11","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1016\/S0167-6377(03)00025-7","volume":"31","author":"M. Elf","year":"2003","unstructured":"Elf, M., J\u00fcnger, M., Rinaldi, G.: Minimizing breaks by maximizing cuts. Operations Research Letters\u00a031, 343\u2013349 (2003)","journal-title":"Operations Research Letters"},{"issue":"2-3","key":"23_CR12","doi-asserted-by":"publisher","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. Programming, Ser. B\u00a0105(2-3), 451\u2013469 (2006)","journal-title":"Math. Programming, Ser. B"},{"issue":"2-3","key":"23_CR13","doi-asserted-by":"publisher","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., Ser. B\u00a0104(2-3), 375\u2013388 (2005)","journal-title":"Math. Program., Ser. B"},{"issue":"3","key":"23_CR14","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. Management Sci\u00a044(3), 336\u2013345 (1998)","journal-title":"Management Sci"},{"key":"23_CR15","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, Montreal, Quebec, Canada, pp. 422\u2013431 (1994)","DOI":"10.1145\/195058.195216"},{"issue":"6","key":"23_CR16","doi-asserted-by":"crossref","first-page":"1115","DOI":"10.1145\/227683.227684","volume":"42","author":"M.X. 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.\u00a042(6), 1115\u20131145 (1995), preliminary version see: Proceedings of the Twenty-Sixth Annual ACM Symposium on the Theory of Computing, Montreal, Quebec, Canada, pp. 422\u2013431 (1994)","journal-title":"J. Assoc. Comput. Mach."},{"issue":"3","key":"23_CR17","doi-asserted-by":"publisher","first-page":"952","DOI":"10.1137\/S089547989631442X","volume":"21","author":"C. Helmberg","year":"2000","unstructured":"Helmberg, C.: Fixing variables in semidefinite relaxations. SIAM J. Matrix Anal. Appl. (electronic)\u00a021(3), 952\u2013969 (2000)","journal-title":"SIAM J. Matrix Anal. Appl."},{"issue":"3","key":"23_CR18","doi-asserted-by":"publisher","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. Programming, Ser. A\u00a082(3), 291\u2013315 (1998)","journal-title":"Math. Programming, Ser. A"},{"issue":"6","key":"23_CR19","doi-asserted-by":"publisher","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.\u00a037(6), 865\u2013892 (1989)","journal-title":"Oper. Res."},{"key":"23_CR20","series-title":"Fields Inst. Commun","first-page":"77","volume-title":"Topics in semidefinite and interior-point methods","author":"S.E. Karisch","year":"1998","unstructured":"Karisch, S.E., Rendl, F.: Semidefinite programming and graph equipartition. In: Topics in semidefinite and interior-point methods, Toronto, ON, 1996. Fields Inst. Commun, vol.\u00a018, pp. 77\u201395. Amer. Math. Soc., Providence (1998)"},{"issue":"3-4","key":"23_CR21","doi-asserted-by":"publisher","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.\u00a015(3-4), 201\u2013224 (2001)","journal-title":"Optim. Methods Softw."},{"key":"23_CR22","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":"23_CR23","doi-asserted-by":"publisher","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, Chichester (2004)"},{"issue":"2","key":"23_CR24","first-page":"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. Japan\u00a046(2), 164\u2013177 (2003)","journal-title":"J. Oper. Res. Soc. Japan"},{"issue":"2","key":"23_CR25","doi-asserted-by":"publisher","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\u00a045(2), 131\u2013144 (1990)","journal-title":"Computing"},{"issue":"1-4","key":"23_CR26","doi-asserted-by":"publisher","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.\u00a022(1-4), 271\u2013292 (1990)","journal-title":"Ann. Oper. Res."},{"issue":"1-3","key":"23_CR27","doi-asserted-by":"publisher","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.\u00a062(1-3), 249\u2013278 (1995)","journal-title":"Discrete Appl. Math."},{"issue":"3","key":"23_CR28","doi-asserted-by":"publisher","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.\u00a05(3), 467\u2013487 (1995)","journal-title":"SIAM J. Optim."},{"key":"23_CR29","unstructured":"Rendl, F., Rinaldi, G., Wiegele, A.: Biq Mac \u2013 a solver for binary quadratic and max-cut problems (2006), http:\/\/BiqMac.uni-klu.ac.at\/"},{"key":"23_CR30","unstructured":"Rinaldi, G.: Rudy (1998), http:\/\/www-user.tu-chemnitz.de\/~helmberg\/rudy.tar.gz"},{"key":"23_CR31","unstructured":"Wiegele, A.: Nonlinear optimization techniques applied to combinatorial optimization problems. PhD thesis, Alpen-Adria-Universit\u00e4t Klagenfurt (2006)"}],"container-title":["Lecture Notes in Computer Science","Integer Programming and Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-72792-7_23.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,19]],"date-time":"2020-11-19T05:05:21Z","timestamp":1605762321000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-72792-7_23"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540727910","9783540727927"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-72792-7_23","relation":{},"subject":[]}}