Valid inequalities and facets for multi‐module survivable network design problem. Issue 2 (24th August 2022)

• Record Type: Journal Article
• Authors: Luo, Haochen; Kianfar, Kiavash
• Is Part Of: Networks. Volume 81:Issue 2(2023)
• Page Start: 155
• Page End: 176
• Publication Date: 2022-08-24
• Subjects: cutting planes -- integer programming -- network design -- n$$ n $$‐step cutset inequalities -- n$$ n $$‐step MIR -- survivable network design -- telecommunication backbone network; Network analysis (Planning) -- Periodicals; 658.4032
• DOI: 10.1002/net.22122
• Languages: English
• ISSNs: 0028-3045

Abstract

Abstract: Capacitated survivable network design (SND), that is, designing a network that can survive edge failures with minimum flow‐routing plus capacity‐installation cost, is a fundamental problem in network science and its applications. In this article, we study a highly applicable form of the SND, referred to as the multi‐module SND (MM‐SND), in which transmission capacities on edges can be sum of integer multiples of differently sized capacity modules. We formulate MM‐SND as mixed integer programs, where existing structures of the network (p‐cycles) are used to protect edge failures. We derive valid inequalities for MM‐SND through polyhedral analysis and show that the valid inequalities previously developed in the literature for the single‐module SND are special cases of these inequalities. Furthermore, we show that these inequalities define facets for the convex hull of MM‐SND in many cases. Our computational results show that these inequalities are very effective in solving MM‐SND problem instances.