Two-stage Models and Algorithms for Optimizing Infrastructure Design and Recovery Operations under Stochastic Disruptions
Abstract: This paper models an infrastructure as a network with sets of supply, transshipment, and demand nodes. A subset of potential arcs can be constructed between node pairs for conveying service flow. We assume stochastic occurrences of arc failure under non-deliberate disruptive events, and study two model variants. Model 1 considers small-scale failures, and repairs arcs for a quick (or temporary) service restoration. Model 2 analyzes multiple interdependent infrastructures under large-scale disruptions and cascading failures. Immediate loss mitigation reactions are implemented, such as load shedding and disconnecting node pairs for isolating failures. We formulate both Model 1 and Model 2 as mixed-integer programs, in which the first-stage problem designs a network, and the second-stage problem optimizes recourse operations for restoring service and mitigating losses. The goal is to minimize costs of infrastructure design and recovery operations, and we develop decomposition-based cutting-plane algorithms and heuristic approaches. For Model 1, we test our approaches on an IEEE 118-bus system and compare the effectiveness of cutting planes provided by different approaches under varying parameter settings. Model 2 are tested on two- and three-infrastructure systems consisting of the 118-bus system, as well as 20- and/or 50-node networks, whose interdependencies are randomly generated. We demonstrate the computational efficacy by comparing CPU times and objectives.
Keywords: Stochastic network optimization; mixed-integer programming; decomposition; cutting-plane algorithms; critical infrastructure analysis.
Category 1: Integer Programming (Cutting Plane Approaches )
Category 2: Integer Programming ((Mixed) Integer Linear Programming )
Category 3: Network Optimization
Citation: Department of Industrial and Operations Engineering, University of Michigan, Ann Arbor, MI, June 2012
Entry Submitted: 06/20/2012
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|