Autores

5756
Renan Vicente Pinto
2240,44
5757
2240,44

Informações:

Publicações do PESC

Título
O Problema de Recobrimento de Sólidos por Esferas de Diferentes Raios
Linha de pesquisa
Otimização
Tipo de publicação
Tese de Doutorado
Número de registro
Data da defesa
9/3/2015
Resumo

Neste trabalho, apresentamos um modelo de programação matemática para o problema de recobrimento de sólidos por esferas de diferentes raios.
Dado um conjunto de esferas, possivelmente de diferentes diâmetros, e um sólido, deseja-se posicionar essas esferas de tal modo que a união delas forme uma cobertura para esse sólido, utilizando a menor quantidade possível de esferas desse conjunto. Esse problema tem aplicação no planejamento do tratamento por radiocirurgia conhecida como Gamma Knife e pode ser formulado como um problema de otimização não-convexa, com restrições quadráticas e função objetivo linear. Utilizamos técnicas de discretização a fim de trabalhar com um modelo linear. Propomos, ainda, uma heurística e uma reformulação baseada em uma estrutura de grafos, onde a clique de peso máximo é a solução ótima do modelo original, com a finalidade de encontrar boas soluções em tempos razoáveis.

Abstract

In this work, we present a mathematical programming model for the problem of covering solids by spheres of different radii. Given a set of spheres, possibly with different diameters, and a solid, the goal is to locate the spheres in such a way their union forms a coverage for this solid, using the smallest possible number of spheres of this set. This problem has an application in the radiosurgical treatment planning known as Gamma Knife and can be formulated as a nonconvex optimization problem with quadratic constraints and a linear objective function. Linearizations techniques are also proposed to obtain a linear model. We also present an heuristic and reformulation based on a graph structure, where the maximum weight clique is the optimal solution the original model, in order to find good solutions in reasonable times.

Topo