# On the strength of recursive McCormick relaxations for binary polynomial optimization

arXiv: https://arxiv.org/abs/2209.13034 · HTML: https://mlsanity.com/paper/2209.13034/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Sep 2022.

## Built on by (most cited first, 1 of 1)

- [Disjunctive Branch-and-Bound for Certifiably Optimal Low-Rank Matrix Completion](https://mlsanity.com/paper/2305.12292/) (2023)

## Abstract (arXiv)

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.