NETWORK DESIGN PROBLEM WITH RELAYS:
Abstract: Relays are regenerators extending the reach of optical signals in telecommunication networks; they may be strategic locations where exchange of drivers, trucks or mode of transportation takes place in transportation networks; they may become refuelling/recharging stations extending the reach of alternative fuel vehicles in green transportation. With different names and characteristics, relays play a crucial role in the design of telecommunication and transportation networks. We study the network design problem with relays and present a multi-commodity flow formulation and a branch-and-price algorithm to solve it. Motivated by the practical applications we investigate the special case where each demand has a common designated source. In this special case, we show that there exists an optimal design that is a tree. Using this fact, we replace the multi-commodity flow formulation with a tree formulation enhanced with Steiner and connectivity cuts. Employing a branch-and-price-and-cut schema on this formulation, we are able to further extend computational efficiency. Our extensive computational experiments indicate the efficacy of the proposed solution approaches solving problem instances up to 500 nodes.
Bio: Barış Yıldız is a Ph.D. candidate at Bilkent University Industrial Engineering Department. He holds an M.S. degree in Operations Research from U.S. Naval Postgraduate School and a B.S. degree in Systems Engineering from Turkish Army Academy. He is currently working as an operations research analyst at the Project Management Division of Turkish General Staff Headquarters. His research focuses on network design problems with relays and their applications in telecommunication and transportation networks.
February 3, 2016 – 13:40, FENS G032