A fast ILP-based Heuristic for the robust design of Body Wireless Sensor Networks
arXiv:1704.04640 · doi:10.1007/978-3-319-55849-3_16
Abstract
We consider the problem of optimally designing a body wireless sensor network, while taking into account the uncertainty of data generation of biosensors. Since the related min-max robustness Integer Linear Programming (ILP) problem can be difficult to solve even for state-of-the-art commercial optimization solvers, we propose an original heuristic for its solution. The heuristic combines deterministic and probabilistic variable fixing strategies, guided by the information coming from strengthened linear relaxations of the ILP robust model, and includes a very large neighborhood search for reparation and improvement of generated solutions, formulated as an ILP problem solved exactly. Computational tests on realistic instances show that our heuristic finds solutions of much higher quality than a state-of-the-art solver and than an effective benchmark heuristic.
This is the authors' final version of the paper published in G. Squillero and K. Sim (Eds.): EvoApplications 2017, Part I, LNCS 10199, pp. 1-17, 2017. DOI: 10.1007/978-3-319-55849-3\_16. The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-319-55849-3_16
References in corpus (5)
- Towards the fast and robust optimal design of Wireless Body Area Networks
- 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
- A hybrid primal heuristic for Robust Multiperiod Network Design