Modeling Defender-Attacker Problems as Robust Linear Programs with Mixed-Integer Uncertainty Sets
研究了一类防御者-攻击者序贯优化问题，其中防御者的目标不确定且依赖于攻击者的操作，通过混合整数不确定集建模，提出了两种精确求解算法，实验表明算法在时间和解质量上优于标准方法，且混合整数集比凸集更不保守。
We study a class of sequential defender-attacker optimization problems where the defender’s objective is uncertain and depends on the operations of the attacker, which are represented by a mixed-integer uncertainty set. The defender seeks to hedge against the worst possible data realization, resulting in a robust optimization problem with a mixed-integer uncertainty set, which requires the solution of a challenging mixed-integer problem, which can be seen as a saddle-point problem over a nonconvex domain. We study two exact solution algorithms and present two feature applications for which the uncertainty is naturally modeled as a mixed-integer set. Our computational experiments show that the considered algorithms greatly outperform standard algorithms both in terms of computational time and solution quality. Moreover, our results show that modeling uncertainty with mixed-integer sets, instead of approximating the data using convex sets, results in less conservative solutions, which translates to a lower cost for the defender to protect from uncertainty. Summary of Contribution: We consider a class of defender-attacker problems where the defender has to make operational decisions that depend on uncertain actions from an adversarial attacker. Due to the type of information available to the defender, neither probabilistic modeling, nor robust optimization methods with convex uncertainty sets, are well suited to address the defender’s decision-making problem. Consequently, we frame the defender’s problem as a class of robust optimization problems with a mixed-integer uncertainty sets, and devise two exact algorithms that solve this class of problems. A comprehensive computational study shows that for the considered applications, our algorithms improves the performance of existing robust optimization approaches that can be adapted to solve this class of problems. Moreover, we show how mixed-integer uncertainty sets can reduce the level of over-conservatism that is a known issue of robust optimization approaches.