Binary polynomial optimization through a hypergraph theoretic lens

Presenter:  Prof. Aida Khajavirad
Lehigh University

April 4th, 2025 | 11.00 am
Politecnico di Milano, 3. 1. 10 Room (Bld. 3)
Piazza Leonardo da Vinci, 32

Contact:  Prof.  Pietro Belotti

Sommario

On April 4th, 2025 at 11.00 am the seminar titled "Binary polynomial optimization through a hypergraph theoretic lens"  will take place at Politecnico di Milano, 3. 1. 10 Room (Building 3 - Gino Cassinis).

We define the multilinear polytope as the convex hull of a set of binary points satisfying a collection of multilinear equations. This set corresponds to the convex hull of the feasible region of a linearized binary polynomial optimization problem. By introducing a hypergraph representation framework, we relate the complexity of the facial structure of the multilinear polytope to the acyclicity degree of the corresponding hypergraph. We then demonstrate how different degrees of acyclicity can be used to obtain compact formulations for the multilinear polytope in the original or in an extended space. This in turn enables us to identify several classes of polynomial-time solvable binary polynomial optimization problems. We conclude by discussing several extensions as well as open questions.

Biografia

Aida Khajavirad is an Assistant Professor of Industrial and Systems Engineering at Lehigh University. Before joining Lehigh, she worked at Rutgers University, University of Texas at Austin and IBM TJ Watson Research Center. She received her PhD from Carnegie Mellon University in 2012. Aida’s research goal is to advance the state-of-the-art in Mixed-Integer Nonlinear Optimization (MINLP) at theoretical, algorithmic, and software levels. Recently, she has become interested in developing optimization algorithms with performance guarantees for data science applications. Her work has been recognized by the 2017 Young Researchers Prize by INFORMS Optimization Society and 2023 INFORMS Computing Society (ICS) prize by INFORMS Computing Society. Aida’s research has been funded by NSF, DOE, and AFOSR.