Solving the sensor cover energy problem via integer linear programming

Pingke Li

Kybernetika (2021)

  • Volume: 57, Issue: 4, page 568-593
  • ISSN: 0023-5954

Abstract

top
This paper demonstrates that the sensor cover energy problem in wireless communication can be transformed into a linear programming problem with max-plus linear inequality constraints. Consequently, by a well-developed preprocessing procedure, it can be further reformulated as a 0-1 integer linear programming problem and hence tackled by the routine techniques developed in linear and integer optimization. The performance of this two-stage solution approach is evaluated on a set of randomly generated instances and demonstrates that it is capable of solving large size instances of the sensor cover energy problem.

How to cite

top

Li, Pingke. "Solving the sensor cover energy problem via integer linear programming." Kybernetika 57.4 (2021): 568-593. <http://eudml.org/doc/297452>.

@article{Li2021,
abstract = {This paper demonstrates that the sensor cover energy problem in wireless communication can be transformed into a linear programming problem with max-plus linear inequality constraints. Consequently, by a well-developed preprocessing procedure, it can be further reformulated as a 0-1 integer linear programming problem and hence tackled by the routine techniques developed in linear and integer optimization. The performance of this two-stage solution approach is evaluated on a set of randomly generated instances and demonstrates that it is capable of solving large size instances of the sensor cover energy problem.},
author = {Li, Pingke},
journal = {Kybernetika},
keywords = {sensor coverage problem; max-plus algebra; integer linear programming},
language = {eng},
number = {4},
pages = {568-593},
publisher = {Institute of Information Theory and Automation AS CR},
title = {Solving the sensor cover energy problem via integer linear programming},
url = {http://eudml.org/doc/297452},
volume = {57},
year = {2021},
}

TY - JOUR
AU - Li, Pingke
TI - Solving the sensor cover energy problem via integer linear programming
JO - Kybernetika
PY - 2021
PB - Institute of Information Theory and Automation AS CR
VL - 57
IS - 4
SP - 568
EP - 593
AB - This paper demonstrates that the sensor cover energy problem in wireless communication can be transformed into a linear programming problem with max-plus linear inequality constraints. Consequently, by a well-developed preprocessing procedure, it can be further reformulated as a 0-1 integer linear programming problem and hence tackled by the routine techniques developed in linear and integer optimization. The performance of this two-stage solution approach is evaluated on a set of randomly generated instances and demonstrates that it is capable of solving large size instances of the sensor cover energy problem.
LA - eng
KW - sensor coverage problem; max-plus algebra; integer linear programming
UR - http://eudml.org/doc/297452
ER -

References

top
  1. Astorino, A., Miglionico, G., , Optim. Lett. 10 (2016), 2, 355-368. DOI
  2. Bartolini, N., Calamoneri, T., Porta, T. La, Petrioli, C., Silvestri, S., 10.1145/2240092.2240098, ACM Trans. Sensor Netw. 8 (2012), 3, Article 24. DOI10.1145/2240092.2240098
  3. Butkovič, P., Max-linear Systems: Theory and Algorithms., Springer, Berlin 2010. Zbl1202.15032
  4. Elbassioni, K. M., , Fuzzy Sets Syst. 159 (2008), 2272-2277. DOI
  5. Fredman, M. L., Khachiyan, L., , J. Algorithms 21 (1996), 618-628. DOI
  6. Hoai, P. T., Tuy, H., , Optim. Lett. 12 (2018), 1569-1587. DOI
  7. Thi, H. A. Le, Pham, D. T., , Ann. Oper. Res. 133 (2005), 23-46. DOI
  8. Thi, H. A. Le, Pham, D. T., , Math. Program., Ser. B 169 (2018), 5-68. DOI
  9. Li, P., , Ph.D. Dissertation, North Carolina State University 2009. DOI
  10. Li, P., Fang, S.-C., , Fuzzy Optim. Decis. Making 7 (2008), 169-214. Zbl1169.90493DOI
  11. Li, P., Fang, S.-C., Latticized linear optimization on the unit interval., IEEE Trans. Fuzzy Syst. 16 (2009), 6, 1353-1365. 
  12. Priyadarshi, R., Gupta, B., Anurag, A., , J. Supercomput. 76 (2020), 7333-7373. DOI
  13. ReVelle, C. S., , Eur. J. Oper. Res. 65 (1993), 2, 147-158. DOI
  14. Tuy, H., Minoux, M., Phuong, N. T. H., , SIAM J. Optim. 17 (2006), 78-97. DOI
  15. Wang, B., 10.1145/1978802.1978811, ACM Comput. Surv. 43 (2011), 4, Article 32. DOI10.1145/1978802.1978811
  16. Wang, Y., Wu, S., Chen, Z., Gao, X., Chen, G., , Comput. Netw. 123 (2017), 200-232. DOI
  17. Zhou, Z., Das, S.R., Gupta, H., 10.1145/1464420.1464428, ACM Trans. Sensor Netw. 5 (2009), 1, Article 8. DOI10.1145/1464420.1464428

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.