Optimization Online


On Decomposability of Multilinear Sets

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

Abstract: In this paper, we consider the Multilinear set defined as the set of binary points satisfying a collection of multilinear equations. Such sets appear in factorable reformulations of many types of nonconvex optimization problems, including binary polynomial optimization. A great simplification in studying the facial structure of the convex hull of the Multilinear set is possible when this set is decomposable into simpler sets. In this paper, we study the decomposability properties of Multilinear sets. Utilizing an equivalent hypergraph representation, we derive necessary and sufficient conditions under which the Multilinear set is decomposable into simpler sets, based on the structure of pair-wise intersection hypergraphs. Our characterizations unify and extend the existing decomposability results for the Boolean quadric polytope. Finally, we propose a polynomial-time algorithm to optimally decompose a Multilinear set into simpler subsets. Our proposed algorithm can be easily incorporated in branch-and-cut based global solvers as a preprocessing step for cut generation.

Keywords: Multilinear functions; Convex hull; Decomposition; Zero-one polynomial optimization; Factorable relaxations; Polynomial-time algorithm

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

Category 2: Global Optimization (Theory )

Category 3: Combinatorial Optimization (Polyhedra )

Citation: Submitted manuscript

Download: [PDF]

Entry Submitted: 05/28/2016
Entry Accepted: 05/28/2016
Entry Last Modified: 05/08/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