New proposals for modelling and solving the problem of covering solids using spheres of different radii
RAIRO - Operations Research - Recherche Opérationnelle, Tome 54 (2020) no. 3, pp. 873-882.

Given a solid T, represented by a compact set in ℝ3, the aim of this work is to find a covering of T by a finite set of spheres of different radii. Some level of intersection between the spheres is necessary to cover the solid. Moreover, the volume occupied by the spheres on the outside of T is limited. This problem has an application in the planning of a radio-surgery treatment known by Gamma Knife and can be formulated as a non-convex optimization problem with quadratic constraints and linear objective function. In this work, two new linear mathematical formulations with binary variables and a hybrid method are proposed. The hybrid method combines heuristic, data mining and an exact method. Computational results show that the proposed methods outperform the ones presented in the literature.

Reçu le :
Accepté le :
Première publication :
Publié le :
DOI : 10.1051/ro/2019041
Classification : 90C10
Mots-clés : Problem of covering solids, mathematical programming, hybrid method 
@article{RO_2020__54_3_873_0,
     author = {Gonz\'alez Silva, Pedro Henrique and Macambira, Ana Fl\'avia U. S. and Pinto, Renan Vicente and Simonetti, Luidi and Maculan, Nelson and Michelon, Philippe},
     title = {New proposals for modelling and solving the problem of covering solids using spheres of different radii},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {873--882},
     publisher = {EDP-Sciences},
     volume = {54},
     number = {3},
     year = {2020},
     doi = {10.1051/ro/2019041},
     mrnumber = {4078188},
     zbl = {1443.90250},
     language = {en},
     url = {http://archive.numdam.org/articles/10.1051/ro/2019041/}
}
TY  - JOUR
AU  - González Silva, Pedro Henrique
AU  - Macambira, Ana Flávia U. S.
AU  - Pinto, Renan Vicente
AU  - Simonetti, Luidi
AU  - Maculan, Nelson
AU  - Michelon, Philippe
TI  - New proposals for modelling and solving the problem of covering solids using spheres of different radii
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2020
SP  - 873
EP  - 882
VL  - 54
IS  - 3
PB  - EDP-Sciences
UR  - http://archive.numdam.org/articles/10.1051/ro/2019041/
DO  - 10.1051/ro/2019041
LA  - en
ID  - RO_2020__54_3_873_0
ER  - 
%0 Journal Article
%A González Silva, Pedro Henrique
%A Macambira, Ana Flávia U. S.
%A Pinto, Renan Vicente
%A Simonetti, Luidi
%A Maculan, Nelson
%A Michelon, Philippe
%T New proposals for modelling and solving the problem of covering solids using spheres of different radii
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2020
%P 873-882
%V 54
%N 3
%I EDP-Sciences
%U http://archive.numdam.org/articles/10.1051/ro/2019041/
%R 10.1051/ro/2019041
%G en
%F RO_2020__54_3_873_0
González Silva, Pedro Henrique; Macambira, Ana Flávia U. S.; Pinto, Renan Vicente; Simonetti, Luidi; Maculan, Nelson; Michelon, Philippe. New proposals for modelling and solving the problem of covering solids using spheres of different radii. RAIRO - Operations Research - Recherche Opérationnelle, Tome 54 (2020) no. 3, pp. 873-882. doi : 10.1051/ro/2019041. http://archive.numdam.org/articles/10.1051/ro/2019041/

[1] M.C. Ferris, L. Jinho and D.M. Shepard, An optimization approach for radiosurgery treatment planning. SIAM J. Optim. 13 (2002) 921. Available from: http://search-ebscohost-com.ez15.periodicos.capes.gov.br/login.aspx?direct=true&db=iih&AN=10281146&lang=pt-br&site=ehost-live. | DOI | MR | Zbl

[2] J.C. Ganz, Gamma Knife Surgery. Springer-Verlag Wien, Austria (1997). | DOI

[3] B. Goethals and M.J. Zaki, Advances in frequent itemset mining implementations: report on FIMI’03. Acm Sigkdd Explor. Newslett. 6 (2004) 109–117. | DOI

[4] G. Grahne, J. Zhu, Reducing the main memory consumptions of FPmax* and fpclose. In: Proc. Workshop Frequent Item Set Mining Implementations (FIMI 2004, Brighton, UK), Aachen, Germany. Citeseer (2004).

[5] L. Liberti, N. Maculan and Y. Zhang, Optimal configuration of gamma ray machine radiosurgery units: the sphere covering subproblem. Optim. Lett. 3 (2009) 109–121. | DOI | MR | Zbl

[6] Localsolver framework. Available from: http://www.localsolver.com. (2020).

[7] D.C. Lubke, Cobertura de corpos por esferas utilizando suavização hiperbólica, Master’s thesis, COPPE/UFRJ, Rio de Janeiro, 2 (2014).

[8] R.V. Pinto, Problema de Recobrimento de Sólidos por Esferas de Diferentes Raios. Ph.D. thesis, COPPE/UFRJ, Rio de Janeiro, 3 (2015).

[9] M.H. Ribeiro, A. Plastino and S.L. Martins, Hybridization of grasp metaheuristic with data mining techniques. J. Math. Model. Algorithms 5 (2006) 23–41. | DOI | MR | Zbl

[10] A. Sutou and Y. Dai, Global optimization approach to unequal global optimization approach to unequal sphere packing problems in 3D. J. Optim. Theory App. 114 (2002) 671–694. | DOI | Zbl

[11] M.B. Karam Venceslau, O Problema de Recobrimento Mínimo de um Corpo em Três Dimensões por Esferas de Diferentes Raios. PhD thesis, COPPE/UFRJ, Rio de Janeiro, 5 (2015).

Cité par Sources :