Authors: M'Hallah, Rym
Alkandari, Abdulaziz
Mladenović, Nenad 
Title: Packing unit spheres into the smallest sphere using VNS and NLP
Journal: Computers and Operations Research
Volume: 40
Issue: 2
First page: 603
Last page: 615
Issue Date: 1-Feb-2013
Rank: M21
ISSN: 0305-0548
DOI: 10.1016/j.cor.2012.08.019
This paper addresses the NP hard optimization problem of packing identical spheres of unit radii into the smallest sphere (PSS). It models PSS as a non-linear program (NLP) and approximately solves it using a hybrid heuristic which couples a variable neighborhood search (VNS) with a local search (LS). VNS serves as the diversification mechanism whereas LS acts as the intensification one. VNS investigates the neighborhood of a feasible local minimum u in search for the global minimum, where neighboring solutions are obtained by shaking one or more spheres of u and the size of the neighborhood is varied by changing the number of shaken spheres, the distance and the direction each sphere is moved. LS intensifies the search around a solution u by subjecting its neighbors to a sequential quadratic algorithm with non-monotone line search (as the NLP solver). The computational investigation highlights the role of LS and VNS in identifying (near) global optima, studies their sensitivity to initial solutions, and shows that the proposed hybrid heuristic provides more precise results than existing approaches. Most importantly, it provides computational evidence that the multiple-start strategy of non-linear programming solvers is not sufficient to solve PSS. Finally, it gives new upper bounds for 29 out of 48 benchmark instances of PSS.
Keywords: Non-linear programming | Three-dimensional packing | Unit-sphere packing | Variable neighborhood search
Publisher: Elsevier

Show full item record


checked on Jun 14, 2024

Page view(s)

checked on May 9, 2024

Google ScholarTM




Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.