Perturbation-Based Thresholding Search for Packing Equal Circles and Spheres

Xiangjing Lai (), Jin-Kao Hao (), Renbin Xiao () and Fred Glover ()
Additional contact information
Xiangjing Lai: Institute of Advanced Technology, Nanjing University of Posts and Telecommunications, Nanjing 210023, China
Jin-Kao Hao: Laboratoire d’Etude et de Recherche en Informatique d’Angers (LERIA), Université d’Angers, 49045 Angers, France
Renbin Xiao: School of Artificial Intelligence and Automation, Huazhong University of Science and Technology, Wuhan 430074, China
Fred Glover: Electrical, Computer & Energy Engineering (ECEE)—College of Engineering & Applied Science, University of Colorado, Boulder, Colorado 80309

INFORMS Journal on Computing, 2023, vol. 35, issue 4, 725-746

Abstract: This paper presents an effective perturbation-based thresholding search for two popular and challenging packing problems with minimal containers: packing N identical circles in a square and packing N identical spheres in a cube. Following the penalty function approach, we handle these constrained optimization problems by solving a series of unconstrained optimization subproblems with fixed containers. The proposed algorithm relies on a two-phase search strategy that combines a thresholding search method reinforced by two general-purpose perturbation operators and a container adjustment method. The performance of the algorithm is assessed relative to a large number of benchmark instances widely studied in the literature. Computational results show a high performance of the algorithm on both problems compared with the state-of-the-art results. For circle packing, the algorithm improves 156 best-known results (new upper bounds) in the range of 2 ≤ N ≤ 400 and matches 242 other best-known results. For sphere packing, the algorithm improves 66 best-known results in the range of 2 ≤ N ≤ 200 , whereas matching the best-known results for 124 other instances. Experimental analyses are conducted to shed light on the main search ingredients of the proposed algorithm consisting of the two-phase search strategy, the mixed perturbation and the parameters.

Keywords: circle and sphere packing; global optimization; constrained optimization; nonlinear nonconvex optimization; heuristics (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2023.1290 (application/pdf)

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:inm:orijoc:v:35:y:2023:i:4:p:725-746

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().