An (MI)LP-based Primal Heuristic for 3-Architecture Connected Facility Location in Urban Access Network Design
arXiv:1512.09354 · doi:10.1007/978-3-319-31204-0_19
Abstract
We investigate the 3-architecture Connected Facility Location Problem arising in the design of urban telecommunication access networks. We propose an original optimization model for the problem that includes additional variables and constraints to take into account wireless signal coverage. Since the problem can prove challenging even for modern state-of-the art optimization solvers, we propose to solve it by an original primal heuristic which combines a probabilistic fixing procedure, guided by peculiar Linear Programming relaxations, with an exact MIP heuristic, based on a very large neighborhood search. Computational experiments on a set of realistic instances show that our heuristic can find solutions associated with much lower optimality gaps than a state-of-the-art solver.
arXiv commentThis is the authors' final version of the paper published in: Squillero G., Burelli P. (eds), EvoApplications 2016: Applications of Evolutionary Computation, LNCS 9597, pp. 283-298, 2016. DOI: 10.1007/978-3-319-31204-0_19. The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-319-31204-0_19
References in corpus (6)
- New results about multi-band uncertainty in Robust Optimization
- Towards the fast and robust optimal design of Wireless Body Area Networks
- A Fast Hybrid Primal Heuristic for Multiband Robust Capacitated Network Design with Multiple Time Periods
- GUB Covers and Power-Indexed formulations for Wireless Network Design
- On Improving the Capacity of Solving Large-scale Wireless Network Design Problems by Genetic Algorithms
- Negative Cycle Separation in Wireless Network Design