Optimization Online


Two-stage Models and Algorithms for Optimizing Infrastructure Design and Recovery Operations under Stochastic Disruptions

Siqian Shen(siqian***at***umich.edu)

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

Download: [PDF]

Entry Submitted: 06/20/2012
Entry Accepted: 06/20/2012
Entry Last Modified: 06/20/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