  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 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. While 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 provide an algorithm to
obtain 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 datasets to demonstrate the effectiveness of the
methods.
