Multilinear sets with two monomials and cardinality constraints

DOI10.1016/j.dam.2022.09.010zbMath1506.90200arXiv2105.10771OpenAlexW4303613552MaRDI QIDQ2097167

Sanjeeb Dash, Rui Chen, 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

polyhedral combinatoricscardinality constraintbinary polynomial optimization

Mathematics Subject Classification ID

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

Cites Work

• Combinatorial optimization with one quadratic term: spanning trees and forests
• Concave extensions for nonlinear 0-1 maximization problems
• The Boolean quadratic polytope: Some characteristics, facets and relatives
• Cardinality constrained Boolean quadratic polytope
• New facets and a branch-and-cut algorithm for the weighted clique problem.
• Matroid optimisation problems with nested non-linear monomials in the objective function
• On decomposability of multilinear sets
• A class of valid inequalities for multilinear 0-1 optimization problems
• Computing the maximum bichromatic discrepancy, with applications to computer graphics and machine learning
• Cardinality constrained multilinear sets
• A new family of facet defining inequalities for the maximum edge-weighted clique problem
• Complete description for the spanning tree problem with one linearised quadratic term
• An Improved Branch-and-Bound Method for Maximum Monomial Agreement
• Disjunctive Programming
• The Multilinear Polytope for Acyclic Hypergraphs
• The Running Intersection Relaxation of the Multilinear Polytope
• A Polyhedral Study of Binary Polynomial Programs
• Linear programming boosting via column generation