Optimized packing unequal spheres into a multiconnected domain: mixed-integer non-linear programming approach. Issue 1 (2nd January 2021)

• Record Type: Journal Article
• Authors: Stoyan, Yuriy; Yaskov, Georgiy
• Is Part Of: International journal of computer mathematics. Volume 6:Issue 1(2021)
• Page Start: 94
• Page End: 111
• Publication Date: 2021-01-02
• Subjects: Optimization -- packing -- sphere -- container -- prohibited domains; 52C17; Computer systems -- Periodicals; Computer systems; Periodicals; 004
• DOI: 10.1080/23799927.2020.1861105
• Languages: English
• ISSNs: 2379-9927

Abstract

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.