The Multilinear Polytope for Acyclic Hypergraphs

DOI10.1137/16M1095998zbMath1396.90048OpenAlexW2797698037WikidataQ57568042 ScholiaQ57568042MaRDI QIDQ4637506

Aida Khajavirad, Alberto Del Pia

Publication date: 24 April 2018

Published in: SIAM Journal on Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/16m1095998

zbMATH Keywords

cutting planesmixed-integer nonlinear optimizationseparation algorithmhypergraph acyclicitymultilinear polytope

Mathematics Subject Classification ID

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

Related Items (16)

Graph, clique and facet of Boolean logical polytope ⋮ On decomposability of multilinear sets ⋮ Simple odd \(\beta \)-cycle inequalities for binary polynomial optimization ⋮ Tractable Relaxations of Composite Functions ⋮ On the impact of running intersection inequalities for globally solving polynomial optimization problems ⋮ Complexity of optimizing over the integers ⋮ On the strength of recursive McCormick relaxations for binary polynomial optimization ⋮ Efficient linear reformulations for binary polynomial optimization problems ⋮ On the complexity of binary polynomial optimization over acyclic hypergraphs ⋮ A polyhedral study of lifted multicuts ⋮ A new framework to relax composite functions in nonlinear programs ⋮ Berge-acyclic multilinear 0-1 optimization problems ⋮ A note on solving DiDi's driver-order matching problem ⋮ 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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Some characterizations of \(\gamma \) and \(\beta \)-acyclicity of hypergraphs
• Hypergraphs with no special cycles
• Concave extensions for nonlinear 0-1 maximization problems
• Pseudo-Boolean optimization
• The Boolean quadratic polytope: Some characteristics, facets and relatives
• Boolean polynomials and set functions
• A convex envelope formula for multilinear functions
• Convex envelopes of multilinear functions over a unit hypercube and over special discrete sets
• Matroid optimisation problems with nested non-linear monomials in the objective function
• A class of valid inequalities for multilinear 0-1 optimization problems
• Convex envelopes for edge-concave functions
• Some results on the strength of relaxations of multilinear functions
• Explicit convex and concave envelopes through polyhedral subdivisions
• Berge-acyclic multilinear 0-1 optimization problems
• Global optimization of nonconvex problems with multilinear intermediates
• Balanced matrices
• Combinatorial Optimization
• Degrees of acyclicity for hypergraphs and relational database schemes
• 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
• Jointly Constrained Biconvex Programming
• On the cut polytope
• A Polyhedral Study of Binary Polynomial Programs
• Analysis of bounds for multilinear functions

This page was built for publication: The Multilinear Polytope for Acyclic Hypergraphs