On the strength of recursive McCormick relaxations for binary polynomial optimization
From MaRDI portal
Publication:6161903
Abstract: Recursive McCormick relaxations have been among the most popular convexification techniques for binary polynomial optimization problems. It is well-understood that both the quality and the size of these relaxations depend on the recursive sequence, and finding an optimal recursive sequence amounts to solving a difficult combinatorial optimization problem. In this paper, we prove that any recursive McCormick relaxation is implied by the extended flower relaxation, a linear programming relaxation that is a natural generalization of the flower relaxation introduced by Del Pia and Khajavirad 2018, which for binary polynomial optimization problems with fixed degree can be solved in strongly polynomial time.
Recommendations
- A matrix nonconvex relaxation approach to unconstrained binary polynomial programs
- McCormick-Based Relaxations of Algorithms
- Tight sum-of-squares lower bounds for binary polynomial optimization problems
- Tight relaxations for polynomial optimization and Lagrange multiplier expressions
- Efficient linear reformulations for binary polynomial optimization problems
- A hierarchy of spectral relaxations for polynomial optimization
- Exact Semidefinite Programming Relaxations with Truncated Moment Matrix for Binary Polynomial Optimization Problems
- Sum-of-squares hierarchies for binary polynomial optimization
- Sum-of-squares hierarchies for binary polynomial optimization
Cites work
- A class of valid inequalities for multilinear 0-1 optimization problems
- A global optimization algorithm for polynomial programming problems using a reformulation-linearization technique
- A hybrid LP/NLP paradigm for global optimization relaxations
- A polyhedral study of binary polynomial programs
- Analysis of bounds for multilinear functions
- Cardinality constrained multilinear sets
- Computability of global solutions to factorable nonconvex programs: Part I — Convex underestimating problems
- Concave extensions for nonlinear 0-1 maximization problems
- Convex envelopes of multilinear functions over a unit hypercube and over special discrete sets
- Degrees of acyclicity for hypergraphs and relational database schemes
- Explicit convex and concave envelopes through polyhedral subdivisions
- Global optimization of mixed-integer nonlinear programs: a theoretical and computational study
- Global optimization of nonconvex problems with multilinear intermediates
- Jointly Constrained Biconvex Programming
- On decomposability of multilinear sets
- On the impact of running intersection inequalities for globally solving polynomial optimization problems
- Pseudo-Boolean optimization
- Semidefinite programming relaxations for semialgebraic problems
- Some results on the strength of relaxations of multilinear functions
- Technical Note—Converting the 0-1 Polynomial Programming Problem to a 0-1 Linear Program
- The multilinear polytope for acyclic hypergraphs
- The Running Intersection Relaxation of the Multilinear Polytope
Cited in
(6)- McCormick-Based Relaxations of Algorithms
- Bounding the gap between the McCormick relaxation and the convex hull for bilinear functions
- Solving unconstrained binary polynomial programs with limited reach: application to low autocorrelation binary sequences
- A polynomial-size extended formulation for the multilinear polytope of beta-acyclic hypergraphs
- Quadratization and convexification in polynomial binary optimization
- The pseudo-Boolean polytope and polynomial-size extended formulations for binary polynomial optimization
This page was built for publication: On the strength of recursive McCormick relaxations for binary polynomial optimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6161903)
