{"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":1771748549419,"version":"3.50.1"},"reference-count":69,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2022,9,27]],"date-time":"2022-09-27T00:00:00Z","timestamp":1664236800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,9,27]],"date-time":"2022-09-27T00:00:00Z","timestamp":1664236800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000038","name":"natural sciences and engineering research council of canada","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2023,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We consider both facial reduction, <jats:bold>FR<\/jats:bold>, and symmetry reduction, <jats:bold>SR<\/jats:bold>, techniques for semidefinite programming, <jats:bold>SDP<\/jats:bold>. We show that the two together fit surprisingly well in an alternating direction method of multipliers, <jats:bold>ADMM<\/jats:bold>, approach. In fact, this approach allows for simply adding on nonnegativity constraints, and solving the doubly nonnegative, <jats:bold>DNN<\/jats:bold>\u00a0, relaxation of many classes of hard combinatorial problems. We also show that the singularity degree remains the same after <jats:bold>SR<\/jats:bold>, and that the <jats:bold>DNN<\/jats:bold>\u00a0relaxations considered here have singularity degree one, that is reduced to zero after <jats:bold>FR<\/jats:bold>. The combination of <jats:bold>FR<\/jats:bold>\u00a0and <jats:bold>SR<\/jats:bold>\u00a0leads to a significant improvement in both numerical stability and running time for both the <jats:bold>ADMM<\/jats:bold>\u00a0and interior point approaches. We test our method on various <jats:bold>DNN<\/jats:bold>\u00a0relaxations of hard combinatorial problems including quadratic assignment problems with sizes of more than <jats:inline-formula><jats:alternatives><jats:tex-math>$$n=500$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>=<\/mml:mo>\n                    <mml:mn>500<\/mml:mn>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. This translates to a semidefinite constraint of order 250,\u00a0000 and <jats:inline-formula><jats:alternatives><jats:tex-math>$$625\\times 10^8$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mn>625<\/mml:mn>\n                    <mml:mo>\u00d7<\/mml:mo>\n                    <mml:msup>\n                      <mml:mn>10<\/mml:mn>\n                      <mml:mn>8<\/mml:mn>\n                    <\/mml:msup>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> nonnegative constrained variables, before applying the reduction techniques.<\/jats:p>","DOI":"10.1007\/s10107-022-01890-9","type":"journal-article","created":{"date-parts":[[2022,9,27]],"date-time":"2022-09-27T18:03:55Z","timestamp":1664301835000},"page":"475-529","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Facial reduction for symmetry reduced semidefinite and doubly nonnegative programs"],"prefix":"10.1007","volume":"200","author":[{"given":"Hao","family":"Hu","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"}]},{"given":"Henry","family":"Wolkowicz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,9,27]]},"reference":[{"key":"1890_CR1","doi-asserted-by":"crossref","unstructured":"Andersen, E.D., Andersen, K.D.: The mosek interior point optimizer for linear programming: an implementation of the homogeneous algorithm. In High performance optimization, pp. 197\u2013232. Springer, (2000)","DOI":"10.1007\/978-1-4757-3216-0_8"},{"key":"1890_CR2","doi-asserted-by":"crossref","unstructured":"Bachoc, C., Gijswijt, D.C., Schrijver, A., Vallentin, F.: Invariant semidefinite programs. In: Anjos, F., Lasserre, J.B. (eds.) Hand book on semidefinite, conic and polynomial optimization, volume 166 of Internat. Ser. Oper. Res. Management Sci., pp. 219\u2013269. Springer, New York, (2012)","DOI":"10.1007\/978-1-4614-0769-0_9"},{"issue":"2","key":"1890_CR3","doi-asserted-by":"crossref","first-page":"300","DOI":"10.1016\/0022-0000(84)90071-0","volume":"28","author":"SN Bhatt","year":"1984","unstructured":"Bhatt, S.N., Leighton, F.T.: A framework for solving vlsi graph layout problems. J. Comput. Syst. Sci. 28(2), 300\u2013343 (1984)","journal-title":"J. Comput. Syst. Sci."},{"key":"1890_CR4","doi-asserted-by":"crossref","unstructured":"Boisvert, R.F., Pozo, R., Remington, K., Barrett, R.F., Dongarra, J.J.: Matrix market: a web resource for test matrix collections. Boisvert, R.F. (ed.) Quality of Numerical Software, pp. 125\u2013137. Springer, Boston, MA (1997)","DOI":"10.1007\/978-1-5041-2940-4_9"},{"key":"1890_CR5","doi-asserted-by":"crossref","unstructured":"Borwein, J.M., Wolkowicz, H.: Characterization of optimality for the abstract convex program with finite-dimensional range. J. Austral. Math. Soc. Ser. A, 30(4):390\u2013411, (1980\/81)","DOI":"10.1017\/S1446788700017882"},{"key":"1890_CR6","doi-asserted-by":"crossref","unstructured":"Borwein, J.M., Wolkowicz, H.: Facial reduction for a cone-convex programming problem. J. Austral. Math. Soc. Ser. A, 30(3):369\u2013380, (1980\/81)","DOI":"10.1017\/S1446788700017250"},{"issue":"2","key":"1890_CR7","doi-asserted-by":"crossref","first-page":"495","DOI":"10.1016\/0022-247X(81)90138-4","volume":"83","author":"JM Borwein","year":"1981","unstructured":"Borwein, J.M., Wolkowicz, H.: Regularizing the abstract convex program. J. Math. Anal. Appl. 83(2), 495\u2013530 (1981)","journal-title":"J. Math. Anal. Appl."},{"issue":"1","key":"1890_CR8","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1561\/2200000016","volume":"3","author":"S Boyd","year":"2011","unstructured":"Boyd, S., Parikh, N., Chu, E., Peleato, B., Eckstein, J.: Distributed optimization and statistical learning via the alternating direction method of multipliers. Found. Trends Mach. Learn. 3(1), 1\u2013122 (2011)","journal-title":"Found. Trends Mach. Learn."},{"issue":"4","key":"1890_CR9","doi-asserted-by":"crossref","first-page":"391","DOI":"10.1023\/A:1008293323270","volume":"10","author":"RE Burkard","year":"1997","unstructured":"Burkard, R.E., Karisch, S.E., Rendl, F.: QAPLIB\u2013a quadratic assignment problem library. J. Global Optim. 10(4), 391\u2013403 (1997)","journal-title":"J. Global Optim."},{"key":"1890_CR10","unstructured":"Chen, Y., Ye, X.: Projection onto a simplex (2011). arXiv:1101.6081"},{"issue":"1\u20132","key":"1890_CR11","doi-asserted-by":"crossref","first-page":"575","DOI":"10.1007\/s10107-015-0946-6","volume":"158","author":"L Condat","year":"2016","unstructured":"Condat, L.: Fast projection onto the simplex and the $$l_{1}$$ ball. Math. Program. 158(1\u20132), 575\u2013585 (2016)","journal-title":"Math. Program."},{"issue":"1","key":"1890_CR12","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.ejor.2009.01.025","volume":"201","author":"E de Klerk","year":"2010","unstructured":"de Klerk, E.: Exploiting special structure in semidefinite programming: a survey of theory and applications. Eur. J. Oper. Res. 201(1), 1\u201310 (2010)","journal-title":"Eur. J. Oper. Res."},{"key":"1890_CR13","doi-asserted-by":"crossref","unstructured":"de\u00a0Klerk, E., de\u00a0Oliveira\u00a0Filho, F.M., Pasechnik, D.V.: Relaxations of combinatorial problems via association schemes. In: Handbook on semidefinite, conic and polynomial optimization, volume 166 of Internat. Ser. Oper. Res. Management Sci., pp. 171\u2013199. Springer, New York, (2012)","DOI":"10.1007\/978-1-4614-0769-0_7"},{"key":"1890_CR14","doi-asserted-by":"crossref","unstructured":"de\u00a0Klerk, E., Dobre, C., $$\\dot{{{\\rm P}}}$$asechnik, D.V.: Numerical block diagonalization of matrix $$\\ast $$-algebras with application to semidefinite programming. Math. Program., 129(1, Ser. B):91\u2013111, (2011)","DOI":"10.1007\/s10107-011-0461-3"},{"issue":"2","key":"1890_CR15","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1007\/s10107-008-0246-5","volume":"122","author":"E de Klerk","year":"2010","unstructured":"de Klerk, E., Sotirov, R.: Exploiting group symmetry in semidefinite programming relaxations of the quadratic assignment problem. Math. Program. 122(2), 225\u2013246 (2010)","journal-title":"Math. Program."},{"issue":"1\u20132","key":"1890_CR16","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1007\/s10107-010-0411-5","volume":"133","author":"E de Klerk","year":"2012","unstructured":"de Klerk, E., Sotirov, R.: Improved semidefinite programming bounds for quadratic assignment problems with suitable symmetry. Math. Program. 133(1\u20132), 75\u201391 (2012)","journal-title":"Math. Program."},{"key":"1890_CR17","unstructured":"Delsarte, P.: An algebraic approach to the association schemes of coding theory. PhD thesis, Universite Catholique de Louvain, Louvain, France, (1973)"},{"key":"1890_CR18","doi-asserted-by":"crossref","unstructured":"Drusvyatskiy, D., Wolkowicz, H.: The many faces of degeneracy in conic optimization. Found. Trends\u00ae Optim., 3(2):77\u2013170, (2017)","DOI":"10.1561\/2400000011"},{"key":"1890_CR19","doi-asserted-by":"crossref","unstructured":"Eckstein, J.: Deriving solution value bounds from the ADMM. Optim. Lett. 14(6), 1289\u20131303 (2020)","DOI":"10.1007\/s11590-020-01584-1"},{"key":"1890_CR20","doi-asserted-by":"crossref","unstructured":"Fu, B., Oprisan, S.A., Xu, L.: Multi-directional width-bounded geometric separator and protein folding. In: International Symposium on Algorithms and Computation, pp 995\u20131006. Springer, (2005)","DOI":"10.1007\/11602613_99"},{"key":"1890_CR21","first-page":"235","volume":"79","author":"K Fujisawa","year":"1997","unstructured":"Fujisawa, K., Kojima, M., Nakata, K.: Exploiting sparsity in primal-dual interior-point methods for semidefinite programming. Math. Program. 79, 235\u2013253 (1997)","journal-title":"Math. Program."},{"issue":"1\u20133","key":"1890_CR22","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1016\/j.jpaa.2003.12.011","volume":"192","author":"K Gatermann","year":"2004","unstructured":"Gatermann, K., Parrilo, P.A.: Symmetry groups, semidefinite programs, and sums of squares. J. Pure Appl. Algebra 192(1\u20133), 95\u2013128 (2004)","journal-title":"J. Pure Appl. Algebra"},{"issue":"1\u20133","key":"1890_CR23","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1016\/j.jpaa.2003.12.011","volume":"192","author":"K Gatermann","year":"2004","unstructured":"Gatermann, K., Parrilo, P.A.: Symmetry groups, semidefinite programs, and sums of squares. J. Pure Appl. Algebra 192(1\u20133), 95\u2013128 (2004)","journal-title":"J. Pure Appl. Algebra"},{"key":"1890_CR24","unstructured":"Gijswijt, D.: Matrix algebras and semidefinite programming techniques for codes. PhD Thesis, (2010)"},{"issue":"1\u20132","key":"1890_CR25","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1080\/03081089508818381","volume":"39","author":"C Helmberg","year":"1995","unstructured":"Helmberg, C., Rendl, F., Mohar, B., Poljak, S.: A spectral approach to bandwidth and separator problems in graphs. Linear Multilinear Algebra 39(1\u20132), 73\u201390 (1995)","journal-title":"Linear Multilinear Algebra"},{"key":"1890_CR26","doi-asserted-by":"crossref","unstructured":"Hu, H., Sotirov, R.: On solving the quadratic shortest path problem. INFORMS J. Comput. 32(2), 219\u2013233 (2020)","DOI":"10.1287\/ijoc.2018.0861"},{"issue":"2\u20133","key":"1890_CR27","doi-asserted-by":"crossref","first-page":"457","DOI":"10.1080\/02331934.2018.1477943","volume":"68","author":"B Jargalsaikhan","year":"2019","unstructured":"Jargalsaikhan, B., R\u00fcckmann, J.J.: A note on strict complementarity for the doubly non-negative cone. Optimization 68(2\u20133), 457\u2013464 (2019)","journal-title":"Optimization"},{"key":"1890_CR28","unstructured":"Johnson, D.S., Mehrotra, A., Trick, M.A.: COLOR02\/03\/04: Graph coloring and its generalizations, (2002)"},{"key":"1890_CR29","doi-asserted-by":"crossref","first-page":"293","DOI":"10.1023\/A:1015366416311","volume":"2","author":"Y Kanno","year":"2001","unstructured":"Kanno, Y., Ohsaki, M., Murota, K., Katoh, N.: Group symmetry in interior-point methods for semidefinite program. Optim. Eng. 2, 293\u2013320 (2001)","journal-title":"Optim. Eng."},{"key":"1890_CR30","doi-asserted-by":"crossref","unstructured":"Karisch, S.E., Rendl, F.: Semidefinite programming and graph equipartition. In Topics in Semidefinite and Interior-Point Methods, volume\u00a018 of The Fields Institute for Research in Mathematical Sciences, Communications Series, Providence, Rhode Island, 1998. American Mathematical Society","DOI":"10.1090\/fic\/018\/06"},{"key":"1890_CR31","unstructured":"Kojima, M., Kojima, S., Hara, S.: Linear algebra for semidefinite programming. Technical Report 1004, Dept. of Information Sciences, Tokyo Institute of Technology, Tokyo, Japan, 1997. Linear matrix inequalities and positive semidefinite programming (Japanese) (Kyoto, 1996)"},{"key":"1890_CR32","doi-asserted-by":"crossref","unstructured":"Kungurtsev, V., Marecek, J.: A two-step pre-processing for semidefinite programming. In: 59th IEEE Conference on Decision and Control (CDC), pp. 384\u2013389 (2020)","DOI":"10.1109\/CDC42340.2020.9304494"},{"key":"1890_CR33","unstructured":"Leighton, F.T.: Complexity issues in vlsi: optimal layouts for the shu e exchange and other networks, (1983)"},{"key":"1890_CR34","unstructured":"Li, M., Andersen, D.G., Smola, A.J.: Graph partitioning via parallel submodular approximation to accelerate distributed machine learning. arXiv preprint arXiv:1505.04636, (2015)"},{"issue":"3","key":"1890_CR35","doi-asserted-by":"crossref","first-page":"853","DOI":"10.1007\/s10589-020-00261-4","volume":"78","author":"X Li","year":"2021","unstructured":"Li, X., Pong, T.K., Sun, H., Wolkowicz, H.: A strictly contractive Peaceman\u2013Rachford splitting method for the doubly nonnegative relaxation of the minimum cut problem. Comput. Optim. Appl. 78(3), 853\u2013891 (2021)","journal-title":"Comput. Optim. Appl."},{"issue":"2","key":"1890_CR36","doi-asserted-by":"crossref","first-page":"346","DOI":"10.1137\/0716027","volume":"16","author":"RJ Lipton","year":"1979","unstructured":"Lipton, R.J., Rose, D.J., Tarjan, R.E.: Generalized nested dissection. SIAM J. Numer. Anal. 16(2), 346\u2013358 (1979)","journal-title":"SIAM J. Numer. Anal."},{"issue":"3","key":"1890_CR37","doi-asserted-by":"crossref","first-page":"615","DOI":"10.1137\/0209046","volume":"9","author":"RJ Lipton","year":"1980","unstructured":"Lipton, R.J., Tarjan, R.E.: Applications of a planar separator theorem. SIAM J. Comput. 9(3), 615\u2013627 (1980)","journal-title":"SIAM J. Comput."},{"key":"1890_CR38","unstructured":"L\u00f6fberg, J.: Yalmip: A toolbox for modeling and optimization in matlab. In: Proceedings of the CACSD Conference, volume\u00a03. Taipei, Taiwan, (2004)"},{"issue":"5","key":"1890_CR39","doi-asserted-by":"crossref","first-page":"1007","DOI":"10.1109\/TAC.2009.2017144","volume":"54","author":"J L\u00f6fberg","year":"2009","unstructured":"L\u00f6fberg, J.: Pre- and post-processing sum-of-squares programs in practice. IEEE Trans. Autom. Control 54(5), 1007\u20131011 (2009)","journal-title":"IEEE Trans. Autom. Control"},{"issue":"3","key":"1890_CR40","doi-asserted-by":"crossref","first-page":"2304","DOI":"10.1137\/15M1051634","volume":"28","author":"BF Louren\u00e7o","year":"2018","unstructured":"Louren\u00e7o, B.F., Muramatsu, M., Tsuchiya, T.: Facial reduction and partial polyhedrality. SIAM J. Optim. 28(3), 2304\u20132326 (2018)","journal-title":"SIAM J. Optim."},{"issue":"2","key":"1890_CR41","doi-asserted-by":"crossref","first-page":"364","DOI":"10.1137\/S1064827594262613","volume":"19","author":"GL Miller","year":"1998","unstructured":"Miller, G.L., Teng, S.-H., Thurston, W., Vavasis, S.A.: Geometric separators for finite-element meshes. SIAM J. Sci. Comput. 19(2), 364\u2013386 (1998)","journal-title":"SIAM J. Sci. Comput."},{"issue":"6","key":"1890_CR42","doi-asserted-by":"crossref","first-page":"3408","DOI":"10.1137\/090748834","volume":"20","author":"H Mittelmann","year":"2010","unstructured":"Mittelmann, H., Peng, J.: Estimating bounds for quadratic assignment problems associated with hamming and manhattan distance matrices based on semidefinite programming. SIAM J. Optim. 20(6), 3408\u20133426 (2010)","journal-title":"SIAM J. Optim."},{"issue":"1","key":"1890_CR43","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1007\/s13160-010-0006-9","volume":"27","author":"K Murota","year":"2010","unstructured":"Murota, K., Kanno, Y., Kojima, M., Kojima, S.: A numerical algorithm for block-diagonal decomposition of matrix $$*$$-algebras with application to semidefinite programming. Jpn. J. Ind. Appl. Math. 27(1), 125\u2013160 (2010)","journal-title":"Jpn. J. Ind. Appl. Math."},{"issue":"4","key":"1890_CR44","doi-asserted-by":"crossref","first-page":"631","DOI":"10.1007\/s12532-018-0148-3","volume":"10","author":"DE Oliveira","year":"2018","unstructured":"Oliveira, D.E., Wolkowicz, H., Xu, Y.: ADMM for the SDP relaxation of the QAP. Math. Program. Comput. 10(4), 631\u2013658 (2018)","journal-title":"Math. Program. Comput."},{"issue":"1","key":"1890_CR45","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1007\/s10107-019-01372-5","volume":"181","author":"F Permenter","year":"2020","unstructured":"Permenter, F., Parrilo, P.A.: Dimension reduction for semidefinite programs via Jordan algebras. Math. Program. 181(1), 51\u201384 (2020)","journal-title":"Math. Program."},{"key":"1890_CR46","unstructured":"Permenter, F.N.: Reduction methods in semidefinite and conic optimization. PhD thesis, Massachusetts Institute of Technology, (2017)"},{"issue":"12","key":"1890_CR47","doi-asserted-by":"crossref","first-page":"3046","DOI":"10.1016\/j.cor.2012.03.008","volume":"39","author":"H Pirim","year":"2012","unstructured":"Pirim, H., Ek\u015fio\u011flu, B., Perkins, A.D., Y\u00fcceer, \u00c7.: Clustering of high throughput gene expression data. Computers Oper. Res. 39(12), 3046\u20133061 (2012)","journal-title":"Computers Oper. Res."},{"issue":"2","key":"1890_CR48","doi-asserted-by":"crossref","first-page":"333","DOI":"10.1007\/s10589-015-9779-8","volume":"63","author":"TK Pong","year":"2016","unstructured":"Pong, T.K., Sun, H., Wang, N., Wolkowicz, H.: Eigenvalue, quadratic programming, and semidefinite programming relaxations for a cut minimization problem. Comput. Optim. Appl. 63(2), 333\u2013364 (2016)","journal-title":"Comput. Optim. Appl."},{"issue":"1","key":"1890_CR49","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1137\/050637467","volume":"18","author":"J Povh","year":"2007","unstructured":"Povh, J., Rendl, F.: A copositive programming approach to graph partitioning. SIAM J. Optim. 18(1), 223\u2013241 (2007)","journal-title":"SIAM J. Optim."},{"issue":"3","key":"1890_CR50","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1016\/j.disopt.2009.01.002","volume":"6","author":"J Povh","year":"2009","unstructured":"Povh, J., Rendl, F.: Copositive and semidefinite relaxations of the quadratic assignment problem. Discrete Optim. 6(3), 231\u2013241 (2009)","journal-title":"Discrete Optim."},{"issue":"1","key":"1890_CR51","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1007\/s10589-017-9943-4","volume":"69","author":"F Rendl","year":"2018","unstructured":"Rendl, F., Sotirov, R.: The min-cut and vertex separator problem. Comput. Optim. Appl. 69(1), 159\u2013187 (2018)","journal-title":"Comput. Optim. Appl."},{"issue":"4","key":"1890_CR52","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1109\/TIT.1979.1056072","volume":"25","author":"A Schrijver","year":"1979","unstructured":"Schrijver, A.: A comparison of the Delsarte and Lov\u00e1sz bounds. IEEE Trans. Inf. Theory 25(4), 425\u2013429 (1979)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"1","key":"1890_CR53","doi-asserted-by":"crossref","first-page":"16","DOI":"10.1287\/ijoc.1120.0542","volume":"26","author":"R Sotirov","year":"2013","unstructured":"Sotirov, R.: An efficient semidefinite programming relaxation for the graph partition problem. INFORMS J. Comput. 26(1), 16\u201330 (2013)","journal-title":"INFORMS J. Comput."},{"issue":"1","key":"1890_CR54","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1007\/s10479-017-2575-3","volume":"265","author":"R Sotirov","year":"2018","unstructured":"Sotirov, R.: Graph bisection revisited. Ann. Oper. Res. 265(1), 143\u2013154 (2018)","journal-title":"Ann. Oper. Res."},{"key":"1890_CR55","unstructured":"Sremac, S.: Error bounds and singularity degree in semidefinite programming. PhD thesis, University of Waterloo, (2019)"},{"issue":"1","key":"1890_CR56","doi-asserted-by":"crossref","first-page":"812","DOI":"10.1137\/19M1289327","volume":"31","author":"S Sremac","year":"2021","unstructured":"Sremac, S., Woerdeman, H.J., Wolkowicz, H.: Error bounds and singularity degree in semidefinite programming. SIAM J. Optim. 31(1), 812\u2013836 (2021)","journal-title":"SIAM J. Optim."},{"issue":"1\u20134","key":"1890_CR57","doi-asserted-by":"crossref","first-page":"625","DOI":"10.1080\/10556789908805766","volume":"11","author":"JF Sturm","year":"1999","unstructured":"Sturm, J.F.: Using SeDuMi 1.02, a Matlab toolbox for optimization over symmetric cones. Optim. Methods Softw. 11(1\u20134), 625\u2013653 (1999)","journal-title":"Optim. Methods Softw."},{"issue":"4","key":"1890_CR58","doi-asserted-by":"crossref","first-page":"1228","DOI":"10.1137\/S1052623498338606","volume":"10","author":"JF Sturm","year":"2000","unstructured":"Sturm, J.F.: Error bounds for linear matrix inequalities. SIAM J. Optim. 10(4), 1228\u20131248 (2000)","journal-title":"SIAM J. Optim."},{"issue":"1","key":"1890_CR59","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1080\/10556788.2019.1576176","volume":"35","author":"D Sun","year":"2020","unstructured":"Sun, D., Toh, K.C., Yuan, Y., Zhao, X.Y.: SDPNAL $$+$$: a Matlab software for semidefinite programming with bound constraints (version 1.0). Optim. Methods Softw. 35(1), 87\u2013115 (2020)","journal-title":"Optim. Methods Softw."},{"key":"1890_CR60","unstructured":"Truetsch, U.: A semidefinite programming based branch-and-bound framework for the quadratic assignment problem. Tilburg University, (2014)"},{"issue":"4","key":"1890_CR61","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1016\/S0167-6377(01)00093-1","volume":"29","author":"L Tun\u00e7el","year":"2001","unstructured":"Tun\u00e7el, L.: On the Slater condition for the SDP relaxations of nonconvex sets. Oper. Res. Lett. 29(4), 181\u2013186 (2001)","journal-title":"Oper. Res. Lett."},{"issue":"1","key":"1890_CR62","doi-asserted-by":"crossref","first-page":"360","DOI":"10.1016\/j.laa.2008.07.025","volume":"430","author":"F Vallentin","year":"2009","unstructured":"Vallentin, F.: Symmetry in semidefinite programs. Linear Algebra Appl. 430(1), 360\u2013369 (2009)","journal-title":"Linear Algebra Appl."},{"issue":"2","key":"1890_CR63","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1007\/s10107-014-0817-6","volume":"151","author":"ER van Dam","year":"2015","unstructured":"van Dam, E.R., Sotirov, R.: Semidefinite programming and eigenvalue bounds for the graph partition problem. Math. Program. 151(2), 379\u2013404 (2015)","journal-title":"Math. Program."},{"issue":"4","key":"1890_CR64","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1561\/2400000006","volume":"1","author":"L Vandenberghe","year":"2015","unstructured":"Vandenberghe, L., Andersen, M.S.: Chordal graphs and semidefinite optimization. Found. Trends Opt. 1(4), 241\u2013433 (2015)","journal-title":"Found. Trends Opt."},{"issue":"5","key":"1890_CR65","doi-asserted-by":"crossref","first-page":"361","DOI":"10.1016\/j.orl.2010.05.011","volume":"38","author":"H Waki","year":"2010","unstructured":"Waki, H., Muramatsu, M.: A facial reduction algorithm for finding sparse SOS representations. Oper. Res. Lett. 38(5), 361\u2013365 (2010)","journal-title":"Oper. Res. Lett."},{"issue":"6","key":"1890_CR66","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1112\/plms\/s2-6.1.77","volume":"2","author":"JHM Wedderburn","year":"1908","unstructured":"Wedderburn, J.H.M.: On hypercomplex numbers. Proc. Lond. Math. Soc. 2(6), 77\u2013118 (1908)","journal-title":"Proc. Lond. Math. Soc."},{"key":"1890_CR67","doi-asserted-by":"crossref","unstructured":"Wolkowicz, H., Zhao, Q.: Semidefinite programming relaxations for the graph partitioning problem. Discrete Appl. Math., 96\/97:461\u2013479, 1999. Selected for the special Editors\u2019 Choice, Edition (1999)","DOI":"10.1016\/S0166-218X(99)00102-X"},{"issue":"3","key":"1890_CR68","doi-asserted-by":"crossref","first-page":"331","DOI":"10.1007\/s12532-015-0082-6","volume":"7","author":"L Yang","year":"2015","unstructured":"Yang, L., Sun, D., Toh, K.-C.: $${\\rm SDPNAL}+$$: a majorized semismooth Newton-CG augmented Lagrangian method for semidefinite programming with nonnegative constraints. Math. Program. Comput. 7(3), 331\u2013366 (2015)","journal-title":"Math. Program. Comput."},{"key":"1890_CR69","doi-asserted-by":"crossref","unstructured":"Zhao, Q., Karisch, S.E., Rendl, F., Wolkowicz, H., Semidefinite programming relaxations for the quadratic assignment problem. J. Comb. Optim. 2(1):71\u2013109 (1998)","DOI":"10.1023\/A:1009795911987"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-022-01890-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-022-01890-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-022-01890-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,18]],"date-time":"2023-05-18T23:08:04Z","timestamp":1684451284000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-022-01890-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,9,27]]},"references-count":69,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,6]]}},"alternative-id":["1890"],"URL":"https:\/\/doi.org\/10.1007\/s10107-022-01890-9","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,9,27]]},"assertion":[{"value":"21 December 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 September 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 September 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}