Multi-commodity k-splittable survivable network design problems with relays

Abstract

The network design problem is a well known optimization problem with applications in telecommunication infrastructure designs and military operations. This paper devises the first formulation and solution methodology for the multi-commodity k-splittable two-edge disjoint survivable network design problem with capacitated edges and relays. This problem realistically portrays telecommunications network design but has not been solved previously due to its computational difficulty. Edge capacity is considered as either a discrete or a continuous variable. An exact method and a practical heuristic method are presented and computational results are discussed.