An interval method to validate optimal solutions of the ‘packing circles in a unit square’ problems

A numerical algorithm using new kinds of approaches is presented for the packing circles in a unit square problem class. A fully interval-based algorithm is built using a branch-and-bound approach to obtain solutions with guaranteed reliability. This requires some modifications in the basic tools of an interval B&B algorithm, such as giving a non-trivial interval inclusion function for the non-differentiable objective function and proposing a new monotonicity test without gradient evaluation to determine the monotonic parts of the objective function. A furher new interval accelerating device is also introduced based on the real-type ‘method of active areas’ of other algorithms designed for packing problems. The applicability of the presented algorithm is investigated in some preliminary tests, for both validating known real solutions locally, and for determining global solutions. The results show that the presented tools are effective, and suitable to give the base of an advanced interval-based searching method.