Optimization Online


The Multilinear polytope for gamma-acyclic hypergraphs

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

Abstract: In this paper, 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 highly efficient polynomial algorithm to solve the separation problem. Our results imply polynomial solvability of the corresponding classes of binary polynomial optimization problems and provide new types of cutting planes for a variety of mixed-integer nonlinear optimization problems.

Keywords: Multilinear polytope, Hypergraph acyclicity, Separation algorithm, Cutting planes, 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: 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