- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- International Conference on Applications of Statistics and Probability in Civil Engineering (ICASP) (12th : 2015) /
- The computational complexity of probabilistic Interdependent...
Open Collections
International Conference on Applications of Statistics and Probability in Civil Engineering (ICASP) (12th : 2015)
The computational complexity of probabilistic Interdependent Network Design Problems González, Andrés D.; Dueñas-Osorio, Leonardo; Sánchez-Silva, Mauricio; Medaglia, Andrés L.
Abstract
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.
Item Metadata
Title |
The computational complexity of probabilistic Interdependent Network Design Problems
|
Creator | |
Contributor | |
Date Issued |
2015-07
|
Description |
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.
|
Genre | |
Type | |
Language |
eng
|
Notes |
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.
|
Date Available |
2015-05-21
|
Provider |
Vancouver : University of British Columbia Library
|
Rights |
Attribution-NonCommercial-NoDerivs 2.5 Canada
|
DOI |
10.14288/1.0076118
|
URI | |
Affiliation | |
Citation |
Haukaas, T. (Ed.) (2015). Proceedings of the 12th International Conference on Applications of Statistics and Probability in Civil Engineering (ICASP12), Vancouver, Canada, July 12-15.
|
Peer Review Status |
Unreviewed
|
Scholarly Level |
Faculty
|
Rights URI | |
Aggregated Source Repository |
DSpace
|
Item Media
Item Citations and Data
Rights
Attribution-NonCommercial-NoDerivs 2.5 Canada