In binary polynomial optimization, the goal is to find a binary point maximizing a given polynomial function. In this paper, we propose a novel way of formulating this general optimization problem, which we call factorized binary polynomial optimization. In this formulation, we assume that the variables are partitioned into a fixed number of sets, and … Read more
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
Article Download View A polynomial-size extended formulation for the multilinear polytope of beta-acyclic hypergraphs
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
We consider the multilinear polytope which arises naturally in binary polynomial optimization. Del Pia and Di Gregorio introduced the class of odd beta-cycle inequalities valid for this polytope, showed that these generally have Chvátal rank 2 with respect to the standard relaxation and that, together with flower inequalities, they yield a perfect formulation for cycle … Read more
Binary polynomial optimization is equivalent to the problem of minimizing a linear function over the intersection of the multilinear set with a polyhedron. Many families of valid inequalities for the multilinear set are available in the literature, though giving a polyhedral characterization of the convex hull is not tractable in general as binary polynomial optimization … Read more
In this work we advance the understanding of the fundamental limits of computation for Binary Polynomial Optimization (BPO), which is the problem of maximizing a given polynomial function over all binary points. In our main result we provide a novel class of BPO that can be solved efficiently both from a theoretical and computational perspective. … Read more
Recently, several classes of cutting planes have been introduced for binary polynomial optimization. In this paper, we present the first results connecting the combinatorial structure of these inequalities with their Chvatal rank. We show that almost all known cutting planes have Chvatal rank 1. All these inequalities have an associated hypergraph that is beta-acyclic, thus, … Read more