标题： 具有混合整数规划的稳健子模最大化问题的一类 显示英文标题

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

摘要： 我们考虑鲁棒子模最大化问题（RSMs），其中给定一组$m$单调子模目标函数，鲁棒性是针对最差情况（缩放）目标函数的。 我们考虑的模型推广了文献中两种鲁棒子模最大化问题的变体，具体取决于缩放向量的选择。 一方面，通过使用单位缩放，我们得到一个通常的鲁棒子模最大化问题。 另一方面，通过让缩放向量成为每个单独（NP难）子模最大化问题的最优目标函数，我们得到第二种变体。 虽然目标的鲁棒版本不再是子模的，但我们通过利用每个函数的子模性对问题进行重新表述。 我们对所得的表述进行了多面体研究，并提供了子模不等式对于关键混合整数集是面定义的条件。 我们研究了几种策略，将这些不等式纳入延迟割平面生成框架中以精确求解该问题。 对于第二种变体，我们提供了一个算法来获得可行解及其最优性差距。 我们使用真实世界的数据集将所提出的方法应用于水分配网络中的传感器布置优化问题，以证明这些方法的有效性。 显示英文摘要

摘要： 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.