Article ID Journal Published Year Pages File Type
479841 European Journal of Operational Research 2014 10 Pages PDF
Abstract

•We propose three mathematical formulations to model the Resilient Multi-level Hop-constrained Network Design problem.•We evaluate the performance of algorithms based on the proposed formulations.•We show that two formulations are equivalent and provide the same bounds for the problem.•A Branch-and-price approach for the problem presents a much better performance than other traditional optimization tools

In this work, we investigate the Resilient Multi-level Hop-constrained Network Design (RMHND) problem, which consists of designing hierarchical telecommunication networks, assuring resilience against random failures and maximum delay guarantees in the communication. Three mathematical formulations are proposed and algorithms based on the proposed formulations are evaluated. A Branch-and-price algorithm, which is based on a delayed column generation approach within a Branch-and-bound framework, is proven to work well, finding optimal solutions for practical telecommunication scenarios within reasonable time. Computational results show that algorithms based on the compact formulations are able to prove optimality for instances of limited size in the scenarios of interest while the proposed Branch-and-price algorithm exhibits a much better performance.

Related Topics
Physical Sciences and Engineering Computer Science Computer Science (General)
Authors
, , ,