Premium
Detecting resilient structures in stochastic networks: A two‐stage stochastic optimization approach
Author(s) -
Rysz Maciej,
Krokhmal Pavlo A.,
Pasiliao Eduardo L.
Publication year - 2017
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.21727
Subject(s) - mathematical optimization , stochastic programming , stochastic optimization , induced subgraph isomorphism problem , transformation (genetics) , mathematics , set (abstract data type) , computer science , clique , graph , constraint (computer aided design) , theoretical computer science , combinatorics , line graph , biochemistry , chemistry , geometry , voltage graph , gene , programming language
We propose a two‐stage stochastic programming framework for designing or identifying “resilient,” or “reparable” structures in graphs whose topology may undergo a stochastic transformation. The reparability of a subgraph satisfying a given property is defined in terms of a budget constraint, which allows for a prescribed number of vertices to be added to or removed from the subgraph so as to restore its structural properties after the observation of random changes to the graph's set of edges. A two‐stage stochastic programming model is formulated and is shown to be N P ‐complete for a broad range of graph‐theoretical properties that the resilient subgraph is required to satisfy. A general combinatorial branch‐and‐bound algorithm is developed, and its computational performance is illustrated on the example of a two‐stage stochastic maximum clique problem. © 2017 Wiley Periodicals, Inc. NETWORKS, Vol. 69(2), 189–204 2017