The discrete ellipsoid covering problem: A discrete geometric programming approach
| Autor: | Lucídio dos Anjos Formiga Cabral, Ana Flávia Uzeda dos Santos Macambira, Renan Vicente Pinto, Roberto Quirino do Nascimento |
|---|---|
| Rok vydání: | 2014 |
| Předmět: |
Mathematical optimization
Continuous modelling Applied Mathematics Ellipsoid method MathematicsofComputing_NUMERICALANALYSIS Ellipsoid Discrete system Knapsack problem Discrete optimization Discrete Mathematics and Combinatorics Applied mathematics Geometric programming Interior point method ComputingMethodologies_COMPUTERGRAPHICS Mathematics |
| Zdroj: | Discrete Applied Mathematics. 164:276-285 |
| ISSN: | 0166-218X |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect