4 papers
The complete edge relaxation for binary polynomial optimization
Alberto Del Pia, Aida Khajavirad
We consider the multilinear polytope, defined as the convex hull of the feasible region of a lifted binary polynomial optimization problem. We define a relaxation in an extended sp…
Extended formulations for the multilinear polytope of acyclic hypergraphs
Alberto Del Pia, Aida Khajavirad
This article provides an overview of our joint work on binary polynomial optimization over the past decade. We define the multilinear polytope as the convex hull of the feasible re…
Beyond hypergraph acyclicity: limits of tractability for pseudo-Boolean optimization
Alberto Del Pia, Aida Khajavirad
In this paper, we study the problem of minimizing a polynomial function with literals over all binary points, often referred to as pseudo-Boolean optimization. We investigate the f…
The pseudo-Boolean polytope and polynomial-size extended formulations for binary polynomial optimization
Alberto Del Pia, Aida Khajavirad
With the goal of obtaining strong relaxations for binary polynomial optimization problems, we introduce the pseudo-Boolean polytope defined as the convex hull of the set of binary…