Silvia Di Gregorio – Optimization Online

On the complexity of binary polynomial optimization over acyclic hypergraphs

Published: 2019/11/26, Updated: 2021/10/29

(Mixed) Integer Nonlinear Programming acyclic hypergraphs, binary polynomial optimization, hardness of approximation, random hypergraphs, strongly polynomial-time algorithm

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

Chvatal rank in binary polynomial optimization

Published: 2018/11/20, Updated: 2022/06/13

Alberto Del Pia

Silvia Di Gregorio

0-1 Programming, Cutting Plane Approaches, Global Optimization Theory binary polynomial optimization, chvatal rank, chvatal-gomory cuts, Integer nonlinear optimization, multilinear polytope, polyhedral relaxations

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