The ring-tree facility location problem is a generalization of the capacitated ring-tree problem in which additional cost and capacity related to facilities are considered. Applications of this problem arise in the strategic design of bi-level telecommunication networks. We investigate an extended integer programming formulation for the problem and different approaches to deal with the NP-hardness of the pricing problem that appears in a branch-and-price algorithm to solve it. Computational experiments show how heuristics and relaxations improved the performance of a branch-and-price algorithm.
A Branch-and-Price Algorithm for the Ring-Tree Facility Location Problem / Abe, Fabio H.N.; Hoshino, Edna A.; Hill, Alessandro; Baldacci, Roberto. - In: ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE. - ISSN 1571-0661. - ELETTRONICO. - 346:(2019), pp. 3-14. [10.1016/j.entcs.2019.08.002]
A Branch-and-Price Algorithm for the Ring-Tree Facility Location Problem
Hill, Alessandro;Baldacci, Roberto
2019
Abstract
The ring-tree facility location problem is a generalization of the capacitated ring-tree problem in which additional cost and capacity related to facilities are considered. Applications of this problem arise in the strategic design of bi-level telecommunication networks. We investigate an extended integer programming formulation for the problem and different approaches to deal with the NP-hardness of the pricing problem that appears in a branch-and-price algorithm to solve it. Computational experiments show how heuristics and relaxations improved the performance of a branch-and-price algorithm.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
