Packing Unit Spheres into a Cube Using VNS

This paper applies a variable neighborhood search (VNS) to the difficult problem of packing unit radii spheres into the smallest cube (PSC). VNS identifies (near-) global optima by searching the neighborhoods of local minima. It obtains neighboring solutions by shaking one or more spheres. It alters the size of a neighborhood every time it fails to find an improving solution. VNS matches 42 out of 55 upper bounds.