Optimization Online


The Multilinear polytope for acyclic hypergraphs

Alberto Del Pia (delpia***at***wisc.edu)
Aida Khajavirad (aida***at***cmu.edu)

Abstract: We consider the Multilinear polytope defined as the convex hull of the set of binary points satisfying a collection of multilinear equations. Such sets are of fundamental importance in many types of mixed-integer nonlinear optimization problems, such as binary 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 binary 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 sub-expressions.

Keywords: Multilinear polytope, Cutting planes, Hypergraph acyclicity, Separation algorithm, Mixed-integer nonlinear optimization

Category 1: Integer Programming ((Mixed) Integer Nonlinear Programming )

Category 2: Integer Programming ((Mixed) Integer Linear Programming )

Category 3: Global Optimization (Theory )

Citation: manuscript

Download: [PDF]

Entry Submitted: 09/26/2016
Entry Accepted: 09/26/2016
Entry Last Modified: 12/11/2017

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