Generalized Submodular Optimization—Theory, Algorithms, and Applications

Par

Kim Yu

Northwestern University

Résumé:

Submodularity is an important concept in integer and combinatorial optimization. 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 certain items from various 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 Diminishing Returns (DR)-submodular optimization and k-submodular optimization. We will discuss the polyhedral theory for the mixed-integer set structures that arise from these problem classes, which leads to efficient and versatile exact solution methods.Submodularity is an important concept in integer and combinatorial optimization. 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 certain items from various 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 Diminishing Returns (DR)-submodular optimization and k-submodular optimization. We will discuss the polyhedral theory for the mixed-integer set structures that arise from these problem classes, which leads to efficient and versatile exact solution methods.

Biographie :

Qimeng (Kim) Yu is a Ph.D. candidate at Northwestern University in the Department of Industrial Engineering and Management Sciences, 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. Before coming to Northwestern, she received her BA in Mathematics from Carleton College. Qimeng (Kim) Yu is a Ph.D. candidate at Northwestern University in the Department of Industrial Engineering and Management Sciences, 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. Before coming to Northwestern, she received her BA in Mathematics from Carleton College.