A fast ILP-based Heuristic for the robust design of Body Wireless Sensor Networks
This work addresses the robust design of body wireless sensor networks, which is important for healthcare monitoring, but it is incremental as it builds on existing ILP methods.
The authors tackled the problem of designing body wireless sensor networks under data uncertainty by proposing a heuristic that combines variable fixing and large neighborhood search, achieving solutions of much higher quality than state-of-the-art solvers and benchmark heuristics.
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.