Extended flower relaxation – Optimization Online

Relaxation strength for multilinear optimization: McCormick strikes back

Published: 2023/11/14

(Mixed) Integer Linear Programming, Nonlinear Optimization, Polyhedra binary polynomial optimization, cutting planes, Extended flower relaxation, multilinear polytope, pseudo-Boolean optimization, Recursive McCormick relaxations

We consider linear relaxations for multilinear optimization problems. In a recent paper, Khajavirad proved that the extended flower relaxation is at least as strong as the relaxation of any recursive McCormick linearization (Operations Research Letters 51 (2023) 146-152). In this paper we extend the result to more general linearizations, and present a simpler proof. Moreover, … Read more

On the strength of recursive McCormick relaxations for binary polynomial optimization

Published: 2022/09/26

Aida Khajavirad

(Mixed) Integer Nonlinear Programming, Cutting Plane Approaches, Integer Programming binary polynomial optimization, cutting planes, Extended flower relaxation, multilinear polytope, Recursive McCormick relaxations

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 … Read more