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
Abstract: 
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

SCOPUSTM   
Citations

23
checked on Apr 14, 2021

Page view(s)

8
checked on Apr 15, 2021

Google ScholarTM

Check

Altmetric

Altmetric


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