Optimization Online


Facet-Defining Inequalities for Multi-Module Survivable Network Design Problem

Haochen Luo(hcluo***at***tamu.edu)
Kiavash Kianfar(kianfar***at***tamu.edu)

Abstract: Capacitated survivable network design (SND), i.e., 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 paper, 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. For the first time, we formulate the MM-SND as a mixed integer program (MIP) using preconfigured-cycles (p-cycles) to reroute flow on failed edges. We derive several classes of valid inequalities for this MIP, and show that the valid inequalities previously developed in the literature for the single-module SND are special cases of our inequalities. Furthermore, we show that our valid inequalities are facet-defining for the MM-SND in many cases. Our computational results, using a heuristic separation algorithm, show that these inequalities are very effective in solving the MM-SND. In particular they are more effective than compared to using single-module inequalities alone.

Keywords: multi-module survivable network design; n-step cutset inequalities; n-step MIR; telecommunication network design

Category 1: Integer Programming ((Mixed) Integer Linear Programming )

Category 2: Integer Programming (Cutting Plane Approaches )

Category 3: Applications -- Science and Engineering (Facility Planning and Design )


Download: [PDF]

Entry Submitted: 05/08/2019
Entry Accepted: 05/08/2019
Entry Last Modified: 05/08/2019

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