  


A polyhedral study of binary polynomial programs
Alberto Del Pia (delpiawisc.edu) Abstract: We study the polyhedral convex hull of a mixedinteger set S defined by a collection of multilinear equations over the 01cube. Such sets appear frequently in the factorable reformulation of mixedinteger 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 mixedinteger set S, which enables us to derive several families of facetdefining inequalities, structural properties, and lifting operations for its convex hull in the space of the original variables. Our theoretical developments extend several wellknown results from the Boolean quadric polytope and the cut polytope literature, paving a way for devising novel optimization algorithms for nonconvex problems containing multilinear subexpressions. Keywords: binary polynomial optimization; polyhedral relaxations; multilinear functions; cutting planes; lifting Category 1: Integer Programming ((Mixed) Integer Nonlinear Programming ) Category 2: Global Optimization Category 3: Integer Programming (Cutting Plane Approaches ) Citation: To appear in Mathematics of Operations Research, May 2016 Download: [PDF] Entry Submitted: 02/16/2015 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  