Optimization Online


Optimal Response to Epidemics and Cyber Attacks in Networks

Noam Goldberg (noamgold***at***mcs.anl.gov)
Sven Leyffer (leyffer***at***mcs.anl.gov)
Ilya Safro (safro***at***mcs.anl.gov)

Abstract: This paper introduces novel formulations for optimally responding to epidemics and cyber attacks in networks. In our models, at a given time period, network nodes (e.g., users or computing resources) are associated with probabilities of being infected, and each network edge is associated with some probability of propagating the infection. A decision maker would like to maximize the network's utility; keeping as many nodes open as possible, while satisfying given bounds on the probabilities of nodes being infected in the next time period. The model's relation to previous deterministic optimization models and to both probabilistic and deterministic asymptotic models is explored. Initially, we formulate a nonlinear integer program with high order multilinear terms. We then propose a quadratic approximation that provides a lower bound and feasible solution to the original problem and can be easily linearized and solved by standard integer programming solvers. We also devise a novel application and extension of cover inequalities for our formulation, to speed the solution using standard solvers.

Keywords: Nonlinear integer programming, cutting planes, network optimization, probability bounds, cybersecurity, epidemiology

Category 1: Integer Programming (0-1 Programming )

Category 2: Integer Programming (Cutting Plane Approaches )

Category 3: Network Optimization

Citation: Preprint ANL/MCS-1992-0112, Argonne National Laboratory, Mathematics and Computer Science Division, January 2012.

Download: [PDF]

Entry Submitted: 01/18/2012
Entry Accepted: 01/18/2012
Entry Last Modified: 01/18/2012

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society