{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,22]],"date-time":"2026-01-22T21:07:50Z","timestamp":1769116070691,"version":"3.49.0"},"reference-count":40,"publisher":"Springer Science and Business Media LLC","issue":"2-3","license":[{"start":{"date-parts":[[2005,10,12]],"date-time":"2005-10-12T00:00:00Z","timestamp":1129075200000},"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":[[2006,2]]},"DOI":"10.1007\/s10107-005-0661-9","type":"journal-article","created":{"date-parts":[[2005,10,12]],"date-time":"2005-10-12T15:10:17Z","timestamp":1129129817000},"page":"451-469","source":"Crossref","is-referenced-by-count":53,"title":["Computational experience with a bundle approach for semidefinite cutting plane relaxations of Max-Cut and Equipartition"],"prefix":"10.1007","volume":"105","author":[{"given":"Ilse","family":"Fischer","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gerald","family":"Gruber","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Franz","family":"Rendl","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Renata","family":"Sotirov","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,10,12]]},"reference":[{"key":"661_CR1","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1137\/0805002","volume":"5","author":"Alizadeh","year":"1995","unstructured":"Alizadeh, F.: Interior Point methods in semidefinite programming with applications to combinatorial optimization. SIAM Journal on Optimization 5, 13\u201351 (1995)","journal-title":"SIAM Journal on Optimization"},{"key":"661_CR2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF01585551","volume":"69","author":"Atkinson","year":"1995","unstructured":"Atkinson, D.S., Vaidya, P.M.: A cutting plane algorithm for convex programming that uses analytic centers. Mathematical Programming 69, 1\u201343 (1995)","journal-title":"Mathematical Programming"},{"key":"661_CR3","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1007\/s10107-002-0357-3","volume":"94","author":"Bahiense","year":"2002","unstructured":"Bahiense, L., Maculan, N., Sagastizabal, C.: The volume algorithm revisited: relation with bundle methods. Mathematical Programming 94, 41\u201369 (2002)","journal-title":"Mathematical Programming"},{"key":"661_CR4","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1007\/BF01584228","volume":"21","author":"Balas","year":"1981","unstructured":"Balas, C., Christofides, N.: A restricted Lagrangian approach to the traveling salesman problem. Mathematical Programming 21, 19\u201346 (1981)","journal-title":"Mathematical Programming"},{"key":"661_CR5","doi-asserted-by":"crossref","first-page":"385","DOI":"10.1007\/s101070050002","volume":"87","author":"Barahona","year":"2000","unstructured":"Barahona, F., Anbil, R.: The Volume algorithm: producing primal solutions with a subgradient method. Mathematical Programming 87, 385\u2013399 (2000)","journal-title":"Mathematical Programming"},{"key":"661_CR6","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1007\/BF01587084","volume":"44","author":"Barahona","year":"1989","unstructured":"Barahona, F., J\u00fcnger, M., Reinelt, G.: Experiments in quadratic 0-1 programming. Mathematical Programming 44, 127\u2013137 (1989)","journal-title":"Mathematical Programming"},{"key":"661_CR7","unstructured":"Barahona, F., Ladanyi, L.: Branch and Cut based on the Volume Algorithm: Steiner trees in graphs and Max-Cut. Technical report, (2001)"},{"key":"661_CR8","unstructured":"Belloni, A., Sagastizabal, C.: Dynamic bundle methods: applications to combinatorial optimization problems. Technical report, (2004)"},{"key":"661_CR9","unstructured":"Billionnet, A., Elloumi, S.: Using a mixed integer quadratic programming solver for the unconstrained quadratic 0-1 problem. Technical report, CNAM, rapport technique 466, (2003)"},{"key":"661_CR10","doi-asserted-by":"crossref","first-page":"503","DOI":"10.1137\/S1052623400382467","volume":"12","author":"Burer","year":"2002","unstructured":"Burer, S., Monteiro, R.D.C., Zhang, Y.: Rank-two relaxation heuristics for Max-Cut and other binary quadratic programs. SIAM Journal on Optimization 12, 503\u2013521 (2002)","journal-title":"SIAM Journal on Optimization"},{"key":"661_CR11","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1007\/s10107-002-0353-7","volume":"95","author":"Burer","year":"2003","unstructured":"Burer, S., Monteiro, R.D.C., Zhang, Y.: A computational study of gradient-based log-barrier algorithms for a class of large-scale sdps. Mathematical Programming 95, 359\u2013379 (2003)","journal-title":"Mathematical Programming"},{"key":"661_CR12","unstructured":"Choi, C., Ye, Y.: Solving sparse semidefinite programs using the dual scaling algorithm with an iterative solver. Technical report, University of Iowa, (2000)"},{"key":"661_CR13","doi-asserted-by":"crossref","first-page":"557","DOI":"10.1007\/BF01585184","volume":"62","author":"Delorme","year":"1993","unstructured":"Delorme, C., Poljak, S.: Laplacian eigenvalues and the maximum cut problem. Mathematical Programming 62, 557\u2013574 (1993)","journal-title":"Mathematical Programming"},{"key":"661_CR14","doi-asserted-by":"crossref","first-page":"420","DOI":"10.1147\/rd.175.0420","volume":"17","author":"Donath","year":"1973","unstructured":"Donath, W.E., Hoffman, A.J.: Lower bounds for the partitioning of graphs. IBM J. of Research and Developement 17, 420\u2013425 (1973)","journal-title":"IBM J. of Research and Developement"},{"key":"661_CR15","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1137\/S1052623498342186","volume":"13","author":"Frangioni","year":"2002","unstructured":"Frangioni, A.: Generalized bundle methods. SIAM Journal on Optimization 13, 117\u2013156 (2002)","journal-title":"SIAM Journal on Optimization"},{"key":"661_CR16","doi-asserted-by":"crossref","first-page":"1115","DOI":"10.1145\/227683.227684","volume":"42","author":"Goemans","year":"1995","unstructured":"Goemans, M.X., Williamson, D.P.: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the ACM 42, 1115\u20131145 (1995)","journal-title":"Journal of the ACM"},{"key":"661_CR17","doi-asserted-by":"crossref","first-page":"284","DOI":"10.1287\/mnsc.38.2.284","volume":"38","author":"Goffin","year":"1992","unstructured":"Goffin, J.L., Haurie, A., Vial, J.P.: Decomposition and nondifferentiable optimization with the projective algorithm. Management Science 38, 284\u2013302 (1992)","journal-title":"Management Science"},{"key":"661_CR18","doi-asserted-by":"crossref","first-page":"1138","DOI":"10.1287\/opre.18.6.1138","volume":"18","author":"Held","year":"1970","unstructured":"Held, M., Karp, R.: The traveling salesman problem and minimum spanning trees. Operations Research 18, 1138\u20131162 (1970)","journal-title":"Operations Research"},{"key":"661_CR19","unstructured":"Helmberg, C.: An interior point method for semidefinite programming and max-cut bounds. PhD thesis, Graz University of Technology, Austria, (1994)"},{"key":"661_CR20","doi-asserted-by":"crossref","unstructured":"Helmberg, C., Kiwiel, K.C., Rendl, F.: Incorporating inequality constraints in the spectral bundle method. In: Boyd, E.A., Bixby, R.E., Rios-Mercado, R.Z., (ed.) Integer Programming and combinatorial optimization, 423\u2013435. Springer Lecture Notes 1412, (1998)","DOI":"10.1007\/3-540-69346-7_32"},{"key":"661_CR21","first-page":"291","volume":"82","author":"Helmberg","year":"1998","unstructured":"Helmberg, C., Rendl, F.: Solving quadratic (0,1)-problems by semidefinite programming and cutting planes. Mathematical Programming 82, 291\u2013315 (1998)","journal-title":"Mathematical Programming"},{"key":"661_CR22","doi-asserted-by":"crossref","first-page":"342","DOI":"10.1137\/0806020","volume":"6","author":"Helmberg","year":"1996","unstructured":"Helmberg, C., Rendl, F., Vanderbei, R., Wolkowicz, H.: An interior-point method for semidefinite programming. SIAM Journal on Optimization 6, 342\u2013361 (1996)","journal-title":"SIAM Journal on Optimization"},{"key":"661_CR23","first-page":"77","volume":"18","author":"Karisch","year":"1998","unstructured":"Karisch, S.E., Rendl, F.: Semidefinite Programming and Graph Equipartition. Fields Institute Communications 18, 77\u201395 (1998)","journal-title":"Fields Institute Communications"},{"key":"661_CR24","doi-asserted-by":"crossref","unstructured":"Kiwiel, K.C.: Methods of descent for nondifferentiable optimization. Springer, Berlin, (1985)","DOI":"10.1007\/BFb0074500"},{"key":"661_CR25","unstructured":"Lemarechal, C.: Nonsmooth optimization and descent methods. Technical report, International Institute for Applied Systems Analysis, (1978)"},{"key":"661_CR26","doi-asserted-by":"crossref","unstructured":"Lemarechal, C.: The omnipresence of Lagrange. 4OR 1, 7\u201325 (2003)","DOI":"10.1007\/s10288-002-0003-1"},{"key":"661_CR27","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1007\/BF01585555","volume":"69","author":"Lemarechal","year":"1995","unstructured":"Lemarechal, C., Nemirovskii, A., Nesterov, Y.: New variants of bundle methods. Mathematical Programming 69, 111\u2013147 (1995)","journal-title":"Mathematical Programming"},{"key":"661_CR28","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1007\/s10107-002-0342-x","volume":"95","author":"Lisser","year":"2002","unstructured":"Lisser, A., Rendl, F.: Graph partitioning using Linear and Semidefinite Programming. Mathematical Programming (B) 95, 91\u2013101 (2002)","journal-title":"Mathematical Programming (B)"},{"key":"661_CR29","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1109\/TIT.1979.1055985","volume":"25","author":"Lov\u00e1sz","year":"1979","unstructured":"Lov\u00e1sz, L.: On the shannon capacity of a graph. IEEE Trans. Inform. Theory 25, 1\u20137 (1979)","journal-title":"IEEE Trans. Inform. Theory"},{"key":"661_CR30","doi-asserted-by":"crossref","first-page":"166","DOI":"10.1137\/0801013","volume":"1","author":"Lov\u00e1sz","year":"1991","unstructured":"Lov\u00e1sz, L., Schrijver, A.: Cones of matrices and set-functions and 0-1 optimization. SIAM Journal on Optimization 1, 166\u2013190 (1991)","journal-title":"SIAM Journal on Optimization"},{"key":"661_CR31","unstructured":"Meurdesoif, P.: Strengthening the Lovasz bound for graph coloring. Mathematical Programming (forthcoming)."},{"key":"661_CR32","first-page":"149","volume":"69","author":"Nesterov","year":"1995","unstructured":"Nesterov, Y.: Complexity estimates of some cutting plane methods based on the analytic barrier. Mathematical Programming 69, 149\u2013176 (1995)","journal-title":"Mathematical Programming"},{"key":"661_CR33","unstructured":"Nesterov, Y.: Quality of semidefinite relaxation for nonconvex quadratic optimization. Technical report, (1997)"},{"key":"661_CR34","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1007\/BF02247879","volume":"45","author":"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, 131\u2013144 (1990)","journal-title":"Computing"},{"key":"661_CR35","doi-asserted-by":"crossref","first-page":"467","DOI":"10.1137\/0805024","volume":"5","author":"Poljak","year":"1995","unstructured":"Poljak, S., Rendl, F.: Nonpolyhedral relaxations of graph bisection problems. SIAM Journal on Optimization 5, 467\u2013487 (1995)","journal-title":"SIAM Journal on Optimization"},{"key":"661_CR36","first-page":"593","volume":"8","author":"Polyak","year":"1966","unstructured":"Polyak, B.T.: A general method for solving extremum problems. Soviet Mathematics 8, 593\u2013597 (1966)","journal-title":"Soviet Mathematics"},{"key":"661_CR37","unstructured":"Rendl, F., Sotirov, R.: Bounds for the quadratic assignment problem using the bundle method. Technical report, University of Klagenfurt, Austria, (2003)"},{"key":"661_CR38","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1137\/0802008","volume":"2","author":"Schramm","year":"1992","unstructured":"Schramm, H., Zowe, J.: A version of the bundle idea for minimizing a nonsmooth function: Conceptual idea, convergence analysis, numerical results. SIAM J. Optimization 2, 121\u2013152 (1992)","journal-title":"SIAM J. Optimization"},{"key":"661_CR39","unstructured":"Sotirov, R.: The bundle method in combinatorial optimization. PhD thesis, University of Klagenfurt, Austria, (2003)"},{"key":"661_CR40","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1080\/10556789908805745","volume":"11","author":"Todd","year":"1999","unstructured":"Todd, M.J.: A study of search directions in primal-dual interior-point methods for semidefinite programming. Optimization Methods and Software 11, 1\u201346 (1999)","journal-title":"Optimization Methods and Software"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-005-0661-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-005-0661-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-005-0661-9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T09:49:59Z","timestamp":1559123399000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-005-0661-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,10,12]]},"references-count":40,"journal-issue":{"issue":"2-3","published-print":{"date-parts":[[2006,2]]}},"alternative-id":["661"],"URL":"https:\/\/doi.org\/10.1007\/s10107-005-0661-9","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,10,12]]}}}