Modeling Worst-case Defender-attacker Problems as Robust Linear Programs with Mixed-integer Uncertainty Sets
Abstract
Many problems in Defender~Attacker settings require the Defender to solve optimization problems where there is uncertainty about the operations of the Attacker. Most of the models in the mathematical optimization literature can quantify such uncertainty via probability distributions, which require that the Defender has enough information, sourced on historical data, expert opinions, or well understood physical processes, to measure the likelihood of uncertain events. In Defender~Attacker settings, however, the Defender might not be able to characterize the uncertainty probabilistically, due to the lack of reliable data about the operations of the attackers. Robust Optimization (RO) provides an alternative way to model uncertainty when using probability distributions is not possible. Here, the Defender only needs to characterize an uncertainty set for theunknown data, and the optimization is carried out only over those solutions that are feasible for all data realizations within this set. Traditional RO models, however, assume uncertainty sets with simple structures which result in a limited modeling power. Particularly, they cannot address settings where theDefender has scarce, but detailed information about the potential actions of the Attacker, or where the realization of the Attacker s plan depends upon intricate relationships between uncertain events.Therefore, there is a need to develop optimization models that are capable of hedging against uncertainty from complex adversarial operations for which very limited information is known. The lack of such models can lead to the Defender devising unnecessarily costly plans that might expose him/her to potentially catastrophic mitigable risks. In our proposed research, we seek to address this need by considering RO with uncertainty sets that can be represented with mixed~integer variables and linear constraints. Such a class of sets allows the Defender to optimize and hedge over a significantly broader class of uncertain events. However, this comes at the expense of computational tractability.We plan to develop the RO models described above by (i) establishing fundamental theoretical results that can lead to the design of novel solution algorithms; and (ii) by analyzing and implementing the methods that such algorithms require. In order to do so, we plan to build upon theories and algorithmic ideas from bilevel, continuous, and discrete optimization, including decomposition algorithms, cuttingplane methods, convex optimization algorithms, and decision diagrams. Although we do not expect to design fast (i.e., polynomial~time) algorithms due to the computational complexity of the problem, the desired methods should be able to solve reasonably sized instances of RO problems with mixed~integer uncertainty sets in a reasonable amount of time, by using state~of~theart optimization solvers. We also expect to develop formal approximation techniques for the resulting optimization problems that yield near~optimal solutions in polynomial time, and we plan to characterizethe tradeoff between computational tractability and the quality of information.The resulting methods will positively impact the Navy~s capabilities by providing decision support tools for strategic and tactical operational planning in adversarial environments under uncertainty. Examples of such settings include military deployments in adversarial territories, the defense of critical militaryinfrastructure, and post~disaster response logistics.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- May 23, 2019
- Source ID
- N000141912329
Entities
People
- Juan Borrero
Organizations
- Office of Naval Research
- Oklahoma State University–Stillwater
- United States Navy