Packing ellipsoids into volume-minimizing rectangular boxes

Josef Kallrath ()
Additional contact information
Josef Kallrath: BASF SE, Scientific Computing, GMC/MS-B009

Journal of Global Optimization, 2017, vol. 67, issue 1, No 8, 185 pages

Abstract: Abstract A set of tri-axial ellipsoids, with given semi-axes, is to be packed into a rectangular box; its widths, lengths and height are subject to lower and upper bounds. We want to minimize the volume of this box and seek an overlap-free placement of the ellipsoids which can take any orientation. We present closed non-convex NLP formulations for this ellipsoid packing problem based on purely algebraic approaches to represent rotated and shifted ellipsoids. We consider the elements of the rotation matrix as variables. Separating hyperplanes are constructed to ensure that the ellipsoids do not overlap with each other. For up to 100 ellipsoids we compute feasible points with the global solvers available in GAMS. Only for special cases of two ellipsoids we are able to reach gaps smaller than $$10^{-4}$$ 10 - 4 .

Keywords: Global optimization; Non-convex nonlinear programming; Packing problem; Ellipsoid representation; Non-overlap constraints; Computational geometry (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (6)

Downloads: (external link)
http://link.springer.com/10.1007/s10898-015-0348-6 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jglopt:v:67:y:2017:i:1:d:10.1007_s10898-015-0348-6

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10898

DOI: 10.1007/s10898-015-0348-6

Access Statistics for this article

Journal of Global Optimization is currently edited by Sergiy Butenko

More articles in Journal of Global Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().