Mixed-Integer Programming for a Class of Robust Submodular Maximization Problems

We consider robust submodular maximization problems (RSMs), where given a set of m monotone submodular objective functions, the robustness is with respect to the worst-case (scaled) objective function. The model we consider generalizes two variants of robust submodular maximization problems in the literature, depending on the choice of the scaling vector. On the one hand, by using unit scaling, we obtain a usual robust submodular maximization problem. On the other hand, by letting the scaling vector be the optimal objective function of each individual (NP-hard) submodular maximization problem, we obtain a second variant. Although the robust version of the objective is no longer submodular, we reformulate the problem by exploiting the submodularity of each function. We conduct a polyhedral study of the resulting formulation and provide conditions under which the submodular inequalities are facet-defining for a key mixed-integer set. We investigate several strategies for incorporating these inequalities within a delayed cut generation framework to solve the problem exactly. For the second variant, we present an algorithm that yields a feasible solution along with its optimality gap. We apply the proposed methods to a sensor placement optimization problem in water distribution networks, using real-world data sets to demonstrate their effectiveness.

Funding: H. H Wu was supported by National Science and Technology Council (Taiwan) [Grants 111-2221-E-A49-079 and 112-2221-E-A49-126-MY2]. S. Kucukyavuz was supported by Office of Naval Research [Grant N00014-22-1-2602].