The multilinear polytope of beta-acyclic hypergraphs has polynomial extension complexity
Article Download View The multilinear polytope of beta-acyclic hypergraphs has polynomial extension complexity
multilinear polytope
On the strength of recursive McCormick relaxations for binary polynomial optimization
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
Rank-one Boolean tensor factorization and the multilinear polytope
We consider the NP-hard problem of approximating a tensor with binary entries by a rank-one tensor, referred to as rank-one Boolean tensor factorization problem. We formulate this problem, in an extended space of variables, as the problem of minimizing a linear function over a highly structured multilinear set. Leveraging on our prior results regarding the … Read more
Chvatal rank in binary polynomial optimization
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
On decomposability of the multilinear polytope and its implications in mixed-integer nonlinear optimization
In this article, we provide an overview of some of our recent results on the facial structure of the multilinear polytope with a special focus on its decomposability properties. Namely, we demonstrate that, in the context of mixed-integer nonlinear optimization, the decomposability of the multilinear polytope plays a key role from both theoretical and algorithmic … Read more
The Multilinear polytope for acyclic hypergraphs
We consider the Multilinear polytope defined as the convex hull of the set of binary points satisfying a collection of multilinear equations. Such sets are of fundamental importance in many types of mixed-integer nonlinear optimization problems, such as binary polynomial optimization. Utilizing an equivalent hypergraph representation, we study the facial structure of the Multilinear polytope … Read more