{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,31]],"date-time":"2025-10-31T14:21:02Z","timestamp":1761920462069,"version":"3.37.3"},"reference-count":49,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2018,5,25]],"date-time":"2018-05-25T00:00:00Z","timestamp":1527206400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2018,5,25]],"date-time":"2018-05-25T00:00:00Z","timestamp":1527206400000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100005713","name":"Office of the Secretary of Defense","doi-asserted-by":"publisher","award":["FA9550-10-1-0168"],"award-info":[{"award-number":["FA9550-10-1-0168"]}],"id":[{"id":"10.13039\/100005713","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2018,7]]},"DOI":"10.1007\/s10107-018-1301-5","type":"journal-article","created":{"date-parts":[[2018,5,25]],"date-time":"2018-05-25T11:46:30Z","timestamp":1527248790000},"page":"141-176","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":29,"title":["Strong formulations for quadratic optimization with M-matrices and indicator variables"],"prefix":"10.1007","volume":"170","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1220-808X","authenticated-orcid":false,"given":"Alper","family":"Atamt\u00fcrk","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3668-0653","authenticated-orcid":false,"given":"Andr\u00e9s","family":"G\u00f3mez","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,5,25]]},"reference":[{"key":"1301_CR1","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1007\/s00453-004-1085-2","volume":"39","author":"RK Ahuja","year":"2004","unstructured":"Ahuja, R.K., Hochbaum, D.S., Orlin, J.B.: A cut-based algorithm for the nonlinear dual of the minimum cost network flow problem. Algorithmica 39, 189\u2013208 (2004)","journal-title":"Algorithmica"},{"key":"1301_CR2","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1016\/j.orl.2008.12.009","volume":"37","author":"MS Akt\u00fcrk","year":"2009","unstructured":"Akt\u00fcrk, M.S., Atamt\u00fcrk, A., G\u00fcrel, S.: A strong conic quadratic reformulation for machine-job assignment with controllable processing times. Oper. Res. Lett. 37, 187\u2013191 (2009)","journal-title":"Oper. Res. Lett."},{"key":"1301_CR3","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1007\/s10107-012-0602-3","volume":"136","author":"KM Anstreicher","year":"2012","unstructured":"Anstreicher, K.M.: On convex relaxations for quadratically constrained quadratic programming. Math. Program. 136, 233\u2013251 (2012)","journal-title":"Math. Program."},{"key":"1301_CR4","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1002\/net.21769","volume":"71","author":"A Atamt\u00fcrk","year":"2018","unstructured":"Atamt\u00fcrk, A., Bhardwaj, A.: Network design with probabilistic capacities. Networks 71, 16\u201330 (2018)","journal-title":"Networks"},{"unstructured":"Atamt\u00fcrk, A., Gomez, A.: Submodularity in conic quadratic mixed 0\u20131 optimization. BCOL Research Report 16.02, IEOR, UC Berkeley. arXiv preprint \n                    arXiv:1705.05918\n                    \n                   (2017)","key":"1301_CR5"},{"unstructured":"Atamt\u00fcrk, A., Jeon, H.: Lifted polymatroid for mean-risk optimization with indicator variables. BCOL Research Report 17.01, IEOR, UC Berkeley. $$\\text{arXiv}\\,\\,\\text{ preprint }$$\n                           \n                    arXiv:1705.05915\n                    \n                   (2017)","key":"1301_CR6"},{"doi-asserted-by":"crossref","unstructured":"Atamt\u00fcrk, A., Narayanan, V.: Cuts for conic mixed integer programming. In: Fischetti, M., Williamson, D.P. (eds.) Proceedings of the 12th International IPCO Conference, pp. 16\u201329 (2007)","key":"1301_CR7","DOI":"10.1007\/978-3-540-72792-7_2"},{"key":"1301_CR8","doi-asserted-by":"publisher","first-page":"466","DOI":"10.1137\/0606047","volume":"6","author":"E Balas","year":"1985","unstructured":"Balas, E.: Disjunctive programming and a hierarchy of relaxations for discrete optimization problems. SIAM J. Algebr. Discrete Methods 6, 466\u2013486 (1985)","journal-title":"SIAM J. Algebr. Discrete Methods"},{"doi-asserted-by":"crossref","unstructured":"Belotti, P., G\u00f3ez, J.C., P\u00f3lik, I., Ralphs, T.K., Terlaky, T.: A conic representation of the convex hull of disjunctive sets and conic cuts for integer second order cone optimization. In: Numerical Analysis and Optimization, pp. 1\u201335. Springer (2015)","key":"1301_CR9","DOI":"10.1007\/978-3-319-17689-5_1"},{"key":"1301_CR10","doi-asserted-by":"publisher","first-page":"813","DOI":"10.1214\/15-AOS1388","volume":"44","author":"D Bertsimas","year":"2016","unstructured":"Bertsimas, D., King, A., Mazumder, R.: Best subset selection via a modern optimization lens. Ann. Stat. 44, 813\u2013852 (2016)","journal-title":"Ann. Stat."},{"key":"1301_CR11","first-page":"121","volume":"74","author":"D Bienstock","year":"1996","unstructured":"Bienstock, D.: Computational study of a family of mixed-integer quadratic programming problems. Math. Program. 74, 121\u2013140 (1996)","journal-title":"Math. Program."},{"key":"1301_CR12","doi-asserted-by":"publisher","first-page":"643","DOI":"10.1137\/120878963","volume":"24","author":"D Bienstock","year":"2014","unstructured":"Bienstock, D., Michalka, A.: Cutting-planes for optimization of convex functions over nonconvex sets. SIAM J. Optim. 24, 643\u2013677 (2014)","journal-title":"SIAM J. Optim."},{"key":"1301_CR13","doi-asserted-by":"publisher","first-page":"523","DOI":"10.1007\/s10107-016-1031-5","volume":"162","author":"N Boland","year":"2017","unstructured":"Boland, N., Dey, S.S., Kalinowski, T., Molinaro, M., Rigterink, F.: Bounding the gap between the McCormick relaxation and the convex hull for bilinear functions. Math. Program. 162, 523\u2013535 (2017a)","journal-title":"Math. Program."},{"unstructured":"Boland, N., Gupte, A., Kalinowski, T., Rigterink, F., Waterer, H.: Extended formulations for convex hulls of graphs of bilinear functions. arXiv preprint \n                    arXiv:1702.04813\n                    \n                   (2017b)","key":"1301_CR14"},{"key":"1301_CR15","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1007\/s10107-015-0891-4","volume":"151","author":"P Bonami","year":"2015","unstructured":"Bonami, P., Lodi, A., Tramontani, A., Wiese, S.: On mathematical programming with indicator constraints. Math. Program. 151, 191\u2013223 (2015)","journal-title":"Math. Program."},{"key":"1301_CR16","doi-asserted-by":"publisher","first-page":"1222","DOI":"10.1109\/34.969114","volume":"23","author":"Y Boykov","year":"2001","unstructured":"Boykov, Y., Veksler, O., Zabih, R.: Fast approximate energy minimization via graph cuts. IEEE Trans. Pattern Anal. Mach. Intell. 23, 1222\u20131239 (2001)","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"1301_CR17","doi-asserted-by":"publisher","first-page":"595","DOI":"10.1007\/s101070050106","volume":"86","author":"S Ceria","year":"1999","unstructured":"Ceria, S., Soares, J.: Convex programming for disjunctive convex optimization. Math. Program. 86, 595\u2013614 (1999)","journal-title":"Math. Program."},{"key":"1301_CR18","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511753886","volume-title":"Optimization Methods in Finance","author":"G Cornuejols","year":"2006","unstructured":"Cornuejols, G., T\u00fct\u00fcnc\u00fc, R.: Optimization Methods in Finance, vol. 5. Cambridge University Press, Cambridge (2006)"},{"doi-asserted-by":"crossref","unstructured":"Dong, H., Linderoth, J.: On valid inequalities for quadratic programming with continuous variables and binary indicators. In: Goemans, M., Correa, J. (eds.) Proceedings of IPCO 2013, pp. 169\u2013180. Springer, Berlin (2013)","key":"1301_CR19","DOI":"10.1007\/978-3-642-36694-9_15"},{"key":"1301_CR20","first-page":"69","volume-title":"Combinatorial Structures and Their Applications","author":"J Edmonds","year":"1970","unstructured":"Edmonds, J.: Submodular functions, matroids, and certain polyhedra. In: Guy, R., Hanani, H., Sauer, N., Sch\u00f6nenheim, J. (eds.) Combinatorial Structures and Their Applications, pp. 69\u201387. Gordon and Breach, Philadelphia (1970)"},{"key":"1301_CR21","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1007\/s10107-005-0594-3","volume":"106","author":"A Frangioni","year":"2006","unstructured":"Frangioni, A., Gentile, C.: Perspective cuts for a class of convex 0\u20131 mixed integer programs. Math. Program. 106, 225\u2013236 (2006)","journal-title":"Math. Program."},{"unstructured":"Frangioni, A., Gentile, C., Hungerford, J.: Decompositions of semidefinite matrices and the perspective reformulation of nonseparable quadratic programs. Report R-16-10, IASI, Rome (2016)","key":"1301_CR22"},{"key":"1301_CR23","doi-asserted-by":"publisher","first-page":"1936","DOI":"10.1109\/TAC.2011.2140770","volume":"56","author":"J Gao","year":"2011","unstructured":"Gao, J., Li, D.: Cardinality constrained linear-quadratic optimal control. IEEE Trans. Autom. Control 56, 1936\u20131941 (2011)","journal-title":"IEEE Trans. Autom. Control"},{"key":"1301_CR24","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1007\/s10107-010-0360-z","volume":"124","author":"O G\u00fcnl\u00fck","year":"2010","unstructured":"G\u00fcnl\u00fck, O., Linderoth, J.: Perspective reformulations of mixed integer nonlinear programs with indicator variables. Math. Program. 124, 183\u2013205 (2010)","journal-title":"Math. Program."},{"key":"1301_CR25","doi-asserted-by":"publisher","first-page":"537","DOI":"10.1007\/s10589-011-9424-0","volume":"52","author":"H Hijazi","year":"2012","unstructured":"Hijazi, H., Bonami, P., Cornu\u00e9jols, G., Ouorou, A.: Mixed-integer nonlinear programs featuring \u201con\/off\u201d constraints. Comput. Optim. Appl. 52, 537\u2013558 (2012)","journal-title":"Comput. Optim. Appl."},{"key":"1301_CR26","volume-title":"Convex Analysis and Minimization Algorithms I: Fundamentals","author":"JB Hiriart-Urruty","year":"2013","unstructured":"Hiriart-Urruty, J.B., Lemar\u00e9chal, C.: Convex Analysis and Minimization Algorithms I: Fundamentals, vol. 305. Springer, Berlin (2013)"},{"key":"1301_CR27","doi-asserted-by":"crossref","first-page":"169","DOI":"10.4208\/nmtma.2013.mssvm09","volume":"6","author":"DS Hochbaum","year":"2013","unstructured":"Hochbaum, D.S.: Multi-label markov random fields as an efficient and effective tool for image segmentation, total variations and regularization. Numer. Math. Theory Methods Appl. 6, 169\u2013198 (2013)","journal-title":"Numer. Math. Theory Methods Appl."},{"key":"1301_CR28","doi-asserted-by":"publisher","first-page":"388","DOI":"10.1287\/opre.13.3.388","volume":"13","author":"PL Iv\u0103nescu","year":"1965","unstructured":"Iv\u0103nescu, P.L.: Some network flow problems solved with pseudo-boolean programming. Oper. Res. 13, 388\u2013399 (1965)","journal-title":"Oper. Res."},{"key":"1301_CR29","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1016\/j.disopt.2016.04.008","volume":"24","author":"H Jeon","year":"2017","unstructured":"Jeon, H., Linderoth, J., Miller, A.: Quadratic cone cutting surfaces for quadratic programs with on\u2013off constraints. Discrete Optim. 24, 32\u201350 (2017)","journal-title":"Discrete Optim."},{"key":"1301_CR30","doi-asserted-by":"publisher","first-page":"439","DOI":"10.1016\/0022-247X(73)90219-9","volume":"41","author":"J Keilson","year":"1973","unstructured":"Keilson, J., Styan, G.P.H.: Markov chains and M-matrices: inequalities and equalities. J. Math. Anal. Appl. 41, 439\u2013459 (1973)","journal-title":"J. Math. Anal. Appl."},{"key":"1301_CR31","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1007\/s10107-015-0903-4","volume":"154","author":"F K\u0131l\u0131n\u00e7-Karzan","year":"2015","unstructured":"K\u0131l\u0131n\u00e7-Karzan, F., Y\u0131ld\u0131z, S.: Two-term disjunctions on the second-order cone. Math. Program. 154, 463\u2013491 (2015)","journal-title":"Math. Program."},{"key":"1301_CR32","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1109\/TPAMI.2004.1262177","volume":"26","author":"V Kolmogorov","year":"2004","unstructured":"Kolmogorov, V., Zabin, R.: What energy functions can be minimized via graph cuts? IEEE Trans. Pattern Anal. Mach. Intell. 26, 147\u2013159 (2004)","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"1301_CR33","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1007\/s10479-006-0145-1","volume":"152","author":"MS Lobo","year":"2007","unstructured":"Lobo, M.S., Fazel, M., Boyd, S.: Portfolio optimization with linear and fixed transaction costs. Ann. Oper. Res. 152, 341\u2013365 (2007)","journal-title":"Ann. Oper. Res."},{"key":"1301_CR34","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1007\/978-3-642-68874-4_10","volume-title":"Mathematical Programming The State of the Art: Bonn 1982","author":"L Lov\u00e1sz","year":"1983","unstructured":"Lov\u00e1sz, L.: Submodular functions and convexity. In: Bachem, A., Korte, B., Gr\u00f6tschel, M. (eds.) Mathematical Programming The State of the Art: Bonn 1982, pp. 235\u2013257. Springer, Berlin (1983)"},{"key":"1301_CR35","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1007\/s10107-012-0606-z","volume":"136","author":"J Luedtke","year":"2012","unstructured":"Luedtke, J., Namazifar, M., Linderoth, J.: Some results on the strength of relaxations of multilinear functions. Math. Program. 136, 325\u2013351 (2012)","journal-title":"Math. Program."},{"unstructured":"Luedtke, J., D\u2019Ambrosio, C., Linderoth, J., Schweiger, J.: Strong convex nonlinear relaxations of the pooling problem. arXiv preprint \n                    arXiv:1803.02955\n                    \n                   (2018)","key":"1301_CR36"},{"key":"1301_CR37","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1016\/0024-3795(80)90095-6","volume":"33","author":"FT Luk","year":"1980","unstructured":"Luk, F.T., Pagano, M.: Quadratic programming with M-matrices. Linear Algebra Appl. 33, 15\u201340 (1980)","journal-title":"Linear Algebra Appl."},{"unstructured":"Mahajan, A., Leyffer, S., Linderoth, J., Luedtke, J., Munson, T.: Minotaur: A mixed-integer nonlinear optimization toolkit. ANL\/MCS-P8010-0817, Argonne National Lab (2017)","key":"1301_CR38"},{"key":"1301_CR39","doi-asserted-by":"publisher","first-page":"575","DOI":"10.1007\/s10107-015-0866-5","volume":"155","author":"S Modaresi","year":"2016","unstructured":"Modaresi, S., K\u0131l\u0131n\u00e7, M.R., Vielma, J.P.: Intersection cuts for nonlinear integer programming: convexification techniques for structured sets. Math. Program. 155, 575\u2013611 (2016)","journal-title":"Math. Program."},{"key":"1301_CR40","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1007\/BF01588971","volume":"14","author":"GL Nemhauser","year":"1978","unstructured":"Nemhauser, G.L., Wolsey, L.A., Fisher, M.L.: An analysis of approximations for maximizing submodular set functions I. Math. Program. 14, 265\u2013294 (1978)","journal-title":"Math. Program."},{"key":"1301_CR41","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1007\/s10107-007-0189-2","volume":"118","author":"JB Orlin","year":"2009","unstructured":"Orlin, J.B.: A faster strongly polynomial time algorithm for submodular function minimization. Math. Program. 118, 237\u2013251 (2009)","journal-title":"Math. Program."},{"key":"1301_CR42","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1002\/net.3230050405","volume":"5","author":"JC Picard","year":"1975","unstructured":"Picard, J.C., Ratliff, H.D.: Minimum cuts and related problems. Networks 5, 357\u2013370 (1975)","journal-title":"Networks"},{"key":"1301_CR43","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1016\/0024-3795(77)90073-8","volume":"18","author":"RJ Plemmons","year":"1977","unstructured":"Plemmons, R.J.: M-matrix characterizations. I\u2014nonsingular M-matrices. Linear Algebra Appl. 18, 175\u2013188 (1977)","journal-title":"Linear Algebra Appl."},{"key":"1301_CR44","doi-asserted-by":"publisher","first-page":"550","DOI":"10.1287\/moor.20.3.550","volume":"20","author":"S Poljak","year":"1995","unstructured":"Poljak, S., Wolkowicz, H.: Convex relaxations of (0,1)-quadratic programming. Math. Oper. Res. 20, 550\u2013561 (1995)","journal-title":"Math. Oper. Res."},{"key":"1301_CR45","doi-asserted-by":"publisher","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."},{"doi-asserted-by":"crossref","unstructured":"Vielma, J.P.: Small and strong formulations for unions of convex sets from the cayley embedding. To appear in Mathematical Programming, arXiv preprint \n                    arXiv:1704.03954\n                    \n                   (2018)","key":"1301_CR46","DOI":"10.1007\/s10107-018-1258-4"},{"key":"1301_CR47","doi-asserted-by":"publisher","first-page":"857","DOI":"10.1109\/TSP.2012.2229996","volume":"61","author":"D Wei","year":"2013","unstructured":"Wei, D., Sestok, C.K., Oppenheim, A.V.: Sparse filter design under a quadratic constraint: low-complexity algorithms. IEEE Trans. Signal Process. 61, 857\u2013870 (2013)","journal-title":"IEEE Trans. Signal Process."},{"key":"1301_CR48","doi-asserted-by":"publisher","first-page":"1531","DOI":"10.1137\/15M1012232","volume":"27","author":"B Wu","year":"2017","unstructured":"Wu, B., Sun, X., Li, D., Zheng, X.: Quadratic convex reformulations for semicontinuous quadratic programming. SIAM J. Optim. 27, 1531\u20131553 (2017)","journal-title":"SIAM J. Optim."},{"key":"1301_CR49","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1016\/0024-3795(81)90278-0","volume":"35","author":"N Young","year":"1981","unstructured":"Young, N.: The rate of convergence of a matrix power series. Linear Algebra Appl. 35, 261\u2013278 (1981)","journal-title":"Linear Algebra Appl."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-018-1301-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-018-1301-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-018-1301-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,16]],"date-time":"2020-05-16T16:29:28Z","timestamp":1589646568000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-018-1301-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,5,25]]},"references-count":49,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,7]]}},"alternative-id":["1301"],"URL":"https:\/\/doi.org\/10.1007\/s10107-018-1301-5","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"type":"print","value":"0025-5610"},{"type":"electronic","value":"1436-4646"}],"subject":[],"published":{"date-parts":[[2018,5,25]]},"assertion":[{"value":"1 February 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 May 2018","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 May 2018","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}