Generalized Submodular Optimization: Theory, Algorithms, and Computation (21-000000918)
Abstract
Many modern systems consist of networks of interconnected components that exchange relevant data to sense environmental conditions a,nd continuously improve and optimize operations. Consider a multi-type sensor network-enabled by the internet-of-things (IoT) techno,logy-that measures the temperature, light, and humidity conditions of a smart building and makes necessary adjustments in real time,to achieve energy efficiency. The design of such a network requires optimal placement of various types of sensors to gather salient,information about the building condition. The quality of the deployment plan is measured by a (nonlinear) set function. A common pro,perty of such set functions-known as submodularity-is that they exhibit diminishing returns or economies of scale. Intuitively, the,more sensors we place, the less additional information we obtain. Submodularity has proved to be a powerful concept in integer progr,amming and combinatorial optimization. This concept has given rise to rich theoretical results and efficient solution methods for a,broad array of problems, including set covers, graph cuts, and matroids. The classical submodular set function models the effects of, selecting certain items from a single ground set. Thus, this class of combinatorial optimization problems can be modeled using bina,ry variables to indicate whether an item is chosen. However, increasingly, many problem contexts require ,low multiple copies of each item to be selected from different types of ground sets. This calls for generalizations of submodularity, that require general integer and continuous variables or multi-set functions. We refer to such optimization problems as generalized, submodular optimization. The multi-type sensor placement problem is one such example. Researchers have predominantly applied approx,imation approaches to certain generalized submodular optimization problems under limited constraint structures (e.g., cardinality).,Approximation algorithms are appealing in applications where an approximate solution suffices, and computing resources such as time,and memory are limited. In our project, however, we propose to apply a polyhedral approach for capital-intensive problems for which,exact optimal solutions are desired and complicated constraints (e.g., budget, cardinality, sensor interference) may need to be cons,idered. Our proposed approach leads to versatile algorithms that can be readily incorporated into state-of-the-art optimization solv,ers, which have witnessed tremendous success in solving large-scale mixed-integer programs in practice. Generalized submodular optim,ization 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 arbi,trary linearly representable 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 tha,t 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. Final,ly, we will conduct extensive computational experiments on test instances constructed based on practical problems and real-world dat,a from multiple domains (e.g., intelligent infrastructure and national security).
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Aug 05, 2022
- Source ID
- N000142212602
Entities
People
- Si̇mge Küçükyavuz
Organizations
- Northwestern University
- Office of Naval Research
- United States Navy