{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,18]],"date-time":"2026-08-18T14:45:55Z","timestamp":1787064355114,"version":"build-2736575974"},"reference-count":48,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2019,11,14]],"date-time":"2019-11-14T00:00:00Z","timestamp":1573689600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,11,14]],"date-time":"2019-11-14T00:00:00Z","timestamp":1573689600000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Comput Optim Appl"],"published-print":{"date-parts":[[2020,3]]},"DOI":"10.1007\/s10589-019-00153-2","type":"journal-article","created":{"date-parts":[[2019,11,14]],"date-time":"2019-11-14T03:02:20Z","timestamp":1573700540000},"page":"493-513","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":17,"title":["A branch-and-cut algorithm for solving mixed-integer semidefinite optimization problems"],"prefix":"10.1007","volume":"75","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6609-7488","authenticated-orcid":false,"given":"Ken","family":"Kobayashi","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yuich","family":"Takano","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2019,11,14]]},"reference":[{"issue":"1","key":"153_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s12532-008-0001-1","volume":"1","author":"T Achterberg","year":"2009","unstructured":"Achterberg, T.: SCIP: solving constraint integer programs. Math. Program. Comput. 1(1), 1\u201341 (2009)","journal-title":"Math. Program. Comput."},{"issue":"3","key":"153_CR2","doi-asserted-by":"publisher","first-page":"503","DOI":"10.1590\/S0101-74382009000300002","volume":"29","author":"D Aloise","year":"2009","unstructured":"Aloise, D., Hansen, P.: A branch-and-cut SDP-based algorithm for minimum sum-of-squares clustering. Pesqui. Oper. 29(3), 503\u2013516 (2009)","journal-title":"Pesqui. Oper."},{"key":"153_CR3","doi-asserted-by":"publisher","first-page":"355","DOI":"10.1007\/978-3-642-38189-8_15","volume-title":"Facets of Combinatorial Optimization","author":"MF Anjos","year":"2013","unstructured":"Anjos, M.F., Ghaddar, B., Hupp, L., Liers, F., Wiegele, A.: Solving $$k$$-way graph partitioning problems to optimality: the impact of semidefinite relaxations and the bundle method. In: J\u00fcnger, M., Reinelt, G. (eds.) Facets of Combinatorial Optimization, pp. 355\u2013386. Springer, Berlin (2013)"},{"issue":"3","key":"153_CR4","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1007\/s12532-012-0040-5","volume":"4","author":"M Armbruster","year":"2012","unstructured":"Armbruster, M., F\u00fcgenschuh, M., Helmberg, C., Martin, A.: LP and SDP branch-and-cut algorithms for the minimum graph bisection problem: a computational comparison. Math. Program. Comput. 4(3), 275\u2013306 (2012)","journal-title":"Math. Program. Comput."},{"issue":"4","key":"153_CR5","doi-asserted-by":"publisher","first-page":"118","DOI":"10.1109\/MSP.2007.4286571","volume":"24","author":"RG Baraniuk","year":"2007","unstructured":"Baraniuk, R.G.: Compressive sensing [lecture notes]. IEEE Signal Process. Mag. 24(4), 118\u2013121 (2007)","journal-title":"IEEE Signal Process. Mag."},{"issue":"2","key":"153_CR6","doi-asserted-by":"publisher","first-page":"443","DOI":"10.1137\/S1052623497328008","volume":"10","author":"SJ Benson","year":"2000","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)","journal-title":"SIAM J. Optim."},{"issue":"4","key":"153_CR7","doi-asserted-by":"publisher","first-page":"991","DOI":"10.1137\/S1052623495291951","volume":"7","author":"A Ben-Tal","year":"1997","unstructured":"Ben-Tal, A., Nemirovski, A.: Robust truss topology design via semidefinite programming. SIAM J. Optim. 7(4), 991\u20131016 (1997)","journal-title":"SIAM J. Optim."},{"issue":"2","key":"153_CR8","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1007\/s10287-015-0236-z","volume":"13","author":"D Bertsimas","year":"2016","unstructured":"Bertsimas, D., Dunning, I., Lubin, M.: Reformulation versus cutting-planes for robust optimization. Comput. Manag. Sci. 13(2), 195\u2013217 (2016)","journal-title":"Comput. Manag. Sci."},{"issue":"3","key":"153_CR9","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1214\/16-STS602","volume":"32","author":"D Bertsimas","year":"2017","unstructured":"Bertsimas, D., King, A.: Logistic regression: from art to science. Stat. Sci. 32(3), 367\u2013384 (2017)","journal-title":"Stat. Sci."},{"issue":"3","key":"153_CR10","doi-asserted-by":"publisher","first-page":"756","DOI":"10.1287\/moor.2014.0694","volume":"40","author":"G Braun","year":"2015","unstructured":"Braun, G., Fiorini, S., Pokutta, S., Steurer, D.: Approximation limits of linear programs (beyond hierarchies). Math. Oper. Res. 40(3), 756\u2013772 (2015)","journal-title":"Math. Oper. Res."},{"issue":"1","key":"153_CR11","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1007\/s10589-012-9487-6","volume":"54","author":"A Cerveira","year":"2013","unstructured":"Cerveira, A., Agra, A., Bastos, F., Gromicho, J.: A new Branch and Bound method for a discrete truss topology design problem. Comput. Optim. Appl. 54(1), 163\u2013187 (2013)","journal-title":"Comput. Optim. Appl."},{"issue":"3","key":"153_CR12","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1109\/99.714603","volume":"5","author":"J Czyzyk","year":"1998","unstructured":"Czyzyk, J., Mesnier, M.P., Mor\u00e9, J.J.: The NEOS server. IEEE Comput. Sci. Eng. 5(3), 68\u201375 (1998)","journal-title":"IEEE Comput. Sci. Eng."},{"issue":"3","key":"153_CR13","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1007\/BF02592064","volume":"36","author":"MA Duran","year":"1986","unstructured":"Duran, M.A., Grossmann, I.E.: An outer-approximation algorithm for a class of mixed-integer nonlinear programs. Math. Program. 36(3), 307\u2013339 (1986)","journal-title":"Math. Program."},{"issue":"1\u20133","key":"153_CR14","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1007\/BF01581153","volume":"66","author":"R Fletcher","year":"1994","unstructured":"Fletcher, R., Leyffer, S.: Solving mixed integer nonlinear programs by outer approximation. Math. Program. 66(1\u20133), 327\u2013349 (1994)","journal-title":"Math. Program."},{"issue":"3","key":"153_CR15","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1016\/j.acha.2008.09.001","volume":"26","author":"S Foucart","year":"2009","unstructured":"Foucart, S., Lai, M.J.: Sparsest solutions of underdetermined linear systems via $$\\ell _q$$-minimization for $$0 < q \\le 1$$. Appl. Comput. Harmon. Anal. 26(3), 395\u2013407 (2009)","journal-title":"Appl. Comput. Harmon. Anal."},{"key":"153_CR16","unstructured":"Gally, T., Pfetsch, M. E.: Computing restricted isometry constants via mixed-integer semidefinite programming. Optimization Online, http:\/\/www.optimization-online.org\/DB_HTML\/2016\/04\/5395.html (2016)"},{"issue":"3","key":"153_CR17","doi-asserted-by":"publisher","first-page":"594","DOI":"10.1080\/10556788.2017.1322081","volume":"33","author":"T Gally","year":"2018","unstructured":"Gally, T., Pfetsch, M.E., Ulbrich, S.: A framework for solving mixed-integer semidefinite programs. Optim. Methods Softw. 33(3), 594\u2013632 (2018)","journal-title":"Optim. Methods Softw."},{"key":"153_CR18","unstructured":"Gleixner, A., Eifler, L., Gally, T., Gamrath, G., Gemander, P., Gottwald, R. L., Hendel, G., Hojny, C., Koch, T., Miltenberger, M., M\u00fcller, B.: The SCIP optimization suite 5.0. Optimization Online, http:\/\/www.optimization-online.org\/DB_HTML\/2017\/12\/6385.html (2017)"},{"key":"153_CR19","volume-title":"Matrix Analysis","author":"RA Horn","year":"2013","unstructured":"Horn, R.A., Johnson, C.R.: Matrix Analysis, 2nd edn. Cambridge University Press, Cambridge (2013)","edition":"2"},{"issue":"2","key":"153_CR20","doi-asserted-by":"publisher","first-page":"451","DOI":"10.1109\/TSP.2008.2007095","volume":"57","author":"S Joshi","year":"2009","unstructured":"Joshi, S., Boyd, S.: Sensor selection via convex optimization. IEEE Trans. Signal Process. 57(2), 451\u2013462 (2009)","journal-title":"IEEE Trans. Signal Process."},{"issue":"4","key":"153_CR21","doi-asserted-by":"publisher","first-page":"703","DOI":"10.1137\/0108053","volume":"8","author":"JE Kelley Jr","year":"1960","unstructured":"Kelley Jr., J.E.: The cutting-plane method for solving convex programs. J. Soc. Ind. Appl. Math. 8(4), 703\u2013712 (1960)","journal-title":"J. Soc. Ind. Appl. Math."},{"issue":"1","key":"153_CR22","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1016\/S0377-0427(02)00424-7","volume":"146","author":"H Konno","year":"2002","unstructured":"Konno, H., Gotoh, J., Uno, T., Yuki, A.: A cutting plane algorithm for semi-definite programming problems with applications to failure discriminant analysis. J. Comput. Appl. Math. 146(1), 141\u2013154 (2002)","journal-title":"J. Comput. Appl. Math."},{"issue":"2","key":"153_CR23","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1023\/A:1021985014197","volume":"25","author":"H Konno","year":"2003","unstructured":"Konno, H., Kawadai, N., Tuy, H.: Cutting plane algorithms for nonlinear semi-definite programming problems with applications. J. Glob. Optim. 25(2), 141\u2013155 (2003)","journal-title":"J. Glob. Optim."},{"issue":"1","key":"153_CR24","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1080\/10556780500065283","volume":"21","author":"K Krishnan","year":"2006","unstructured":"Krishnan, K., Mitchell, J.E.: A unifying framework for several cutting plane methods for semidefinite programming. Optim. Methods Softw. 21(1), 57\u201374 (2006)","journal-title":"Optim. Methods Softw."},{"key":"153_CR25","unstructured":"L\u00f6fberg, J.: YALMIP: A toolbox for modeling and optimization in MATLAB. In: Proceedings of the 2004 IEEE International Symposium on Computer Aided Control Systems Design, pp. 284\u2013289 (2004)"},{"issue":"1","key":"153_CR26","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1007\/s10107-017-1191-y","volume":"172","author":"M Lubin","year":"2018","unstructured":"Lubin, M., Yamangil, E., Bent, R., Vielma, J.P.: Polyhedral approximation in mixed-integer convex optimization. Math. Program. 172(1), 139\u2013168 (2018)","journal-title":"Math. Program."},{"key":"153_CR27","doi-asserted-by":"crossref","unstructured":"Manousakis, N. M., Korres, G. N.: Semidefinite programming for optimal placement of PMUs with channel limits considering pre-existing SCADA and PMU measurements. In: Proceedings of the 2016 Power Systems Computation Conference, pp. 1\u20137 (2016)","DOI":"10.1109\/PSCC.2016.7540813"},{"issue":"2","key":"153_CR28","doi-asserted-by":"publisher","first-page":"407","DOI":"10.1007\/s10107-002-0355-5","volume":"95","author":"HD Mittelmann","year":"2003","unstructured":"Mittelmann, H.D.: An independent benchmarking of SDP and SOCP solvers. Math. Program. 95(2), 407\u2013430 (2003)","journal-title":"Math. Program."},{"issue":"3","key":"153_CR29","doi-asserted-by":"publisher","first-page":"1092","DOI":"10.1287\/trsc.2015.0621","volume":"50","author":"N Noyan","year":"2015","unstructured":"Noyan, N., Balcik, B., Atakan, S.: A stochastic optimization model for designing last mile relief networks. Trans. Sci. 50(3), 1092\u20131113 (2015)","journal-title":"Trans. Sci."},{"key":"153_CR30","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1007\/11362197_4","volume-title":"Foundations and Advances in Data Mining","author":"J Peng","year":"2005","unstructured":"Peng, J., Xia, Y.: A new theoretical framework for k-means-type clustering. In: Chu, W., Young Lin, T. (eds.) Foundations and Advances in Data Mining, pp. 79\u201396. Springer, Berlin (2005)"},{"key":"153_CR31","doi-asserted-by":"crossref","unstructured":"Philipp, A., Ulbrich, S., Cheng, Y., Pesavento, M.: Multiuser downlink beamforming with interference cancellation using a SDP-based branch-and-bound algorithm. In: Proceedings of the 2014 IEEE International Conference on Acoustics, Speech and Signal Processing, pp. 7724\u20137728 (2014)","DOI":"10.1109\/ICASSP.2014.6855103"},{"issue":"10\u201311","key":"153_CR32","doi-asserted-by":"publisher","first-page":"937","DOI":"10.1016\/0098-1354(92)80028-8","volume":"16","author":"I Quesada","year":"1992","unstructured":"Quesada, I., Grossmann, I.E.: An LP\/NLP based branch and bound algorithm for convex MINLP optimization problems. Comput. Chem. Eng. 16(10\u201311), 937\u2013947 (1992)","journal-title":"Comput. Chem. Eng."},{"key":"153_CR33","doi-asserted-by":"publisher","first-page":"687","DOI":"10.1007\/978-3-540-68279-0_18","volume-title":"50 Years of Integer Programming 1958\u20132008","author":"F Rendl","year":"2010","unstructured":"Rendl, F.: Semidefinite relaxations for integer programming. In: J\u00fcnger, M., et al. (eds.) 50 Years of Integer Programming 1958\u20132008, pp. 687\u2013726. Springer, Berlin (2010)"},{"issue":"2","key":"153_CR34","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1007\/s10107-008-0235-8","volume":"121","author":"F Rendl","year":"2010","unstructured":"Rendl, F., Rinaldi, G., Wiegele, A.: Solving max-cut to optimality by intersecting semidefinite and polyhedral relaxations. Math. Program. 121(2), 307\u2013335 (2010)","journal-title":"Math. Program."},{"key":"153_CR35","unstructured":"Rowe, C., Maciejowski, J.: An efficient algorithm for mixed integer semidefinite optimisation. In: Proceedings of the 2003 American Control Conference, vol. 6, pp. 4730\u20134735 (2003)"},{"key":"153_CR36","doi-asserted-by":"publisher","first-page":"795","DOI":"10.1007\/978-1-4614-0769-0_27","volume-title":"Handbook on Semidefinite, Conic and Polynomial Optimization","author":"R Sotirov","year":"2012","unstructured":"Sotirov, R.: SDP relaxations for some combinatorial optimization problems. In: Anjos, M., Lasserre, J. (eds.) Handbook on Semidefinite, Conic and Polynomial Optimization, pp. 795\u2013819. Springer, Boston (2012)"},{"issue":"3","key":"153_CR37","doi-asserted-by":"publisher","first-page":"321","DOI":"10.15807\/jorsj.60.321","volume":"60","author":"R Tamura","year":"2017","unstructured":"Tamura, R., Kobayashi, K., Takano, Y., Miyashiro, R., Nakata, K., Matsui, T.: Best subset selection for eliminating multicollinearity. J. Oper. Res. Soc. Jpn. 60(3), 321\u2013336 (2017)","journal-title":"J. Oper. Res. Soc. Jpn."},{"issue":"3","key":"153_CR38","doi-asserted-by":"publisher","first-page":"1060","DOI":"10.1109\/TCST.2016.2575799","volume":"25","author":"JA Taylor","year":"2017","unstructured":"Taylor, J.A., Luangsomboon, N., Fooladivanda, D.: Allocating sensors and actuators via optimal estimation and control. IEEE Trans. Control Syst. Technol. 25(3), 1060\u20131067 (2017)","journal-title":"IEEE Trans. Control Syst. Technol."},{"key":"153_CR39","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1017\/S0962492901000071","volume":"10","author":"MJ Todd","year":"2001","unstructured":"Todd, M.J.: Semidefinite optimization. Acta Numer. 10, 515\u2013560 (2001)","journal-title":"Acta Numer."},{"key":"153_CR40","doi-asserted-by":"crossref","unstructured":"Torchio, M., Magni, L., Raimondo, D.M.: A mixed integer SDP approach for the optimal placement of energy storage devices in power grids with renewable penetration. In: Proceedings of the American Control Conference, pp. 3892\u20133897 (2015)","DOI":"10.1109\/ACC.2015.7171937"},{"issue":"2","key":"153_CR41","doi-asserted-by":"crossref","first-page":"157","DOI":"10.5849\/forsci.11-040","volume":"59","author":"SF T\u00f3th","year":"2013","unstructured":"T\u00f3th, S.F., McDill, M.E., K\u00f6nny\u00fc, N., George, S.: Testing the use of lazy constraints in solving area-based adjacency formulations of harvest scheduling models. For. Sci. 59(2), 157\u2013176 (2013)","journal-title":"For. Sci."},{"issue":"1","key":"153_CR42","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1137\/1038003","volume":"38","author":"L Vandenberghe","year":"1996","unstructured":"Vandenberghe, L., Boyd, S.: Semidefinite programming. SIAM Rev. 38(1), 49\u201395 (1996)","journal-title":"SIAM Rev."},{"key":"153_CR43","volume-title":"Model Building in Mathematical Programming","author":"HP Williams","year":"2013","unstructured":"Williams, H.P.: Model Building in Mathematical Programming. Wiley, Hoboken (2013)"},{"key":"153_CR44","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1016\/0098-1354(95)87027-X","volume":"19","author":"T Westerlund","year":"1995","unstructured":"Westerlund, T., Pettersson, F.: An extended cutting plane method for solving convex MINLP problems. Comput. Chem. Eng. 19, 131\u2013136 (1995)","journal-title":"Comput. Chem. Eng."},{"issue":"4","key":"153_CR45","doi-asserted-by":"publisher","first-page":"491","DOI":"10.1080\/1055678031000118482","volume":"18","author":"M Yamashita","year":"2003","unstructured":"Yamashita, M., Fujisawa, K., Kojima, M.: Implementation and evaluation of SDPA 6.0 (semidefinite programming algorithm 6.0). Optim. Methods Softw. 18(4), 491\u2013505 (2003)","journal-title":"Optim. Methods Softw."},{"key":"153_CR46","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1016\/j.enconman.2014.12.020","volume":"92","author":"R Yokoyama","year":"2015","unstructured":"Yokoyama, R., Shinano, Y., Taniguchi, S., Ohkura, M., Wakui, T.: Optimization of energy supply systems by MILP branch and bound method in consideration of hierarchical relationship between design and operation. Energy Convers. Manag. 92, 92\u2013104 (2015)","journal-title":"Energy Convers. Manag."},{"issue":"3","key":"153_CR47","doi-asserted-by":"publisher","first-page":"355","DOI":"10.1007\/s11081-010-9107-1","volume":"11","author":"K Yonekura","year":"2010","unstructured":"Yonekura, K., Kanno, Y.: Global optimization of robust truss topology via mixed integer semidefinite programming. Optim. Eng. 11(3), 355\u2013379 (2010)","journal-title":"Optim. Eng."},{"issue":"7","key":"153_CR48","doi-asserted-by":"publisher","first-page":"1503","DOI":"10.1007\/s11590-018-1255-9","volume":"12","author":"Y Zhang","year":"2018","unstructured":"Zhang, Y., Shen, S., Erdogan, S.A.: Solving 0\u20131 semidefinite programs for distributionally robust allocation of surgery blocks. Optim. Lett. 12(7), 1503\u20131521 (2018)","journal-title":"Optim. Lett."}],"container-title":["Computational Optimization and Applications"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-019-00153-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10589-019-00153-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-019-00153-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,12]],"date-time":"2020-11-12T19:31:11Z","timestamp":1605209471000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10589-019-00153-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,11,14]]},"references-count":48,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2020,3]]}},"alternative-id":["153"],"URL":"https:\/\/doi.org\/10.1007\/s10589-019-00153-2","relation":{},"ISSN":["0926-6003","1573-2894"],"issn-type":[{"value":"0926-6003","type":"print"},{"value":"1573-2894","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,11,14]]},"assertion":[{"value":"24 September 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 November 2019","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}