On decomposability of multilinear sets

DOI10.1007/s10107-017-1158-zzbMath1446.90114OpenAlexW2611323361WikidataQ57568056 ScholiaQ57568056MaRDI QIDQ1659675

Aida Khajavirad, Alberto Del Pia

Publication date: 22 August 2018

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10107-017-1158-z

zbMATH Keywords

decompositionconvex hullpolynomial-time algorithmmultilinear functionsfactorable relaxationszero-one polynomial optimization

Mathematics Subject Classification ID

Mixed integer programming (90C11) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Nonconvex programming, global optimization (90C26) Hypergraphs (05C65)

Related Items (8)

Exact and approximate results for convex envelopes of special structured functions over simplices ⋮ (Global) optimization: historical notes and recent developments ⋮ On the impact of running intersection inequalities for globally solving polynomial optimization problems ⋮ On the strength of recursive McCormick relaxations for binary polynomial optimization ⋮ On the complexity of binary polynomial optimization over acyclic hypergraphs ⋮ The Running Intersection Relaxation of the Multilinear Polytope ⋮ Matroid optimization problems with monotone monomials in the objective ⋮ Multilinear sets with two monomials and cardinality constraints

Uses Software

• BARON
• SCIP
• GloMIQO
• ANTIGONE

Cites Work

• Unnamed Item
• Unnamed Item
• The projected faces property and polyhedral relations
• The max-cut problem on graphs not contractible to \(K_ 5\)
• Concave extensions for nonlinear 0-1 maximization problems
• Decomposition by clique separators
• The Boolean quadratic polytope: Some characteristics, facets and relatives
• The max-cut problem and quadratic 0-1 optimization; polyhedral aspects, relaxations and bounds
• A convex envelope formula for multilinear functions
• Convex envelopes of multilinear functions over a unit hypercube and over special discrete sets
• On certain polytopes associated with graphs
• Convexification and global optimization in continuous and mixed-integer nonlinear programming. Theory, algorithms, software, and applications
• Some results on the strength of relaxations of multilinear functions
• ANTIGONE: algorithms for coNTinuous/Integer global optimization of nonlinear equations
• Global optimization of nonconvex problems with multilinear intermediates
• Optimal decomposition by clique separators
• Dynamically generated cutting planes for mixed-integer quadratically constrained quadratic programs and their incorporation into GloMIQO 2
• A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
• Multiterm polyhedral relaxations for nonconvex, quadratically constrained quadratic programs
• Efficient Reduction of Polynomial Zero-One Optimization to the Quadratic Case
• Computability of global solutions to factorable nonconvex programs: Part I — Convex underestimating problems
• Compositions of Graphs and Polyhedra II: Stable Sets
• The Multilinear Polytope for Acyclic Hypergraphs
• SCIP: global optimization of mixed-integer nonlinear programs in a branch-and-cut framework
• On the cut polytope
• A Polyhedral Study of Binary Polynomial Programs

This page was built for publication: On decomposability of multilinear sets