A matheuristic approach with nonlinear subproblems for large-scale packing of ellipsoids

Abstract The problem of packing ellipsoids in the three-dimensional space is considered in the present work. The proposed approach combines heuristic techniques with the resolution of recently introduced nonlinear programming models in order to construct solutions with a large number of ellipsoids. The introduced approach is able to pack identical and non-identical ellipsoids within a variety of containers. Moreover, it allows the inclusion of additional positioning constraints. This fact makes the proposed approach suitable for constructing large-scale solutions with specific positioning constraints in which density may not be the main issue. Numerical experiments illustrate that the introduced approach delivers good quality solutions with a computational cost that scales linearly with the number of ellipsoids; and solutions with more than a million ellipsoids are exhibited.

• Publication year

  2019

• Venue

  European Journal of Operational Research

• Publication date

  2019-01-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1016/J.EJOR.2018.07.006
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Molecular

  2019cited by this paper
• Fabrication of Ellipsoidal Mesostructures in Block Copolymers via a Step-Shear Deformation

  2018cited by this paper
• Interparticle force analysis on the packing of fine ellipsoids

  2017cited by this paper
• High-density equilibrium phases of colloidal ellipsoids by application of optically enhanced, direct current electric fields.

  2017cited by this paper
• Effective Properties of Composites with Periodic Random Packing of Ellipsoids

  2017cited by this paper
• DEM simulation on the packing of fine ellipsoids

  2016cited by this paper
• General Ellipse Packings in an Optimized Circle Using Embedded Lagrange Multipliers

  2016cited by this paper
• A nonlinear programming model with implicit variables for packing ellipsoids

  2016cited by this paper
• Packing ellipsoids into volume-minimizing rectangular boxes

  2015influential reference
• Packing ellipsoids by nonlinear optimization

  2015cited by this paper
• Quasi-phi-functions and optimal packing of ellipses

  2015cited by this paper
• Quasi-Phi-Functions in Packing Problem of Ellipsoids

  2015cited by this paper
• Particle-based simulation of ellipse-shaped particle aggregation as a model for vascular network formation

  2015cited by this paper
• Cutting ellipses from area-minimizing rectangles

  2014influential reference
• Practical augmented Lagrangian methods for constrained optimization

  2014cited by this paper
• cellPACK: A Virtual Mesoscope to Model and Visualize Structural Systems Biology

  2014cited by this paper
• X-ray tomography study of the random packing structure of ellipsoids.

  2014cited by this paper
• Numerical optimization methods for packing equal orthogonally oriented ellipses in a rectangular domain

  2013cited by this paper
• I and J

  2012influential reference
• Packing Ellipsoids with Overlap

  2012cited by this paper
• Colloidal suspensions

  2011cited by this paper
• Experiments on the random packing of tetrahedral dice.

  2010cited by this paper
• On Augmented Lagrangian Methods with General Lower-Level Constraints

  2007cited by this paper
• Brownian Motion of an Ellipsoid

  2006cited by this paper
• Underconstrained jammed packings of nonspherical hard particles: ellipses and ellipsoids.

  2006cited by this paper
• Neighbor list collision-driven molecular dynamics simulation for nonspherical hard particles.

  2005cited by this paper
• Improving the Density of Jammed Disordered Packings Using Ellipsoids

  2004influential reference
• Unusually dense crystal packings of ellipsoids.

  2004cited by this paper
• Packing optimization for automated generation of complex system's initial configurations for molecular dynamics and docking

  2003cited by this paper
• Thermodynamics and hydrodynamics of hard spheres: the role of gravity

  2000cited by this paper
• Controlled growth of hard-sphere colloidal crystals

  1999cited by this paper
• Granular solids, liquids, and gases

  1996cited by this paper
• Metastability and Crystallization in Hard-Sphere Systems.

  1996cited by this paper
• The Role of Entropy in the Specification of a Powder

  1994cited by this paper
• Physics of the Granular State

  1992cited by this paper
• A Geometrical Approach to the Structure Of Liquids

  1959cited by this paper
• Phase Transition for a Hard Sphere System

  1957cited by this paper

• A Framework for Efficient Approximation Schemes on Geometric Packing Problems of $d$-dimensional Fat Objects

  2024cites this paper
• Establishing metrics to quantify spatial similarity in spherical and red blood cell distributions

  2023cites this paper
• Diffusion model of sulfate ions in concrete based on pore change of cement mortar and its application in mesoscopic numerical simulation

  2022cites this paper
• Establishing Metrics to Quantify Underlying Structure in Vascular Red Blood Cell Distributions

  2022cites this paper
• Sparse Balanced Layout of Spherical Voids in Three-Dimensional Domains

  2021cites this paper
• A support tool for planning classrooms considering social distancing between students

  2021influential citation
• Effects of volume fraction and particle shape on the rheological properties of oblate spheroid suspensions

  2021cites this paper
• Optimized advance front method of packing dense ellipse for generating the convex polygon structure statistically equivalent with real material

  2020cites this paper
• An Optimized Covering Spheroids by Spheres

  2020cites this paper
• Packing ellipsoids in an optimized cylinder

  2020cites this paper
• Filling of Irregular Channels with Round Cross-Section: Modeling Aspects to Study the Properties of Porous Materials

  2018cites this paper