Using Iterated Local Search for Efficiently Packing Unequal Disks in a Larger Circle

Abstract:

Packing unequal disks in a container as small as possible without mutual overlap is a NP-hard problem with a plenty of real world applications. In this paper, we introduced iterated local search to tackle with this problem, and using Critical Element Guided Perturbation (CEGP) strategy to jump out the local minimal, and using BFGS method to get each neighborhood optimized in local search procedure. Experiments showed its efficiency by breaking several world records of a set of benchmark.

• Periodical: Advanced Materials Research (Volumes 430-432)
• Pages: 1477-1481
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.430-432.1477
• Online since: January 2012
• Authors: Wen Qi Huang, Zhi Zhong Zeng, Ru Chu Xu, Zhang Hua Fu
• Keywords: Basin-Hopping, BFGS, Critical Element Guided Perturbation, Disks Packing, Iterated Local Search, NP-Hard

References

[1] E.G. Birgin, J.M. Martinez, D.P. Ronconi, Optimizing the Packing of Cylinders into a Rectangular Container: A Nonlinear Approach, European Journal of Operational Research, vol. 160(1), 2005, p.19–33.

DOI: 10.1016/j.ejor.2003.06.018

[2] I. Castillo, F.J. Kampas, J.D. Printer. Solving circle packing problems by global optimization: Numerical results and industrial applications, European Journal of Operational Research, Vol 191(3), 2008, pp.786-802.

DOI: 10.1016/j.ejor.2007.01.054

[3] M. D. Adickes, R. E. Billo, B. A. Norman, S. Banerjee, J. Nnaji et al., Optimization of indoor wireless communication network layouts, IIE. Trans., vol. 34(9), 2002, pp.823-836.

DOI: 10.1080/07408170208928915

[4] W. Q. Huang, Y. Li, C. M. Li and R. C. Xu, New heuristics for packing unequal circles into a circular container, Comput. Oper. Res. vol. 33, 2006, pp.2125-2142.

DOI: 10.1016/j.cor.2005.01.003

[5] M. Hifi and R. M'Hallah, A dynamic adaptive local search algorithm for the circular packing problem, Eur. J. Oper. Res., vol. 183, 2007, pp.1280-1294.

DOI: 10.1016/j.ejor.2005.11.069

[6] Z. P. Lü and W. Q. Huang, PERM for solving circle packing problem, Comput. Oper. Res., vol. 35, 2008, pp.1742-1755.

DOI: 10.1016/j.cor.2006.10.012

[7] H. Akeb, M. Hifi and R. M'Hallah, A beam search algorithm for the circular packing problem, Comput. Oper. Res., vol. 36, 2009, pp.1513-1528.

DOI: 10.1016/j.cor.2008.02.003

[8] D. F. Zhang and A. S. Deng, An effective hybrid algorithm for the problem of packing circles into a larger containing circle, Comput. Oper. Res., vol. 32, 2005, p.1941-(1951).

DOI: 10.1016/j.cor.2003.12.006

[9] E. G. Birgin and F. N. C. Sobral, Minimizing the object dimensions in circle and sphere packing problems, Comput. Oper. Res., vol. 35, 2008, pp.2357-2375.

DOI: 10.1016/j.cor.2006.11.002

[10] J. F. Liu, Y. L. Wang and J. J. Pan, Effciently Packing Circles into a Larger Containing Circle, HPCA. LNCS., vol. 5938, 2010, pp.250-256.

[11] W. Huang, Y. Li, B. Jurkowiak, C. Li, R. Xu, A two-level search strategy for packing unequal circles into a circular container, in: Proceedings of the International Conference on Principles and Practice of Constraint Programming, Springer, Berlin, 2003, p.868.

DOI: 10.1007/978-3-540-45193-8_69

[12] Lourenco, H.R., Martin, O., Stützle, T. Iterated local search,. In: Glover, F., Kochenberger, G. (eds. ) Handbook of Meta-heuristics, p.321–353. Springer, Heidelberg.

[13] F. Glover, M. Laguna, Tabu Search, Kluwer Academic, Boston, (1997).

[14] Z. P. Lü and Jin-Kao Hao. A Critical Element-Guided Perturbation Strategy for Iterated Local Search, Lecture Notes in Computer Science, vol 5482, 2009, pp.1-12.

DOI: 10.1007/978-3-642-01009-5_1

[15] Dong C. Liu, Jorge Nocedal , On the limited memory BFGS method for large scale optimization, Mathematical Programming, vol. 45, 1989, pp.503-528.

DOI: 10.1007/bf01589116

[16] Huang Wenqi, Zeng Zhizhong, Fu Zhanghua, Ruchu Xu, A new algorithm for packing unequal disks in a larger circle, to be published in American Journal of Engineering and Technology Research.

DOI: 10.1109/csip.2012.6308788