  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 heterogenous 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 tutorial, 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.
