Aida Khajavirad, an associate professor of industrial and systems engineering, is advancing the theoretical foundations of a notoriously difficult class of optimization problems through a new project supported by the Office of Naval Research (ONR). Working in collaboration with Alberto Del Pia of the University of Wisconsin–Madison, Khajavirad is rethinking how researchers approach binary polynomial optimization (BPO). This broad family of problems (which are so complex that solving them exactly becomes impractical at scale) underpins applications ranging from machine learning and cybersecurity to mission planning and logistics.
While binary quadratic optimization has been studied extensively, far less is known about higher-degree BPOs. Through a novel hypergraph representation scheme, Khajavirad and Del Pia aim to advance the state-of-the-art by obtaining sufficient conditions in terms of the structure of the hypergraph under which BPO problems are solvable in polynomial time. Their work builds on their decade-long collaboration relating the complexity of these optimization problems to the acyclicity degree of the corresponding hypergraph.
The new project will go beyond hypergraph acyclicity, and identify polynomial-time solvable classes of BPO whose hypergraphs contain cycles. A major limitation in almost all previous theoretical results is that they assume all binary points are feasible points. In this project, the PIs remove this restrictive assumption by allowing for inequality constraints defined by multivariate polynomial functions.
Khajavirad’s research centers on the theoretical, algorithmic, and computational aspects of optimization, with applications in data science and engineering. Her work has been recognized with honors from the INFORMS Optimization and Computing Societies and has been supported by multiple federal agencies. The ONR project reflects both the depth of her scholarship and the collaborative nature of today’s advances in optimization theory.
“Despite the extensive applications of binary polynomial optimization across science and engineering, many fundamental questions remain open,” she says. “This project allows us to significantly advance the theory and algorithms behind these problems and broaden their real-world impact.
