Generalized Submodular Optimization: Theory, Algorithms, and Computation (21-000000918)

Generalized submodular optimization is a nascent area of research with enormous potential for rich theory and broad practical impact. In this proposed project, we aim to establish foundational polyhedral theory of the set structures arising from generalized submodular optimization under arbitrary linearly representable restrictions, such as budget constraints. We will leverage these novel theoretical results to devise scalable exact solution methods. We will characterize and exploit the properties of generalized submodular functions to construct classes of valid inequalities to strengthen the continuous relaxation of the resulting optimization problems. We will conduct rigorous analysis on the strength of the proposed inequalities and develop efficient separation schemes to improve the computational performance of our algorithms. Finally, we will conduct extensive computational experiments on test instances constructed based on practical problems and real-world data from multiple domains (e.g., intelligent infrastructure and national security).