A non-oscillating beam-search with a look-ahead for the circular packing problem

This paper addresses the circular packing problem (CPP) which consists in packing n circles C_i, each of known radius r_i, i ¿ N = {1,...,n}, into the smallest containing circle C. The objective is to determine the radius r of C as well as the coordinates (x_i, y_i) of each circle C_i. This problem is solved via a binary search that evaluates the solution using a non-oscillating beam search with separate beams (instead of pooled ones). This beam search guarantees a monotonic decrease of r as the beam width increases. A node of level l of the beam search tree represents a partial packing of l circles into C. The potential of each node of the tree is assessed via a look-ahead strategy. The computational results on different benchmark instances show the effectiveness of the algorithm.