Packing equal circles into a circle with circular prohibited areas

Abstract

The paper considers the problem of packing a maximal number of identical circles of a given radius into a multiconnected domain. The domain is a circle with prohibited areas to be finite unions of circles of given radii. We construct a mathematical model of the problem and investigate its characteristics. The starting points are constructed in a random way or on the ground of the hexagonal lattice. To find the local maxima, a modification of the Zoutendijk method of feasible directions and a strategy of active inequalities are applied. We compare our results with the benchmark instances of packing circles into circular and annular containers. A number of numerical examples are given.

Keywords:

• packing
• circle
• prohibited area
• modelling
• optimization

2000 AMS Subject Classification :

• 52C15

Acknowledgements

The authors thank Dr Csaba Mészáros for providing the special interior point solver BPMPD, which essentially improves the runtime and quality of solutions obtained.