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

Project: Research project

Project Details


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).
Effective start/end date8/1/227/31/25


  • Office of Naval Research (N00014-22-1-2602-P00002)


Explore the research topics touched on by this project. These labels are generated based on the underlying awards/grants. Together they form a unique fingerprint.