{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,29]],"date-time":"2026-09-29T09:30:02Z","timestamp":1790674202302,"version":"4.1.0"},"reference-count":33,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CMMI-1634768"],"award-info":[{"award-number":["CMMI-1634768"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Optim."],"published-print":{"date-parts":[[2018,1]]},"abstract":"<jats:p>We consider the multilinear polytope defined as the convex hull of the set of binary points $z$ satisfying a collection of equations of the form $z_e = \\prod_{v \\in e} {z_v}$, $e \\in E$, where $E$ denotes a family of subsets of $\\{1, \\ldots , n\\}$ of cardinality at least two. Such sets are of fundamental importance in many types of mixed-integer nonlinear optimization problems, such as $0-1$ polynomial optimization. Utilizing an equivalent hypergraph representation, we study the facial structure of the multilinear polytope in conjunction with the acyclicity degree of the underlying hypergraph. We provide explicit characterizations of the multilinear polytopes corresponding to Berge-acylic and $\\gamma$-acyclic hypergraphs. As the multilinear polytope for $\\gamma$-acyclic hypergraphs may contain exponentially many facets in general, we present a strongly polynomial-time algorithm to solve the separation problem, implying polynomial solvability of the corresponding class of $0-1$ polynomial optimization problems. As an important byproduct, we present a new class of cutting planes for constructing tighter polyhedral relaxations of mixed-integer nonlinear optimization problems with multilinear subexpressions.<\/jats:p>","DOI":"10.1137\/16m1095998","type":"journal-article","created":{"date-parts":[[2018,4,10]],"date-time":"2018-04-10T14:48:58Z","timestamp":1523371738000},"page":"1049-1076","source":"Crossref","is-referenced-by-count":42,"title":["The Multilinear Polytope for Acyclic Hypergraphs"],"prefix":"10.1137","volume":"28","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8428-3914","authenticated-orcid":true,"given":"Alberto","family":"Del Pia","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Aida","family":"Khajavirad","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2018,4,10]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.8.2.273"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579287"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1007\/s12532-014-0073-z"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1080\/10556780902883184"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1007\/BF02592023"},{"key":"atypb6","unstructured":"C. Berge,\n                      Hypergraphs: Combinatorics of Finite Sets\n                      , North-Holland Math. Libr., Elsevier, New York, 1984."},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(01)00341-9"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1145\/2983573"},{"key":"atypb9","unstructured":"C. Buchheim, Y. Crama, and E. Rodri\u0301guez-Heck,\n                      Berge-Cyclic Multilinear 0-1 Optimization Problems\n                      , manuscript, 2016."},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2005.12.033"},{"key":"atypb11","unstructured":"T. Cormen, C. Leiserson, R. Rivest, and C. Stein,\n                      Introduction to Algorithms\n                      , Vol. 6, MIT Press, Cambridge, 2001."},{"key":"atypb12","doi-asserted-by":"crossref","unstructured":"G. Cornue\u0301jols,\n                      Combinatorial Optimization: Packing and Covering\n                      , CBMS-NSF Regional Conf. Ser. in Appl. Math. 74, SIAM, Philadelphia, 2001.","DOI":"10.1137\/1.9780898717105"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1007\/BF01582138"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1016\/j.disopt.2017.02.001"},{"key":"atypb15","doi-asserted-by":"crossref","unstructured":"A. Del Pia and A. Khajavirad,\n                      On decomposability of multilinear sets\n                      , Math. Program., 2017.","DOI":"10.1007\/s10107-017-1158-z"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2016.0804"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2012.05.005"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1145\/2402.322390"},{"key":"atypb19","doi-asserted-by":"crossref","unstructured":"A. Fischer, F. Fischer, and S. McCormick,\n                      Matroid optimisation problems with nested non-linear monomials in the objective function\n                      , Math. Program., 2017.","DOI":"10.1007\/s10107-017-1140-9"},{"key":"atypb20","first-page":"17","volume":"4","author":"Fortet R.","year":"1960","journal-title":"Informatique et Recherche Ope\u0301rationnelle"},{"key":"atypb21","unstructured":"M. Garey and D. Johnson,\n                      Computers and Intractability: A Guide to the Theory of NP-Completeness\n                      , Freeman, San Francisco, 1979."},{"key":"atypb22","doi-asserted-by":"crossref","unstructured":"L. Lova\u0301sz,\n                      Combinatorial Problems and Exercises\n                      , AMS, Providence, RI, 1993.","DOI":"10.1016\/B978-0-444-81504-0.50006-0"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-012-0606-z"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-005-0580-9"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1007\/BF01589101"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1016\/0895-7177(93)90012-N"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008217604285"},{"key":"atypb28","first-page":"95","volume":"6","author":"Rosenberg I.","year":"1972","journal-title":"Informatique et Recherche Ope\u0301rationnelle"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1023\/A:1011295715398"},{"key":"atypb30","unstructured":"A. Schrijver,\n                      Theory of Linear and Integer Programming\n                      , Wiley, Chichester, 1986."},{"key":"atypb31","first-page":"245","volume":"22","author":"Sherali H.","year":"1997","journal-title":"Acta Math. Vietnam."},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1137\/0403036"},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-012-0581-4"}],"container-title":["SIAM Journal on Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/16M1095998","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:02:50Z","timestamp":1787338970000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/16M1095998"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1]]},"references-count":33,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["10.1137\/16M1095998"],"URL":"https:\/\/doi.org\/10.1137\/16m1095998","relation":{},"ISSN":["1052-6234","1095-7189"],"issn-type":[{"value":"1052-6234","type":"print"},{"value":"1095-7189","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,1]]}}}