Monday, February 13, 2023
10:00am-11:00am
MC331
5 King's College Rd.
Topic: Generalized Submodular Optimization—Theory, Algorithms, and Applications
Speaker: Qimeng (Kim) Yu, Northwestern University
Abstract
Submodularity is an important concept in integer and combinatorial optimization. Submodular set functions capture diminishing returns, and for this desirable property, they are found in numerous real-world applications. A submodular set function models the effect of selecting items from a single ground set, and whether an item is chosen can be modeled using a binary variable. However, in many problem contexts, the decisions consist of choosing multiple copies of homogenous items, or heterogenous items from multiple sets. These scenarios give rise to generalizations of submodularity that require mixed-integer variables or multi-set functions. We call the associated optimization problems Generalized Submodular Optimization (GSO). GSO arises in numerous applications, including infrastructure design, healthcare, online marketing, and machine learning. Due to the mixed-integer decision space and the often highly nonlinear (even non-convex and non-concave) objective function, GSO is a broad subclass of challenging mixed-integer nonlinear programming problems. In this talk, we will consider two subclasses of GSO, namely k-submodular optimization and Diminishing Returns (DR)-submodular optimization. We will discuss the polyhedral theory for the mixed-integer set structures that arise from these problem classes, which leads to exact solution methods. Our algorithms demonstrate effectiveness and versatility in experiments with real world datasets, and they can be readily incorporated into the state-of-the-art optimization solvers.
Speaker Bio
Qimeng (Kim) Yu is a Ph.D. candidate in the Department of Industrial Engineering and Management Sciences at Northwestern University, advised by Prof. Simge Küçükyavuz. In her research, she develops theory and algorithms for mixed-integer nonlinear programming to facilitate the solution of complex models with real-world applications. Her work has appeared in Mathematical Programming, Operations Research Letters, and Discrete Optimization. She received an honorable mention in the Mixed-Integer Programming (MIP) Workshop Student Poster Competition in 2022 for her most recent work. She is a recipient of Royal E. Cabell Fellowship, Bayer Scholarship for Women in Operations Research, and Terminal Year Fellowship. Before coming to Northwestern, she received her BA in Mathematics from Carleton College.
