Optimization Online


A polyhedral study of binary polynomial programs

Alberto Del Pia (delpia***at***wisc.edu)
Aida Khajavirad (aidak***at***utexas.edu)

Abstract: We study the polyhedral convex hull of a mixed-integer set S defined by a collection of multilinear equations over the 0-1-cube. 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.

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
Entry Accepted: 02/16/2015
Entry Last Modified: 11/28/2016

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society