Modeling Defender-Attacker Problems as Robust Linear Programs with Mixed-Integer Uncertainty Sets

Juan S. Borrero () and Leonardo Lozano ()
Additional contact information
Juan S. Borrero: School of Industrial Engineering and Management, Oklahoma State University, Stillwater, Oklahoma 74078
Leonardo Lozano: Operations, Business Analytics and Information Systems, University of Cincinnati, Cincinnati, Ohio 45221

INFORMS Journal on Computing, 2021, vol. 33, issue 4, 1570-1589

Abstract: 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.

Keywords: defender attacker; robust optimization; bilevel optimization; mixed-integer optimization; cut generation; Frank-Wolfe algorithm (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2020.1041 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:33:y:2021:i:4:p:1570-1589

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().