Lehigh Industrial and Systems Engineering (ISE) is pleased to announce that Associate Professor Aida Khajavirad has been awarded a research grant from the Department of Defense, Office of Naval Research, under the Mathematical and Resource Optimization program. The three-year project titled Binary polynomial optimization through a hypergraph theoretic lens: theory and algorithms will run from October 2025 through September 2028. The total award is $700,000, with $350,000 allocated to Lehigh University. This is a two-PI collaborative grant submitted in parallel through the two participating universities; the partner PI is Professor Alberto Del Pia of the University of Wisconsin–Madison.
The project tackles the fundamental problem of binary polynomial optimization (BPO), an NP-hard problem with extensive applications in computer science, engineering, and operations research. While quadratic cases are well studied, higher-degree BPO problems remain poorly understood. This research seeks to identify structural conditions, both necessary and sufficient, under which BPO problems can be solved in polynomial time. Building on PI’s prior results linking BPO complexity to hypergraph acyclicity, the project will develop new theory that extends beyond acyclic structures to signed hypergraphs that include cycles, characterizing solvable classes through cycle length and type. Additionally, the investigators will study constrained BPO problems by introducing new notions of decomposability and separability, enabling the derivation of polynomial-size linear programming formulations. These theoretical advances will yield strong LP relaxations for general mixed-integer polynomial and nonlinear optimization problems, with applications in binary matrix/tensor factorization, higher-order graphical models, maximum satisfiability, and DoD-relevant domains such as mission planning, command and control, logistics, and cybersecurity.
Professor Aida Khajavirad is an Associate Professor of ISE at Lehigh University whose research advances the theoretical, algorithmic, and computational foundations of Mixed-Integer Nonlinear Optimization (MINLP). In addition, she develops optimization algorithms with performance guarantees for data science and machine learning applications, drawing on tools from convex analysis, integer and combinatorial optimization, and high-dimensional probability. Her contributions have been recognized with major honors such as the INFORMS Optimization Society Young Researchers Prize and the INFORMS Computing Society Prize, and her research has been supported by agencies including the NSF, DOE, AFOSR, and ONR. She also serves as an Associate Editor for Mathematics of Operations Research, Mathematical Programming Computation, and the Journal of Global Optimization.
Aida says “Despite the extensive applications of binary polynomial optimization across science and engineering, many fundamental questions in this area remain open. Over the past twelve years, we have developed a solid foundational framework for analyzing and solving this class of problems. This grant will allow us to significantly advance the state-of-the-art on theory and algorithms for binary polynomial optimization and to broaden its impact by addressing optimization problems of practical importance.”
