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.
Abe, F.H., Hoshino, E.A., Hill, A., Baldacci, R. (2019). A Branch-and-Price Algorithm for the Ring-Tree Facility Location Problem. ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE, 346, 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.
