Negative Cycle Separation in Wireless Network Design
arXiv:1704.04656 · doi:10.1007/978-3-642-21527-8_7
Abstract
The Wireless Network Design Problem (WND) consists in choosing values of radio-electrical parameters of transmitters of a wireless network, to maximize network coverage. We present a pure 0-1 Linear Programming formulation for the WND that may contain an exponential number of constraints. Violated inequalities of this formulation are hard to separate both theoretically and in practice. However, a relevant subset of such inequalities can be separated more efficiently in practice and can be used to strengthen classical MILP formulations for the WND. Preliminary computational experience confirms the effectiveness of our new technique both in terms of quality of solutions found and provided bounds.
This is the authors' final version of the paper published in Pahl J., Reiners T., Voss S. (eds), Network Optimization - INOC 2011. Lecture Notes in Computer Science, vol 6701, pp. 51-56. Springer, Berlin, Heidelberg, 2011, DOI: 10.1007/978-3-642-21527-8_7. The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-642-21527-8_7
Cited by in corpus (5)
- Towards an accurate solution of wireless network design problems
- A fast ILP-based Heuristic for the robust design of Body Wireless Sensor Networks
- A hybrid exact-ACO algorithm for the joint scheduling, power and cluster assignment in cooperative wireless networks
- An (MI)LP-based Primal Heuristic for 3-Architecture Connected Facility Location in Urban Access Network Design
- A hybrid primal heuristic for Robust Multiperiod Network Design