Qimeng (Kim) Yu - On constrained mixed-integer DR-submodular minimization

Qimeng (Kim) Yu - Université de Montréal

On constrained mixed-integer DR-submodular minimization

Abstract: Submodular set functions play an important role in integer programming and combinatorial optimization. Increasingly, applications call for generalized submodular functions defined over general integer or continuous domains. Diminishing returns (DR)–submodular functions are one of such generalizations, which encompass a broad class of functions that are generally nonconvex and nonconcave. We study the problem of minimizing any DR-submodular function with continuous and general integer variables under box constraints and, possibly, additional monotonicity constraints. We propose valid linear inequalities for the epigraph of any DR-submodular function under the constraints. We further provide the complete convex hull of such an epigraph, which, surprisingly, turns out to be polyhedral. We propose a polynomial-time exact separation algorithm for our proposed valid inequalities with which we first establish the polynomial-time solvability of this class of mixed-integer nonlinear optimization problems.



Bio: Qimeng (Kim) Yu is an assistant professor in the Department of Computer Science and Operations Research (DIRO) at Université de Montréal. She completed her Ph.D. in Industrial Engineering and Management Sciences at Northwestern University in 2023, and she obtained her undergraduate degree in Mathematics at Carleton College in 2018. In her research, she develops theory and algorithms for mixed-integer nonlinear programming to facilitate the solution of complex models with real-world applications.