A Polyhedral Study of Binary Polynomial Programs

• 成果类型: Article
• 署名作者: Del Pia, Alberto; Khajavirad, Aida
• 署名单位: University of Wisconsin System; University of Wisconsin Madison; University of Wisconsin System; University of Wisconsin Madison; Carnegie Mellon University
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2016.0804
• 发表日期: 2017
• 页码: 389-410
• 关键词: convex; relaxations; ENVELOPES; polytope

摘要

We study the polyhedral convex hull of a mixed-integer set S defined by a collection of multilinear equations over the unit hypercube. Such sets appear frequently in the factorable reformulation of mixed-integer nonlinear optimization problems. In particular, the set S represents the feasible region of a linearized unconstrained binary polynomial optimization problem. We define an equivalent hypergraph representation of the mixed-integer set S, which enables us to derive several families of facet-defining inequalities, structural properties, and lifting operations for its convex hull in the space of the original variables. Our theoretical developments extend several well-known results from the Boolean quadric polytope and the cut polytope literature, paving a way for devising novel optimization algorithms for nonconvex problems containing multilinear sub-expressions.