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.
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 Citations and Data
Attribution-NonCommercial-NoDerivs 2.5 Canada