{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,22]],"date-time":"2026-02-22T08:22:29Z","timestamp":1771748549412,"version":"3.50.1"},"reference-count":72,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2024,3,13]],"date-time":"2024-03-13T00:00:00Z","timestamp":1710288000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,3,13]],"date-time":"2024-03-13T00:00:00Z","timestamp":1710288000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2025,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>In this paper we study the well-known Chv\u00e1tal\u2013Gomory (CG) procedure for the class of integer semidefinite programs (ISDPs). We prove several results regarding the hierarchy of relaxations obtained by iterating this procedure. We also study different formulations of the elementary closure of spectrahedra. A polyhedral description of the elementary closure for a specific type of spectrahedra is derived by exploiting total dual integrality for SDPs. Moreover, we show how to exploit (strengthened) CG cuts in a branch-and-cut framework for ISDPs. Different from existing algorithms in the literature, the separation routine in our approach exploits both the semidefinite and the integrality constraints. We provide separation routines for several common classes of binary SDPs resulting from combinatorial optimization problems. In the second part of the paper we present a comprehensive application of our approach to the quadratic traveling salesman problem (<jats:sc>QTSP<\/jats:sc>). Based on the algebraic connectivity of the directed Hamiltonian cycle, two ISDPs that model the <jats:sc>QTSP<\/jats:sc> are introduced. We show that the CG cuts resulting from these formulations contain several well-known families of cutting planes. Numerical results illustrate the practical strength of the CG cuts in our branch-and-cut algorithm, which outperforms alternative ISDP solvers and is able to solve large <jats:sc>QTSP<\/jats:sc> instances to optimality.<\/jats:p>","DOI":"10.1007\/s10107-024-02069-0","type":"journal-article","created":{"date-parts":[[2024,3,13]],"date-time":"2024-03-13T20:33:14Z","timestamp":1710361994000},"page":"323-395","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["The Chv\u00e1tal\u2013Gomory procedure for integer SDPs with applications in combinatorial optimization"],"prefix":"10.1007","volume":"209","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1910-0699","authenticated-orcid":false,"given":"Frank","family":"de Meijer","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3298-7255","authenticated-orcid":false,"given":"Renata","family":"Sotirov","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,3,13]]},"reference":[{"key":"2069_CR1","doi-asserted-by":"crossref","first-page":"697","DOI":"10.1137\/S0097539796312721","volume":"29","author":"A Aggarwal","year":"1999","unstructured":"Aggarwal, A., Coppersmith, D., Khanna, S., Motwani, R., Schieber, B.: The angular-metric traveling salesman problem. SIAM J. Comput. 29, 697\u2013711 (1999)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"2069_CR2","doi-asserted-by":"crossref","first-page":"521","DOI":"10.1080\/02331934.2016.1276905","volume":"66","author":"O Aichholzer","year":"2017","unstructured":"Aichholzer, O., Fischer, A., Fischer, F., Meier, J.F., Pferschy, U., Pilz, A., Stan\u011bk, R.: Minimization and maximization versions of the quadratic travelling salesman problem. Optim 66(4), 521\u2013546 (2017)","journal-title":"Optim"},{"issue":"3","key":"2069_CR3","doi-asserted-by":"crossref","first-page":"531","DOI":"10.1137\/S0097539703434267","volume":"35","author":"EM Arkin","year":"2005","unstructured":"Arkin, E.M., Bender, M.A., Demaine, E.D., Fekete, S.P., Mitchell, J.S.B., Sethia, S.: Optimal covering tours with turn costs. SIAM J. Comput. 35(3), 531\u2013566 (2005)","journal-title":"SIAM J. Comput."},{"key":"2069_CR4","doi-asserted-by":"crossref","first-page":"16","DOI":"10.1007\/978-3-540-72792-7_2","volume-title":"Integer Programming and Combinatorial Optimization","author":"A Atamt\u00fcrk","year":"2007","unstructured":"Atamt\u00fcrk, A., Narayanan, V.: Cuts for conic mixed-integer programming. In: Fischetti, M., Williamson, D.P. (eds.) Integer Programming and Combinatorial Optimization, pp. 16\u201329. Springer, Berlin (2007)"},{"issue":"1","key":"2069_CR5","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s10107-008-0239-4","volume":"122","author":"A Atamt\u00fcrk","year":"2010","unstructured":"Atamt\u00fcrk, A., Narayanan, V.: Conic mixed-integer rounding cuts. Math. Program. 122(1), 1\u201320 (2010)","journal-title":"Math. Program."},{"issue":"1","key":"2069_CR6","doi-asserted-by":"crossref","first-page":"30","DOI":"10.1109\/TAC.2002.806652","volume":"48","author":"V Balakrishnan","year":"2003","unstructured":"Balakrishnan, V., Vandenberghe, L.: Semidefinite programming duality and linear time-invariant systems. IEEE Trans. Autom. Control 48(1), 30\u201341 (2003)","journal-title":"IEEE Trans. Autom. Control"},{"key":"2069_CR7","doi-asserted-by":"crossref","first-page":"15","DOI":"10.2140\/pjm.1975.57.15","volume":"57","author":"GP Barker","year":"1975","unstructured":"Barker, G.P., Carlson, D.: Cones of diagonally dominant matrices. Pac. J. Math. 57, 15\u201332 (1975)","journal-title":"Pac. J. Math."},{"key":"2069_CR8","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/j.disopt.2016.10.001","volume":"24","author":"P Belotti","year":"2017","unstructured":"Belotti, P., G\u00f3ez, J.C., P\u00f3lik, I., Ralphs, T.K., Terlaky, T.: A complete characterization of disjunctive conic cuts for mixed integer second order cone optimization. Discrete Optim. 24, 3\u201331 (2017)","journal-title":"Discrete Optim."},{"issue":"2","key":"2069_CR9","doi-asserted-by":"crossref","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."},{"key":"2069_CR10","doi-asserted-by":"crossref","first-page":"1873","DOI":"10.1137\/120904172","volume":"25","author":"A Bhardwaj","year":"2015","unstructured":"Bhardwaj, A., Rostalski, P., Sanyal, R.: Deciding polyhedrality of spectrahedra. SIAM J. Optim. 25, 1873\u20131884 (2015)","journal-title":"SIAM J. Optim."},{"key":"2069_CR11","doi-asserted-by":"crossref","unstructured":"Bonami, P., Kilin\u00e7, M., Linderoth, J.: Mixed integer nonlinear programs, volume 154 of the IMA volumes in mathematics and its applications. In: Algorithms and Software for Convex Mixed Integer Nonlinear Programs, pp. 1\u201339. Springer, New York (2012)","DOI":"10.1007\/978-1-4614-1927-3_1"},{"issue":"5","key":"2069_CR12","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1016\/j.orl.2014.05.004","volume":"42","author":"G Braun","year":"2014","unstructured":"Braun, G., Pokutta, S.: A short proof for the polyhedrality of the Chv\u00e1tal\u2013Gomory closure of a compact convex set. Oper. Res. Lett. 42(5), 307\u2013310 (2014)","journal-title":"Oper. Res. Lett."},{"issue":"1","key":"2069_CR13","doi-asserted-by":"crossref","first-page":"470","DOI":"10.1137\/18M1169710","volume":"34","author":"MK De Carli Silva","year":"2018","unstructured":"De Carli Silva, M.K., Tun\u00e7el, L.: A notion on total dual integrality for convex, semidefinite, and extended formulations. SIAM J. Discrete Math. 34(1), 470\u2013496 (2018)","journal-title":"SIAM J. Discrete Math."},{"key":"2069_CR14","doi-asserted-by":"crossref","first-page":"R39","DOI":"10.37236\/1065","volume":"13","author":"JS Caughman","year":"2006","unstructured":"Caughman, J.S., Veerman, J.J.P.: Kernels of directed graph Laplacians. Electron. J. Comb. 13, R39 (2006)","journal-title":"Electron. J. Comb."},{"key":"2069_CR15","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1007\/s10107-005-0578-3","volume":"104","author":"MT \u00c7ezik","year":"2005","unstructured":"\u00c7ezik, M.T., Iyengar, G.: Cuts for mixed 0\u20131 conic programming. Math. Program. 104, 179\u2013202 (2005)","journal-title":"Math. Program."},{"issue":"1","key":"2069_CR16","doi-asserted-by":"crossref","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."},{"key":"2069_CR17","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1016\/0012-365X(73)90167-2","volume":"4","author":"V Chv\u00e1tal","year":"1973","unstructured":"Chv\u00e1tal, V.: Edmonds polytopes and a hierarchy of combinatorial problems. Discrete Math. 4, 305\u2013337 (1973)","journal-title":"Discrete Math."},{"issue":"1\u20132","key":"2069_CR18","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1007\/s10107-018-1317-x","volume":"179","author":"G Cornu\u00e9jols","year":"2020","unstructured":"Cornu\u00e9jols, G., Lee, D., Li, Y.: On the rational polytopes with Chv\u00e1tal rank 1. Math. Program. 179(1\u20132), 21\u201346 (2020)","journal-title":"Math. Program."},{"key":"2069_CR19","doi-asserted-by":"crossref","unstructured":"Cvetkovi\u0107, D., \u010cangalovi\u0107, M., Kova\u010devi\u0107-Vuj\u010di\u0107, V.: Semidefinite programming methods for the symmetric traveling salesman problem. In: Cornuj\u0301ols, G., Burkard, R.E., Woeginger, G.J. (eds.), Integer Programming and Combinatorial Optimization (IPCO 1999), Volume 1610 of Lecture Notes in Computer Science. Springer, Berlin (1999)","DOI":"10.1007\/3-540-48777-8_10"},{"issue":"3","key":"2069_CR20","doi-asserted-by":"crossref","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":"2","key":"2069_CR21","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1287\/moor.1110.0488","volume":"36","author":"D Dadush","year":"2011","unstructured":"Dadush, D., Dey, S.S., Vielma, J.P.: The Chv\u00e1tal\u2013Gomory closure of a strictly convex body. Math. Oper. Res. 36(2), 227\u2013239 (2011)","journal-title":"Math. Oper. Res."},{"key":"2069_CR22","doi-asserted-by":"crossref","first-page":"327","DOI":"10.1007\/s10107-013-0649-9","volume":"145","author":"D Dadush","year":"2014","unstructured":"Dadush, D., Dey, S.S., Vielma, J.P.: On the Chv\u00e1tal\u2013Gomory closure of a compact convex set. Math. Program. 145, 327\u2013348 (2014)","journal-title":"Math. Program."},{"key":"2069_CR23","first-page":"393","volume":"2","author":"G Dantzig","year":"1954","unstructured":"Dantzig, G., Fulkerson, R., Johnson, S.: Solution of a large-scale traveling-salesman problem. Oper. Res. 2, 393\u2013410 (1954)","journal-title":"Oper. Res."},{"key":"2069_CR24","doi-asserted-by":"publisher","unstructured":"Dash, S., G\u00fcnl\u00fck, O., Lee, D.: On a generalization of the Chv\u00e1tal\u2013Gomory closure. Math. Program. (2021). https:\/\/doi.org\/10.1007\/s10107-021-01697-0","DOI":"10.1007\/s10107-021-01697-0"},{"key":"2069_CR25","volume-title":"14th International Conference on Integer Programing and Combinatorial Optimization (IPCO2010). Lecture Notes in Computer Science","author":"SS Dey","year":"2010","unstructured":"Dey, S.S., Vielma, J.P.: The Chv\u00e1tal\u2013Gomory closure of an ellipsoid is a polyhedron. In: Eisenbrand, F., Shepherd, F.B. (eds.) 14th International Conference on Integer Programing and Combinatorial Optimization (IPCO2010). Lecture Notes in Computer Science, vol. 6080. Springer, Berlin (2010)"},{"issue":"1","key":"2069_CR26","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1287\/moor.1120.0565","volume":"38","author":"J Dunkel","year":"2012","unstructured":"Dunkel, J., Schulz, A.S.: The Gomory\u2013Chv\u00e1tal closure of a nonrational polytope is a rational polytope. Math. Oper. Res. 38(1), 63\u201391 (2012)","journal-title":"Math. Oper. Res."},{"issue":"2","key":"2069_CR27","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1137\/15M1020575","volume":"59","author":"I Dunning","year":"2017","unstructured":"Dunning, I., Huchette, J., Lubin, M.: JuMP: a modeling language for mathematical optimization. SIAM Rev. 59(2), 295\u2013320 (2017)","journal-title":"SIAM Rev."},{"key":"2069_CR28","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1016\/S0167-5060(08)70734-9","volume":"1","author":"J Edmonds","year":"1977","unstructured":"Edmonds, J., Giles, F.R.: A min-max relation for submodular functions on graphs. Ann. Discrete Math. 1, 185\u2013204 (1977)","journal-title":"Ann. Discrete Math."},{"key":"2069_CR29","doi-asserted-by":"crossref","first-page":"100","DOI":"10.1093\/bioinformatics\/18.suppl_2.S100","volume":"18","author":"K Ellrott","year":"2002","unstructured":"Ellrott, K., Yang, C., Sladek, F.M., Jiang, T.: Identifying transcription factor binding sites through Markov chain optimization. Bioinformatics 18, 100\u2013109 (2002)","journal-title":"Bioinformatics"},{"key":"2069_CR30","doi-asserted-by":"crossref","unstructured":"Fekete, S.P., Krupke, D.: Covering tours and cycle covers with turn costs: hardness and approximation. In: Heggernes, P. (ed.), International Conference on Algorithms and Complexity (CIAC2019), Volume 11485 of Lecture Notes in Computer Science. Springer, Cham (2019)","DOI":"10.1007\/978-3-030-17402-6_19"},{"key":"2069_CR31","doi-asserted-by":"crossref","unstructured":"Fekete, S.P., Krupke, D.: Practical methods for computing large covering tours and cycle covers with turn cost. In: Kobourov, S., Meyerhenke, H. (eds.), Meeting on Algorithm Engineering and Experiments (ALENEX2019) (2019)","DOI":"10.1137\/1.9781611975499.15"},{"issue":"2","key":"2069_CR32","doi-asserted-by":"crossref","first-page":"298","DOI":"10.21136\/CMJ.1973.101168","volume":"23","author":"M Fiedler","year":"1973","unstructured":"Fiedler, M.: Algebraic connectivity of graphs. Czechoslov. Math. J. 23(2), 298\u2013305 (1973)","journal-title":"Czechoslov. Math. J."},{"key":"2069_CR33","unstructured":"Fischer, A.: A polyhedral study of quadratic traveling salesman problems. Ph.D. thesis, Chemnitz University of Technology (2013)"},{"issue":"1","key":"2069_CR34","doi-asserted-by":"crossref","first-page":"240","DOI":"10.1137\/110858665","volume":"28","author":"A Fischer","year":"2014","unstructured":"Fischer, A.: An analysis of the asymmetric quadratic traveling salesman polytope. SIAM J. Discrete Math. 28(1), 240\u2013276 (2014)","journal-title":"SIAM J. Discrete Math."},{"key":"2069_CR35","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1016\/j.dam.2013.09.011","volume":"166","author":"A Fischer","year":"2014","unstructured":"Fischer, A., Fischer, F., J\u00e4ger, G., Keilwagen, J., Molitor, P., Grosse, I.: Exact algorithms and heuristics for the quadratic traveling salesman problem with an application in bioinformatics. Discrete Appl. Math. 166, 87\u2013114 (2014)","journal-title":"Discrete Appl. Math."},{"issue":"2","key":"2069_CR36","doi-asserted-by":"crossref","first-page":"285","DOI":"10.3390\/computation3020285","volume":"3","author":"A Fischer","year":"2015","unstructured":"Fischer, A., Fischer, F., J\u00e4ger, G., Keilwagen, J., Molitor, P., Grosse, I.: Computational recognition of RNA splice sites by exact algorithms for the quadratic traveling salesman problem. Computation 3(2), 285\u2013298 (2015)","journal-title":"Computation"},{"issue":"1\u20132","key":"2069_CR37","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1007\/s10107-012-0568-1","volume":"142","author":"A Fischer","year":"2013","unstructured":"Fischer, A., Helmberg, C.: The symmetric quadratic traveling salesman problem. Math. Program. 142(1\u20132), 205\u2013254 (2013)","journal-title":"Math. Program."},{"key":"2069_CR38","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/s10107-006-0054-8","volume":"110","author":"M Fischetti","year":"2007","unstructured":"Fischetti, M., Lodi, A.: Optimizing over the first Chv\u00e1tal closure. Math. Program. 110, 3\u201320 (2007)","journal-title":"Math. Program."},{"key":"2069_CR39","unstructured":"Gally, T., Pfetsch, M.E.: Computing restricted isometry constants via mixed-integer semidefinite programming. Optimization Online. http:\/\/www.optimization-online.org\/DB_FILE\/2016\/04\/5395.pdf (2016)"},{"issue":"3","key":"2069_CR40","doi-asserted-by":"crossref","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":"2069_CR41","unstructured":"Gamrath, G., Anderson, D., Bestuzheva, K., Chen, W., Eifler, L., Gasse, M., Gemander, P., Gleixner, A., Gottwald, L., Halbig, K., Hendel, G., Hojny, C., Koch, T., Le Bodic, P., Maher, S.J., Matter, F., Miltenberger, M., M\u00fchmer, E., M\u00fcller, B., Pfetsch, M.E., Schl\u00f6sser, F., Serrano, F., Shinano, Y., Tawfik, C., Vigerske, S., Wegscheider, F., Weninger, D., Witzig, J.: The SCIP Optimization Suite 7.0. Technical report, Optimization Online (2020)"},{"key":"2069_CR42","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1016\/0024-3795(79)90018-1","volume":"25","author":"FR Giles","year":"1979","unstructured":"Giles, F.R., Pulleyblank, W.R.: Total dual integrality and integer polyhedra. Linear Algebra Appl. 25, 191\u2013196 (1979)","journal-title":"Linear Algebra Appl."},{"issue":"5","key":"2069_CR43","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1090\/S0002-9904-1958-10224-4","volume":"64","author":"RE Gomory","year":"1958","unstructured":"Gomory, R.E.: Outline of an algorithm for integer solutions to linear programs. Bull. Am. Math. Soc. 64(5), 275\u2013278 (1958)","journal-title":"Bull. Am. Math. Soc."},{"key":"2069_CR44","unstructured":"Gurobi Optimization, LLC: Gurobi Optimizer Reference Manual (2021). https:\/\/www.gurobi.com"},{"key":"2069_CR45","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1007\/978-3-540-85097-7_20","volume-title":"International Conference on Combinatorial Optimization and Applications (COCOA2008). Lecture Notes in Computer Science","author":"G J\u00e4ger","year":"2008","unstructured":"J\u00e4ger, G., Molitor, P.: Algorithms and experimental study for the traveling salesman problem of second order. In: Yang, B., Du, D.Z., Wang, C.A. (eds.) International Conference on Combinatorial Optimization and Applications (COCOA2008). Lecture Notes in Computer Science, vol. 5165, pp. 211\u2013224. Springer, Berlin, Heidelberg (2008)"},{"key":"2069_CR46","doi-asserted-by":"crossref","first-page":"493","DOI":"10.1007\/s10589-019-00153-2","volume":"75","author":"K Kobayashi","year":"2020","unstructured":"Kobayashi, K., Takano, Y.: A branch-and-cut algorithm for solving mixed-integer semidefinite optimization problems. Comput. Optim. Appl. 75, 493\u2013513 (2020)","journal-title":"Comput. Optim. Appl."},{"issue":"4","key":"2069_CR47","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3005345","volume":"43","author":"N Krislock","year":"2017","unstructured":"Krislock, N., Malick, J., Roupin, F.: A semidefinite branch-and-bound method for solving binary quadratic problems. ACM Trans. Math. Softw. 43(4), 1\u201323 (2017)","journal-title":"ACM Trans. Math. Softw."},{"key":"2069_CR48","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1007\/s10107-010-0352-z","volume":"131","author":"AN Letchford","year":"2012","unstructured":"Letchford, A.N., S\u00f8rensen, M.M.: Binary positive semidefinite matrices and associated integer polytopes. Math. Program. Ser. A 131, 253\u2013271 (2012)","journal-title":"Math. Program. Ser. A"},{"key":"2069_CR49","unstructured":"L\u00f6fberg, J.: YALMIP: a toolbox for modeling and optimization in MATLAB. In: Proceedings of the CACSD Conference, Taipei, Taiwan (2004)"},{"issue":"2","key":"2069_CR50","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1287\/ijoo.2022.0079","volume":"5","author":"F Matter","year":"2022","unstructured":"Matter, F., Pfetsch, M.E.: Presolving for mixed-integer semidefinite optimization. INFORMS J. Optim. 5(2), 131\u2013154 (2022)","journal-title":"INFORMS J. Optim."},{"key":"2069_CR51","unstructured":"de Meijer, F.: Integrality and Cutting Planes in Semidefinite Programming Approaches for Combinatorial Optimization. Ph.D. thesis, Tilburg University (2023)"},{"key":"2069_CR52","doi-asserted-by":"crossref","first-page":"1096","DOI":"10.1007\/s10878-020-00547-7","volume":"39","author":"F de Meijer","year":"2020","unstructured":"de Meijer, F., Sotirov, R.: The quadratic cycle cover problem: special cases and efficient bounds. J. Comb. Optim. 39, 1096\u20131128 (2020)","journal-title":"J. Comb. Optim."},{"issue":"4","key":"2069_CR53","first-page":"1262","volume":"33","author":"F de Meijer","year":"2021","unstructured":"de Meijer, F., Sotirov, R.: SDP-based bounds for the quadratic cycle cover problem via cutting plane augmented Lagrangian methods and reinforcement learning. INFORMS J. Comput. 33(4), 1262\u20131276 (2021)","journal-title":"INFORMS J. Comput."},{"key":"2069_CR54","unstructured":"MOSEK, A.P.S.: The MOSEK optimization toolbox for MATLAB manual. Version 9.2 (2020)"},{"key":"2069_CR55","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. IEEE (2014)","DOI":"10.1109\/ICASSP.2014.6855103"},{"key":"2069_CR56","unstructured":"Punnen, A.P., Walter, M., Woods, B.D.: A characterization of linearizable instances of the quadratic traveling salesman problem (2018). arXiv:1708.07217"},{"key":"2069_CR57","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1007\/BF01100204","volume":"7","author":"M Ramana","year":"1995","unstructured":"Ramana, M., Goldman, A.J.: Some geometric results in semidefinite programming. J. Glob. Optim. 7, 33\u201350 (1995)","journal-title":"J. Glob. Optim."},{"key":"2069_CR58","doi-asserted-by":"crossref","unstructured":"Ramana, M.V.: Polyhedra, spectrahedra, and semidefinite programming. In: Topics in Semidefinite and Interior-Point Methods, Fields Institute Communications, vol. 18, pp. 27\u201338, Toronto, ON (1997)","DOI":"10.1090\/fic\/018\/03"},{"key":"2069_CR59","doi-asserted-by":"crossref","first-page":"376","DOI":"10.1287\/ijoc.3.4.376","volume":"3","author":"G Reinelt","year":"1991","unstructured":"Reinelt, G.: TSPLIB\u2014a traveling salesman problem library. INFORMS J. Comput. 3, 376\u2013384 (1991)","journal-title":"INFORMS J. Comput."},{"issue":"2","key":"2069_CR60","doi-asserted-by":"crossref","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 (2010)","journal-title":"Math. Program."},{"issue":"3","key":"2069_CR61","doi-asserted-by":"crossref","first-page":"584","DOI":"10.1016\/j.ejor.2016.03.031","volume":"253","author":"B Rostami","year":"2016","unstructured":"Rostami, B., Malucelli, F., Belotti, P., Gualandi, S.: Lower bounding procedure for the asymmetric quadratic traveling salesman problem. Eur. J. Oper. Res. 253(3), 584\u2013592 (2016)","journal-title":"Eur. J. Oper. Res."},{"key":"2069_CR62","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1016\/S0167-5060(08)70085-2","volume":"9","author":"A Schrijver","year":"1980","unstructured":"Schrijver, A.: On cutting planes. Ann. Discrete Math. 9, 291\u2013296 (1980)","journal-title":"Ann. Discrete Math."},{"key":"2069_CR63","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1016\/j.cor.2019.01.016","volume":"108","author":"R Stan\u011bk","year":"2019","unstructured":"Stan\u011bk, R., Greistorfer, P., Ladner, K., Pferschy, U.: Geometric and LP-based heuristics for angular travelling salesman problems in the plane. Comput. Oper. Res. 108, 97\u2013111 (2019)","journal-title":"Comput. Oper. Res."},{"key":"2069_CR64","first-page":"406","volume-title":"Integer Programming and Combinatorial Optimization (IPCO 2001). Lecture Notes in Computer Science","author":"C Stein","year":"2001","unstructured":"Stein, C., Wagner, D.P.: Approximation algorithms for the minimum bends traveling salesman problem. In: Aardal, K., Gerards, B. (eds.) Integer Programming and Combinatorial Optimization (IPCO 2001). Lecture Notes in Computer Science, vol. 2081, pp. 406\u2013425. Springer, Berlin (2001)"},{"key":"2069_CR65","doi-asserted-by":"crossref","first-page":"515","DOI":"10.1007\/s101070050103","volume":"86","author":"RA Stubbs","year":"1999","unstructured":"Stubbs, R.A., Mehrotra, S.: A branch-and-cut method for 0\u20131 mixed convex programming. Math. Program. 86, 515\u2013532 (1999)","journal-title":"Math. Program."},{"issue":"2","key":"2069_CR66","doi-asserted-by":"crossref","first-page":"196","DOI":"10.33581\/1561-4085-2020-23-2-196-206","volume":"23","author":"JJP Veerman","year":"2020","unstructured":"Veerman, J.J.P., Lyons, R.: A primer on Laplacian dynamics in directed graphs. Nonlinear Phenom. Complex Syst. 23(2), 196\u2013206 (2020)","journal-title":"Nonlinear Phenom. Complex Syst."},{"key":"2069_CR67","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1007\/s10107-020-01589-9","volume":"193","author":"AL Wang","year":"2022","unstructured":"Wang, A.L., Kilin\u00e7-Karzan, F.: On the tightness of SDP relaxations of QCQPs. Math. Program. 193, 33\u201373 (2022)","journal-title":"Math. Program."},{"key":"2069_CR68","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1016\/S0166-218X(00)00392-9","volume":"113","author":"H Wirth","year":"2001","unstructured":"Wirth, H., Steffan, J.: Reload cost problems: minimum diameter spanning tree. Discrete Appl. Math. 113, 73\u201385 (2001)","journal-title":"Discrete Appl. Math."},{"issue":"2","key":"2069_CR69","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1007\/s10878-020-00588-y","volume":"40","author":"BD Woods","year":"2020","unstructured":"Woods, B.D., Punnen, A.P.: A class of exponential neighbourhoods for the quadratic travelling salesman problem. J. Comb. Optim. 40(2), 303\u2013332 (2020)","journal-title":"J. Comb. Optim."},{"issue":"3","key":"2069_CR70","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1080\/03081080500054810","volume":"53","author":"CW Wu","year":"2005","unstructured":"Wu, C.W.: Algebraic connectivity of directed graphs. Linear Multilinear Algebra 53(3), 203\u2013223 (2005)","journal-title":"Linear Multilinear Algebra"},{"issue":"3","key":"2069_CR71","doi-asserted-by":"crossref","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."},{"key":"2069_CR72","doi-asserted-by":"crossref","first-page":"894","DOI":"10.1089\/cmb.2005.12.894","volume":"12","author":"X Zhao","year":"2005","unstructured":"Zhao, X., Huang, H., Speed, T.P.: Finding short DNA motifs using permuted Markov models. J. Comput. Biol. 12, 894\u2013906 (2005)","journal-title":"J. Comput. Biol."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-024-02069-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-024-02069-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-024-02069-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,15]],"date-time":"2025-01-15T16:52:29Z","timestamp":1736959949000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-024-02069-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,3,13]]},"references-count":72,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2025,1]]}},"alternative-id":["2069"],"URL":"https:\/\/doi.org\/10.1007\/s10107-024-02069-0","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,3,13]]},"assertion":[{"value":"25 January 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 February 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 March 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}