Optimization Online


Network Design Problem with Relays

Baris Yildiz (baris.yildiz***at***bilkent.edu.tr)
Oya Karasan (karasan***at***bilkent.edu.tr)
Hande Yaman (hyaman***at***bilkent.edu.tr)

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 can 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 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.

Keywords: Relay, regenerator location, Network design, branch and price

Category 1: Applications -- OR and Management Sciences

Category 2: Applications -- OR and Management Sciences (Transportation )

Category 3: Applications -- OR and Management Sciences (Telecommunications )

Citation: Yıldız, Barış, Oya Ekin Karaşan, and Hande Yaman. “Branch-and-Price Approaches for the Network Design Problem with Relays.” Computers & Operations Research (2018).

Download: [PDF]

Entry Submitted: 11/26/2015
Entry Accepted: 11/26/2015
Entry Last Modified: 01/24/2018

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