Planar Maximum Covering Location by Ellipses is an optimization problem where one wants to place fixed shape ellipses on the plane to cover demand points maximizing a function depending on the value of covered points. We propose new exact algorithms for two versions of this problem, one where the ellipses have to be parallel to the coordinate axis, and another where they can be freely rotated. Besides finding optimal solutions for previously published instances, including the ones where no optimal solution was known, both algorithms proposed by us were able to obtain optimal solutions for some new larger instances having with up to seven hundred demand points and five ellipses.

Cobertura Máxima Planar por Ellipses é um problema de otimização em que deseja-se determinar o local para ellipses de forma fixa no plano para cobrir pontos de demanda para maximizar uma função que depende do valor dos pontos cobertos. Neste trabalho, propomos novos algoritmos exatos para duas versões desse problema, uma em que as ellipses tem que ser paralelas em relação aos eixos do sistema de coordenadas, e outro em que elas podem ser rotacionadas livremente. Além de encontrarmos soluções ótimas para instâncias previamente publicadas, incluindo aquelas que nenhuma solução ótima era conhecida, ambos algoritmos propostos por este trabalho também foram capazes de determinar soluções ótimas para novas instâncias com até setecentos pontos e cinco ellipses.