Talks and Poster Presentations (without Proceedings-Entry):
M. Riedler, M. Leitner, I. Ljubic, M. Ruthmair:
"Using Layered Graphs to solve the Directed Network Design Problem with Relays";
Talk: 21st Conference of the International Federation of Operational Research Societies,
We consider mixed integer linear programming models for the directed network design problem with relays (DNDPR) based on layered graphs. DNDPR originates from telecommunication network design but also has applications in hub location and electric mobility. The problem is based on a family of origin-destination pairs and a set of arcs that can be established in the network. A subset of arcs has to be selected in order to allow communication between all these pairs but communication paths must not exceed a certain distance limit. To transmit the signal farther, regeneration devices (relays) have to be installed. The goal is to allow all pairs to communicate while minimizing the costs for establishing arcs and relays.
Previous work in the area involves a node-arc formulation and a branch-and-price approach. We propose two compact formulations and a model based on an exponential number of constraints. The latter is solved using a branch-and-cut algorithm. An experimental study demonstrates the effectiveness of our novel formulations on a diverse set of benchmark instances.
Created from the Publication Database of the Vienna University of Technology.