Talk Title:

Generalized Submodular Optimization—Theory, Algorithms, and Applications

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.

Location:

1174 Etcheverry Hall or Join via Zoom