Open Collections

The computational complexity of probabilistic Interdependent Network Design Problems

International Conference on Applications of Statistics and Probability (12th : 2015 : Vancouver, B.C.)

We present a rigorous study of the computational complexity of an Interdependent Network Design Problem (INDP) solution model, which is at the core of future infrastructure restoration studies. The paper details how each constraint in the INDP formulation adds to the overall complexity, while also revealing strategies to tame the computational demands for large interdependent networks. It is shown how some algorithms that are used to enhance the Network Design Problem (NDP) (Poss 2011), including decomposition techniques, can be cleverly adapted to the INDP model. Computational examples are based on diverse yet idealized topologies, to illustrate the sensitivity of the INDP model to input parameters and constraints, as well as the underlying topological properties of the studied systems. The present study paves the way for future approaches to improve the INDP and its Mixed-Integer Programming (MIP) model, particularly in terms of its efficiency and capability to handle large size instances, and by extension, its ability to support practical infrastructure decision making and resilience analyses.

Text

This collection contains the proceedings of ICASP12, the 12th International Conference on Applications of Statistics and Probability in Civil Engineering held in Vancouver, Canada on July 12-15, 2015. Abstracts were peer-reviewed and authors of accepted abstracts were invited to submit full papers. Also full papers were peer reviewed. The editor for this collection is Professor Terje Haukaas, Department of Civil Engineering, UBC Vancouver.

Vancouver : University of British Columbia Library

10.14288/1.0076118

Non UBC

Unreviewed

http://creativecommons.org/licenses/by-nc-nd/2.5/ca/