Optimal packing of 28 equal circles in a unit square - the first reliable solution

摘要

The paper deals with the problem class of finding the densest packings of non-overlapping equal circles within a unit square. We introduce a new interval branch-and-bound algorithm designed specifically for this optimization problem. After a brief description of the applied algorithmic tools, the capabilities of the algorithm are shown by solving the previously unsolved problem of packing 28 circles. The result confirms the optimality of an earlier found approximate solution and shows that it is unique in a certain sense.