The discrete ellipsoid covering problem: A discrete geometric programming approach

The ellipsoid covering problem consists of covering an ellipsoid with spheres whose radii belong to a discrete set. The discrete nature of the radii of the spheres is one of the difficulties inherent to solving this problem. The other difficulty is to ensure that every point of the ellipsoid is covered by at least one sphere. Despite these difficulties, a good reason for studying this problem is its application in configuring gamma ray machines, used for treatment of brain tumors. This is a semi-infinite nonlinear discrete problem. To solve it, we present a weak version and model it as a discrete signomial geometric programming problem. To obtain convex constraints, we apply the condensation technique to approximate the model in combination with a continuous model applied to the discrete part. Thus, we use a primal dual interior point method to solve the problem. During model construction, we determine the smallest number of spheres that can be used to cover the ellipsoid using an auxiliary model that is similar to the model of the Knapsack problem. Finally, we present computational results for experiments.