A Polyhedral Study of Binary Polynomial Programs

Alberto Del Pia () and Aida Khajavirad ()
Additional contact information
Alberto Del Pia: Department of Industrial and Systems Engineering and Wisconsin Institute for Discovery, University of Wisconsin–Madison, Madison, Wisconsin 53706
Aida Khajavirad: Department of Chemical Engineering, Carnegie Mellon University, Pittsburgh, Pennsylvania 15213

Mathematics of Operations Research, 2017, vol. 42, issue 2, 389-410

Abstract: We study the polyhedral convex hull of a mixed-integer set 𝒮 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 𝒮 represents the feasible region of a linearized unconstrained binary polynomial optimization problem. We define an equivalent hypergraph representation of the mixed-integer set 𝒮 , 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.

Keywords: binary polynomial optimization; polyhedral relaxations; multilinear functions; cutting planes; lifting (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
https://doi.org/10.1287/moor.2016.0804 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:42:y:2017:i:2:p:389-410

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().