Title: Mixed-Integer Programming Approaches to Generalized Submodular Optimization and its Applications

Abstract: Submodularity is an important concept in integer and combinatorial optimization. A classical submodular set function models the utility of selecting homogenous items from a single ground set, and such selections can be represented by binary variables. In practice, many problem contexts involve choosing heterogeneous items from more than one ground set or selecting multiple copies of homogenous items, which call for extensions of submodularity. We refer to the optimization problems associated with such generalized notions of submodularity as Generalized Submodular Optimization (GSO). GSO is found in wide-ranging applications, including infrastructure design, healthcare, online marketing, and machine learning. Due to the often highly nonlinear (even non-convex and non-concave) objective function and the mixed-integer decision space, GSO is a broad subclass of challenging mixed-integer nonlinear programming problems. In this talk, we first provide an overview of classical submodularity. Then we introduce two subclasses of GSO, for which we present polyhedral theory for the mixed-integer set structures that arise from these problem classes. Our theoretical results lead to efficient and versatile exact solution methods that demonstrate their effectiveness in practical problems using real-world datasets. This is joint work with Qimeng (Kim) Yu.

Bio: Simge Küçükyavuz is Chair and David A. and Karen Richards Sachs Professor in the Industrial Engineering and Management Sciences Department at Northwestern University. She is an expert in mixed-integer, large-scale, and stochastic optimization. Her methodologies have applications in complex computational problems across numerous domains, including social networks, computing and energy infrastructure, statistical learning, and logistics. Her research has been supported by multiple grants from the National Science Foundation (NSF) and the Office of Naval Research. She is the recipient of the NSF CAREER Award and the INFORMS Computing Society (ICS) Prize. She is the past chair of ICS and serves on the editorial boards of Mathematics of Operations Research, Mathematical Programming, SIAM Journal on Optimization, and MOS-SIAM Optimization Book Series. She received her Ph.D. in Industrial Engineering and Operations Research from the University of California, Berkeley.