{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:08:00Z","timestamp":1750219680234,"version":"3.41.0"},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2024,7,22]],"date-time":"2024-07-22T00:00:00Z","timestamp":1721606400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,7,22]],"date-time":"2024-07-22T00:00:00Z","timestamp":1721606400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/100000181","name":"Air Force Office of Scientific Research","doi-asserted-by":"publisher","award":["FA9550-23-1-0123","FA9550-23-1-0433"],"award-info":[{"award-number":["FA9550-23-1-0123","FA9550-23-1-0433"]}],"id":[{"id":"10.13039\/100000181","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2025,7]]},"DOI":"10.1007\/s10107-024-02122-y","type":"journal-article","created":{"date-parts":[[2024,7,22]],"date-time":"2024-07-22T09:01:54Z","timestamp":1721638914000},"page":"717-761","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["The pseudo-Boolean polytope and polynomial-size extended formulations for binary polynomial optimization"],"prefix":"10.1007","volume":"212","author":[{"given":"Alberto","family":"Del Pia","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7097-1676","authenticated-orcid":false,"given":"Aida","family":"Khajavirad","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,7,22]]},"reference":[{"issue":"1\u20133","key":"2122_CR1","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/S0166-218X(98)00136-X","volume":"89","author":"E Balas","year":"1998","unstructured":"Balas, E.: Disjunctive programming: properties of the convex hull of feasible points. Discret. Appl. Math. 89(1\u20133), 3\u201344 (1998)","journal-title":"Discret. Appl. Math."},{"key":"2122_CR2","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1007\/BF02592023","volume":"36","author":"F Barahona","year":"1986","unstructured":"Barahona, F., Mahjoub, A.R.: On the cut polytope. Math. Program. 36, 157\u2013173 (1986)","journal-title":"Math. Program."},{"key":"2122_CR3","doi-asserted-by":"publisher","first-page":"479","DOI":"10.1145\/2402.322389","volume":"30","author":"C Beeri","year":"1983","unstructured":"Beeri, C., Fagin, R., Maier, D., Yannakakis, M.: On the desirability of acyclic database schemes. J. ACM 30, 479\u2013513 (1983)","journal-title":"J. ACM"},{"issue":"4\u20135","key":"2122_CR4","doi-asserted-by":"publisher","first-page":"597","DOI":"10.1080\/10556780903087124","volume":"24","author":"P Belotti","year":"2009","unstructured":"Belotti, P., Lee, J., Liberti, L., Margot, F., W\u00e4chter, A.: Branching and bounds tightening echniques for non-convex MINLP. Optim. Method. Softw. 24(4\u20135), 597\u2013634 (2009)","journal-title":"Optim. Method. Softw."},{"issue":"2","key":"2122_CR5","doi-asserted-by":"publisher","first-page":"1121","DOI":"10.1137\/15M1054079","volume":"28","author":"D Bienstock","year":"2018","unstructured":"Bienstock, D., Munoz, G.: LP formulations for polynomial optimization problems. SIAM J. Optim. 28(2), 1121\u20131150 (2018)","journal-title":"SIAM J. Optim."},{"issue":"2","key":"2122_CR6","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1016\/0167-6377(90)90044-6","volume":"9","author":"E Boros","year":"1990","unstructured":"Boros, E., Crama, Y., Hammer, P.L.: Upper-bounds for quadratic 0\u20131 maximization. Oper. Res. Lett. 9(2), 73\u201379 (1990)","journal-title":"Oper. Res. Lett."},{"key":"2122_CR7","doi-asserted-by":"publisher","first-page":"687","DOI":"10.1007\/s10878-019-00511-0","volume":"39","author":"E Boros","year":"2020","unstructured":"Boros, E., Crama, Y., Rodr\u00edguez-Heck, E.: Compact quadratizations for pseudo-Boolean functions. J. Comb. Optim. 39, 687\u2013707 (2020)","journal-title":"J. Comb. Optim."},{"issue":"1\u20133","key":"2122_CR8","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1016\/S0166-218X(01)00341-9","volume":"123","author":"E Boros","year":"2002","unstructured":"Boros, E., Hammer, P.L.: Pseudo-Boolean optimization. Discret. Appl. Math. 123(1\u20133), 155\u2013225 (2002)","journal-title":"Discret. Appl. Math."},{"issue":"3","key":"2122_CR9","first-page":"54:1","volume":"49","author":"J Brault-Baron","year":"2016","unstructured":"Brault-Baron, J.: Hypergraph acyclicity revisited. ACM Comput. Surv. 49(3), 54:1-54:26 (2016)","journal-title":"ACM Comput. Surv."},{"issue":"1","key":"2122_CR10","doi-asserted-by":"publisher","first-page":"102","DOI":"10.1016\/j.ejor.2018.07.045","volume":"273","author":"C Buchheim","year":"2019","unstructured":"Buchheim, C., Crama, Y., Rodr\u00edguez-Heck, E.: Berge-acyclic multilinear 0\u20131 optimization problems. Eur. J. Oper. Res. 273(1), 102\u2013107 (2019)","journal-title":"Eur. J. Oper. Res."},{"key":"2122_CR11","doi-asserted-by":"crossref","unstructured":"Cornu\u00e9jols, G.: Combinatorial optimization: packing and covering, CBMS-NSF regional conference series in applied mathematics, vol.\u00a074. SIAM (2001)","DOI":"10.1137\/1.9780898717105"},{"key":"2122_CR12","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1007\/BF01587085","volume":"44","author":"Y Crama","year":"1989","unstructured":"Crama, Y.: Recognition problems for special classes of polynomials in 0\u20131 variables. Math. Program. 44, 139\u2013155 (1989)","journal-title":"Math. Program."},{"key":"2122_CR13","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1016\/j.disopt.2017.02.001","volume":"25","author":"Y Crama","year":"2017","unstructured":"Crama, Y., Rodr\u00edguez-Heck, E.: A class of valid inequalities for multilinear $$0--1$$ optimization problems. Discret. Optim. 25, 28\u201347 (2017)","journal-title":"Discret. Optim."},{"issue":"4","key":"2122_CR14","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1287\/ijoo.2019.0049","volume":"3","author":"A Del Pia","year":"2021","unstructured":"Del Pia, A., Di Gregorio, S.: Chv\u00e1tal rank in binary polynomial optimization. INFORMS J. Optim. 3(4), 315\u2013349 (2021)","journal-title":"INFORMS J. Optim."},{"key":"2122_CR15","doi-asserted-by":"publisher","first-page":"2189","DOI":"10.1007\/s00453-022-01086-9","volume":"85","author":"A Del Pia","year":"2023","unstructured":"Del Pia, A., Di Gregorio, S.: On the complexity of binary polynomial optimization over acyclic hypergraphs. Algorithmica 85, 2189\u20132213 (2023)","journal-title":"Algorithmica"},{"issue":"2","key":"2122_CR16","doi-asserted-by":"publisher","first-page":"389","DOI":"10.1287\/moor.2016.0804","volume":"42","author":"A Del Pia","year":"2017","unstructured":"Del Pia, A., Khajavirad, A.: A polyhedral study of binary polynomial programs. Math. Oper. Res. 42(2), 389\u2013410 (2017)","journal-title":"Math. Oper. Res."},{"issue":"2","key":"2122_CR17","doi-asserted-by":"publisher","first-page":"1049","DOI":"10.1137\/16M1095998","volume":"28","author":"A Del Pia","year":"2018","unstructured":"Del Pia, A., Khajavirad, A.: The multilinear polytope for acyclic hypergraphs. SIAM J. Optim. 28(2), 1049\u20131076 (2018)","journal-title":"SIAM J. Optim."},{"issue":"2","key":"2122_CR18","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1007\/s10107-017-1158-z","volume":"170","author":"A Del Pia","year":"2018","unstructured":"Del Pia, A., Khajavirad, A.: On decomposability of multilinear sets. Math. Program. Ser. A 170(2), 387\u2013415 (2018)","journal-title":"Math. Program. Ser. A"},{"issue":"3","key":"2122_CR19","doi-asserted-by":"publisher","first-page":"1008","DOI":"10.1287\/moor.2021.1121","volume":"46","author":"A Del Pia","year":"2021","unstructured":"Del Pia, A., Khajavirad, A.: The running intersection relaxation of the multilinear polytope. Math. Oper. Res. 46(3), 1008\u20131037 (2021)","journal-title":"Math. Oper. Res."},{"key":"2122_CR20","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-023-02009-4","author":"A Del Pia","year":"2023","unstructured":"Del Pia, A., Khajavirad, A.: A polynomial-size extended formulation for the multilinear polytope of beta-acyclic hypergraphs. Math. Program. (2023). https:\/\/doi.org\/10.1007\/s10107-023-02009-4","journal-title":"Math. Program."},{"key":"2122_CR21","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1007\/s12532-019-00169-z","volume":"12","author":"A Del Pia","year":"2020","unstructured":"Del Pia, A., Khajavirad, A., Sahinidis, N.: On the impact of running-intersection inequalities for globally solving polynomial optimization problems. Math. Program. Comput. 12, 165\u2013191 (2020)","journal-title":"Math. Program. Comput."},{"key":"2122_CR22","doi-asserted-by":"crossref","unstructured":"Del\u00a0Pia, A., Walter, M.: Simple odd $$\\beta $$-cycle inequalities for binary polynomial optimization. In: Proceedings of IPCO 2022, Lecture Notes in Computer Science, vol. 13265, pp. 181\u2013194. Springer (2022)","DOI":"10.1007\/978-3-031-06901-7_14"},{"key":"2122_CR23","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-023-01992-y","author":"A Del Pia","year":"2023","unstructured":"Del Pia, A., Walter, M.: Simple odd $$\\beta $$-cycle inequalities for binary polynomial optimization. Math. Program. (2023). https:\/\/doi.org\/10.1007\/s10107-023-01992-y","journal-title":"Math. Program."},{"key":"2122_CR24","doi-asserted-by":"publisher","first-page":"617","DOI":"10.1016\/j.ipl.2012.05.005","volume":"112","author":"D Duris","year":"2012","unstructured":"Duris, D.: Some characterizations of $$\\gamma $$ and $$\\beta $$-acyclicity of hypergraphs. Inf. Process. Lett. 112, 617\u2013620 (2012)","journal-title":"Inf. Process. Lett."},{"issue":"3","key":"2122_CR25","doi-asserted-by":"publisher","first-page":"514","DOI":"10.1145\/2402.322390","volume":"30","author":"R Fagin","year":"1983","unstructured":"Fagin, R.: Degrees of acyclicity for hypergraphs and relational database schemes. J. ACM (JACM) 30(3), 514\u2013550 (1983)","journal-title":"J. ACM (JACM)"},{"issue":"4","key":"2122_CR26","doi-asserted-by":"publisher","first-page":"656","DOI":"10.1137\/S0895480192243516","volume":"7","author":"M Goemans","year":"1994","unstructured":"Goemans, M., Williamson, D.P.: New 3\/4-approximation algorithms for the maximum satisfiability problem. SIAM J. Discret. Math. 7(4), 656\u2013666 (1994)","journal-title":"SIAM J. Discret. Math."},{"key":"2122_CR27","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1007\/BF02612354","volume":"28","author":"PL Hammer","year":"1984","unstructured":"Hammer, P.L., Hansen, P., Simeone, B.: Roof duality, complementation and persistency in quadratic 0\u20131 optimization. Math. Program. 28, 121\u2013155 (1984)","journal-title":"Math. Program."},{"key":"2122_CR28","doi-asserted-by":"publisher","first-page":"6535","DOI":"10.1016\/j.disc.2009.06.035","volume":"309","author":"P J\u00e9gou","year":"2009","unstructured":"J\u00e9gou, P., Ndiaye, S.N.: On the notion of cycles in hypergraphs. Discret. Math. 309, 6535\u20136543 (2009)","journal-title":"Discret. Math."},{"issue":"1","key":"2122_CR29","doi-asserted-by":"publisher","first-page":"140","DOI":"10.1214\/088342304000000026","volume":"19","author":"MI Jordan","year":"2004","unstructured":"Jordan, M.I.: Graphical models. Stat. Sci. 19(1), 140\u2013155 (2004)","journal-title":"Stat. Sci."},{"issue":"2","key":"2122_CR30","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1016\/j.orl.2023.01.009","volume":"51","author":"A Khajavirad","year":"2023","unstructured":"Khajavirad, A.: On the strength of recursive McCormick relaxations for binary polynomial optimization. Oper. Res. Lett. 51(2), 146\u2013152 (2023)","journal-title":"Oper. Res. Lett."},{"issue":"3","key":"2122_CR31","doi-asserted-by":"publisher","first-page":"383","DOI":"10.1007\/s12532-018-0138-5","volume":"10","author":"A Khajavirad","year":"2018","unstructured":"Khajavirad, A., Sahinidis, N.V.: A hybrid LP\/NLP paradigm for global optimization relaxations. Math. Program. Comput. 10(3), 383\u2013421 (2018)","journal-title":"Math. Program. Comput."},{"key":"2122_CR32","unstructured":"Kim, J., Richard, J.P., Tawarmalani, M.: A reciprocity between tree ensemble optimization and multilinear optimization. Optim. Online, https:\/\/optimization-online.org\/2022\/03\/8828\/ (2022)"},{"key":"2122_CR33","doi-asserted-by":"crossref","unstructured":"Laurent, M.: Sums of squares, moment matrices and optimization over polynomials. In: Emerging applications of algebraic geometry, The IMA volumes in mathematics and its applications, vol. 149, pp. 157\u2013270. Springer (2009)","DOI":"10.1007\/978-0-387-09686-5_7"},{"issue":"2","key":"2122_CR34","doi-asserted-by":"publisher","first-page":"503","DOI":"10.1007\/s10898-014-0166-2","volume":"59","author":"R Misener","year":"2014","unstructured":"Misener, R., Floudas, C.A.: ANTIGONE: algorithms for continuous\/integer global optimization of nonlinear equations. J. Glob. Optim. 59(2), 503\u2013526 (2014)","journal-title":"J. Glob. Optim."},{"issue":"1\u20133","key":"2122_CR35","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1007\/BF01589101","volume":"45","author":"M Padberg","year":"1989","unstructured":"Padberg, M.: The Boolean quadric polytope: some characteristics, facets and relatives. Math. Program. 45(1\u20133), 139\u2013172 (1989)","journal-title":"Math. Program."},{"key":"2122_CR36","unstructured":"Tawarmalani, M., N. V. Sahinidis. Convexification and global optimization in continuous and mixed-integer nonlinear programming. Theory, Algorithms, Software, and Applications. vol. 65. Springer Science & Business Media (2013)"},{"issue":"3","key":"2122_CR37","doi-asserted-by":"publisher","first-page":"563","DOI":"10.1080\/10556788.2017.1335312","volume":"33","author":"S Vigerske","year":"2018","unstructured":"Vigerske, S., Gleixner, A.: SCIP: global optimization of mixed-integer nonlinear programs in a branch-and-cut framework. Optim. Methods Softw 33(3), 563\u2013593 (2018)","journal-title":"Optim. Methods Softw"},{"key":"2122_CR38","unstructured":"Wainwright, M., Jordan, M.: Treewidth-based conditions for exactness of the Sherali-Adams and Lasserre relaxations. Tech. Rep. 671, University of California (2004)"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-024-02122-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-024-02122-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-024-02122-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:03:08Z","timestamp":1750176188000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-024-02122-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,7,22]]},"references-count":38,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2025,7]]}},"alternative-id":["2122"],"URL":"https:\/\/doi.org\/10.1007\/s10107-024-02122-y","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"type":"print","value":"0025-5610"},{"type":"electronic","value":"1436-4646"}],"subject":[],"published":{"date-parts":[[2024,7,22]]},"assertion":[{"value":"15 September 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 June 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 July 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no financial or non-financial conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}