Discretization-based solution approaches for the circle packing problem

The problem of packing a set of circles into the smallest surrounding container is considered. This problem arises in different application areas such as the automobile, textile, food and chemical industries. The so-called circle packing problem can be cast as a non-convex quadratically constrained program, and is difficult to solve in general. An iterative solution approach based on a bisection-type algorithm on the radius of the larger circle is provided. The present algorithm discretizes the container into small cells and solves two different integer linear programming formulations proposed for a restricted and a relaxed version of the original problem. The present algorithm is enhanced with solution space reduction, bound tightening and variable elimination techniques. Then, a computational study is performed to evaluate the performance of the algorithm. The present algorithm is compared with the BARON and Gurobi $ <^>{{\rm \textsc {tm}}} $ tm optimizers, which solve the original nonlinear formulation, and heuristic methods from the literature. Promising results are obtained.