Optimized packing unequal spheres into a multiconnected domain: mixed-integer non-linear programming approach

Abstract

The problem of packing unequal spheres into a multiconnected domain (container) is considered. Given a set of spheres, the objective is to maximize the packing factor. The problem is considered as a knapsack problem and modelled as a mixed-integer non-linear programming. Characteristics of the model are indicated. We propose a new solution method based on a combination of a branch-and-bound approach and the known local optimization method. The search procedure is represented by a tree which allows handling all possible subsets of spheres. We develop a set of truncation rules to reduce the number of variants under test. The local optimization algorithm proceeds from the assumption of spheres radii being variable. A number of numerical examples are given.

KEYWORDS:

• Optimization
• packing
• sphere
• container
• prohibited domains

2000 AMS Subject Classification:

• 52C17

Acknowledgements

We thank the anonymous reviewers for insightful comments and suggestions.

Disclosure statement

No potential conflict of interest was reported by the author(s).