| Full text | |
| Author(s): |
Birgin, E. G.
;
Lobato, R. D.
;
Martinez, J. M.
Total Authors: 3
|
| Document type: | Journal article |
| Source: | Journal of Global Optimization; v. 68, n. 3, p. 467-499, JUL 2017. |
| Web of Science Citations: | 5 |
| Abstract | |
The problem of packing ellipsoids is considered in the present work. Usually, the computational effort associated with numerical optimization methods devoted to packing ellipsoids grows quadratically with respect to the number of ellipsoids being packed. The reason is that the number of variables and constraints of ellipsoids' packing models is associated with the requirement that every pair of ellipsoids must not overlap. As a consequence, it is hard to solve the problem when the number of ellipsoids is large. In this paper, we present a nonlinear programming model for packing ellipsoids that contains a linear number of variables and constraints. The proposed model finds its basis in a transformation-based non-overlapping model recently introduced by Birgin et al. (J Glob Optim 65(4):709-743, 2016). For solving large-sized instances of ellipsoids' packing problems with up to 1000 ellipsoids, a multi-start strategy that combines clever initial random guesses with a state-of-the-art (local) nonlinear optimization solver is presented. Numerical experiments show the efficiency and effectiveness of the proposed model and methodology. (AU) | |
| FAPESP's process: | 13/07375-0 - CeMEAI - Center for Mathematical Sciences Applied to Industry |
| Grantee: | José Alberto Cuminato |
| Support Opportunities: | Research Grants - Research, Innovation and Dissemination Centers - RIDC |
| FAPESP's process: | 13/05475-7 - Computational methods in optimization |
| Grantee: | Sandra Augusta Santos |
| Support Opportunities: | Research Projects - Thematic Grants |
| FAPESP's process: | 10/10133-0 - Cutting, packing, lot-sizing and scheduling problems and their integration in industrial and logistics settings |
| Grantee: | Reinaldo Morabito Neto |
| Support Opportunities: | Research Projects - Thematic Grants |
| FAPESP's process: | 13/03447-6 - Combinatorial structures, optimization, and algorithms in theoretical Computer Science |
| Grantee: | Carlos Eduardo Ferreira |
| Support Opportunities: | Research Projects - Thematic Grants |
| FAPESP's process: | 12/23916-8 - Ellipsoid packing |
| Grantee: | Rafael Durbano Lobato |
| Support Opportunities: | Scholarships in Brazil - Doctorate |