HYBRID OPTIMIZATION FOR THE 3D COVERING PROBLEM WITH SPHERES: INTEGRATING HEURISTICS, PATTERN MINING AND BRANCH AND CUT

ABSTRACT This paper addresses the challenge of covering three-dimensional solids with spheres of varying radii, allowing for partial overlaps, which is particularly relevant for applications such as gamma knife radiotherapy. In this work a novel approach is introduced, approximating the covering problem in the sense that it focuses on an objective function that maximizes the total volume of the used spheres, but it does not consider the volume of the overlapped regions. This approximation is further refined by discretizing the target volume and utilizing a finite set of potential sphere centers. Exact and hybrid methods are developed to solve this approximation. The exact method employs either a Branch-and-Bound or Branch-and-Cut algorithm, while the hybrid method integrates heuristic solutions and data mining techniques to identify promising sphere configurations, which are then refined using either Branch-and-Bound or Branch-and-Cut on a reduced search space. Data Envelopment Analysis (DEA) is used to determine optimal overlap parameters. Computational experiments demonstrate that the hybrid method outperforms the exact method in both coverage and computational efficiency, highlighting the efficacy of integrating heuristic, data mining, and exact techniques for solving complex optimization problems.