论文标题
关于递归麦考密克的强度，用于二进制多项式优化
On the strength of recursive McCormick relaxations for binary polynomial optimization
论文作者
论文摘要
递归麦考密克弛豫一直是二进制多项式优化问题的最流行的凸化技术之一。人们理解的是，这些放松的质量和大小都取决于递归序列，并找到最佳的递归顺序，等同于解决困难的组合优化问题。在本文中，我们证明了任何递归的麦考密克放松都暗示了延长的花朵放松，这是一种线性编程放松，这是Del Pia和Khajavirad 2018引入的花朵放松的自然概括，对于二进制多项式优化问题，可以在固定的时间内解决固定程度的二元优化问题。
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.
