Optimal covering of solid bodies by spheres via the hyperbolic smoothing technique
- 23 July 2014
- journal article
- research article
- Published by Taylor & Francis in Optimization Methods and Software
- Vol. 30 (2) , 391-403
Abstract
We consider the problem of optimally covering solid bodies by a given number of spheres. The mathematical modelling of this problem leads to a min–max–min formulation which, in addition to its intrinsic multi-level nature, has the significant characteristic of being non-differentiable. The use of the hyperbolic smoothing technique engenders a simple one-level nonlinear programming problem and allows overcoming the main difficulties presented by the original one. To illustrate the performance of the method we present computational results for two large test covering problems with up to 1,200,000 voxels. The first problem is the covering of a ring torus whose optimal solution is known whenever the number of covering spheres is small, and the second problem is a generic test problem.Keywords
This publication has 15 references indexed in Scilit:
- Downscaling spatial structure for the analysis of epidemiological dataComputers, Environment and Urban Systems, 2008
- Solving the continuous space p-centre problem: planning application issuesIMA Journal of Management Mathematics, 2006
- An Optimization Approach for Radiosurgery Treatment PlanningSIAM Journal on Optimization, 2002
- Hyperbolic Penalty: A New Method for Nonlinear Programming with InequalitiesInternational Transactions in Operational Research, 2001
- On Smoothing Exact Penalty Functions for Convex Constrained OptimizationSIAM Journal on Optimization, 1994
- A smooth method for the finite minimax problemMathematical Programming, 1993
- The sphere packing problemJournal of Computational and Applied Mathematics, 1992
- Smooth Optimization Methods for Minimax ProblemsSIAM Journal on Control and Optimization, 1988
- Parallel application of block-iterative methods in medical imaging and radiation therapyMathematical Programming, 1988
- On the maximization of a certain nondifferentiable functionJournal of Optimization Theory and Applications, 1971