Multilinear sets with two monomials and cardinality constraints

DOI10.1016/J.DAM.2022.09.010MaRDI QIDQ2097167zbMATH OpenOpenAlexFDO

Authors Rui Chen, Sanjeeb Dash, Oktay Günlük

Publication date 11 November 2022

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2105.10771

zbMATH Keywords

binary polynomial optimizationcardinality constraintpolyhedral combinatorics

Mathematics Subject Classification ID

Boolean programming (90C09) Polynomial optimization (90C23)

Abstract: Binary polynomial optimization is equivalent to the problem of minimizing a linear function over the intersection of the multilinear set with a polyhedron. Many families of valid inequalities for the multilinear set are available in the literature, though giving a polyhedral characterization of the convex hull is not tractable in general as binary polynomial optimization is NP-hard. In this paper, we study the cardinality constrained multilinear set in the special case when the number of monomials is exactly two. We give an extended formulation, with two more auxiliary variables and exponentially many inequalities, of the convex hull of solutions of the standard linearization of this problem. We also show that the separation problem can be solved efficiently.

Recommendations

• Cardinality constrained multilinear sets
• Polynomial Constraints for Sets with Cardinality Bounds
• On decomposability of multilinear sets
• scientific article; zbMATH DE number 2015558
• Convex sets associated to monomial ideals in two sets of variables
• Dual consistent systems of linear inequalities and cardinality constrained polytopes
• Dual consistent systems of linear inequalities and cardinality constrained polytopes
• On cardinality constrained polymatroids
• On cardinality constrained polymatroids
• Multivalue sets for monotonic mappings and demand mappings

Cites work

• A class of valid inequalities for multilinear 0-1 optimization problems
• A new family of facet defining inequalities for the maximum edge-weighted clique problem
• A polyhedral study of binary polynomial programs
• An improved branch-and-bound method for maximum monomial agreement
• Cardinality constrained Boolean quadratic polytope
• Cardinality constrained multilinear sets
• Combinatorial optimization with one quadratic term: spanning trees and forests
• Complete description for the spanning tree problem with one linearised quadratic term
• Computing the maximum bichromatic discrepancy, with applications to computer graphics and machine learning
• Concave extensions for nonlinear 0-1 maximization problems
• Disjunctive Programming
• Linear programming boosting via column generation
• Matroid optimisation problems with nested non-linear monomials in the objective function
• New facets and a branch-and-cut algorithm for the weighted clique problem.
• On decomposability of multilinear sets
• The Boolean quadratic polytope: Some characteristics, facets and relatives
• The multilinear polytope for acyclic hypergraphs
• The Running Intersection Relaxation of the Multilinear Polytope

Cited in

(10)

• On decomposability of multilinear sets
• Berge-acyclic multilinear 0-1 optimization problems
• Simple odd \(\beta \)-cycle inequalities for binary polynomial optimization
• Cardinality constrained multilinear sets
• The multilinear polytope for acyclic hypergraphs
• A polyhedral study of binary polynomial programs
• The polytope of binary sequences with bounded variation
• Simple odd -cycle inequalities for binary polynomial optimization
• Convexifying multilinear sets with cardinality constraints: structural properties, nested case and extensions
• Submodular maximization and its generalization through an intersection cut lens

This page was built for publication: Multilinear sets with two monomials and cardinality constraints

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2097167)