A formulation space search heuristic for packing unequal circles in a fixed size circular container. (English) Zbl 1346.90710
Summary: In this paper we consider the problem of packing unequal circles in a fixed size circular container, where the objective is to maximise the value of the circles packed. We consider two different objectives: maximise the number of circles packed; maximise the area of the circles packed. For the particular case when the objective is to maximise the number of circles packed we prove that the optimal solution is of a particular form. We present a heuristic for the problem based upon formulation space search. Computational results are given for a number of publicly available test problems involving the packing of up to 40 circles. We also present computational results, for test problems taken from the literature, relating to packing both equal and unequal circles.
MSC:
| 90C27 | Combinatorial optimization |
| 52C15 | Packing and covering in \(2\) dimensions (aspects of discrete geometry) |
| 90C11 | Mixed integer programming |
| 90C59 | Approximation methods and heuristics in mathematical programming |
Keywords:
circle packing; formulation space search; mixed-integer nonlinear optimisation; nonlinear optimisationReferences:
| [1] | Achterberg, T., SCIP: Solving constraint integer programs, Mathematical Programming Computation, 1, 1, 1-41 (2009) · Zbl 1171.90476 |
| [2] | Addis, B.; Locatelli, M.; Schoen, F., Efficiently packing unequal disks in a circle, Operations Research Letters, 36, 1, 37-42 (2008) · Zbl 1151.90035 |
| [3] | Akeb, H.; Hifi, M., Algorithms for the circular two-dimensional open dimension problem, International Transactions in Operational Research, 15, 6, 685-704 (2008) · Zbl 1377.90070 |
| [4] | Akeb, H.; Hifi, M., Solving the circular open dimension problem by using separate beams and look-ahead strategies, Computers & Operations Research, 40, 5, 1243-1255 (2013) · Zbl 1352.90078 |
| [5] | Akeb, H.; Li, Y., A hybrid heuristic for packing unequal circles into a circular container, International Conference on Service Systems and Service Management, 2, 922-927 (2006) |
| [6] | Al-Mudahka, I.; Hifi, M.; M’Hallah, R., Packing circles in the smallest circle: an adaptive hybrid algorithm, Journal of the Operational Research Society, 62, 11, 1917-1930 (2011) |
| [7] | Beasley, J. E., Or-library: distributing test problems by electronic mail, Journal of the Operational Research Society, 41, 11, 1069-1072 (1990) |
| [8] | Birgin, E. G.; Gentil, J. M., New and improved results for packing identical unitary radius circles within triangles, rectangles and strips, Computers & Operations Research, 37, 7, 1318-1327 (2010) · Zbl 1178.90283 |
| [9] | Birgin, E. G.; Sobral, F. N.C., Minimizing the object dimensions in circle and sphere packing problems, Computers & Operations Research, 35, 7, 2357-2375 (2008) · Zbl 1177.90332 |
| [10] | Brimberg, J.; Drezner, Z.; Mladenović, N.; Salhi, S., A new local search for continuous location problems, European Journal of Operational Research, 232, 2, 256-265 (2014) · Zbl 1305.90267 |
| [11] | Bussieck, M. R.; Vigerske, S., MINLP solver software, (Cochran, J. J.; Cox, L. A.; Keskinocak, P.; Kharoufeh, J. P.; Smith, J. C., Wiley Encyclopaedia of operations research and management science (2011), Wiley: Wiley New York) |
| [12] | Butenko, S.; Yezerska, O.; Balasundaram, B., Variable objective search, Journal of Heuristics, 19, 4, 697-709 (2013) |
| [13] | Castillo, I.; Kampas, F. J.; Pinter, J. D., Solving circle packing problems by global optimization: Numerical results and industrial applications, European Journal of Operational Research, 191, 3, 786-802 (2008) · Zbl 1156.90013 |
| [14] | Fu, Z.; Huang, W.; Lu, Z., Iterated tabu search for the circular open dimension problem, European Journal of Operational Research, 225, 2, 236-243 (2013) · Zbl 1292.90164 |
| [15] | George, J. A.; George, J. M.; Lamer, B. W., Packing different-sized circles into a rectangular container, European Journal of Operational Research, 84, 3, 693-712 (1995) · Zbl 0928.90077 |
| [16] | Grosso, A.; Jamali, A. R.M. J.U.; Locatelli, M.; Schoen, F., Solving the problem of packing equal and unequal circles in a circular container, Journal of Global Optimization, 47, 1, 63-81 (2010) · Zbl 1190.90161 |
| [17] | Hansen, P.; Mladenović, N.; Brimberg, J.; Perez, J. A.M., Variable neighborhood search, (Gendreau, M.; Potvin, J.-Y., Handbook of Metaheuristics. Handbook of Metaheuristics, International Series in Operations Research & Management Science, 146 (2010), Springer), 61-86 · Zbl 1198.90002 |
| [18] | He, K.; Huang, M. L.; Yang, C. K., An action-space-based global optimization algorithm for packing circles into a square container, Computers & Operations Research, 58, 1, 67-74 (2015) · Zbl 1348.90542 |
| [19] | He, Y.; Wu, Y., Packing non-identical circles within a rectangle with open length, Journal of Global Optimization, 56, 3, 1187-1215 (2013) · Zbl 1272.90069 |
| [20] | Hertz, A.; Plumettaz, M.; Zufferey, N., Variable space search for graph coloring, Discrete Applied Mathematics, 156, 13, 2551-2560 (2008) · Zbl 1213.05085 |
| [21] | Hertz, A.; Plumettaz, M.; Zufferey, N., Corrigendum to “variable space search for graph coloring”, Discrete Applied Mathematics, 157, 7, 1335-1336 (2009) · Zbl 1237.05076 |
| [22] | Hifi, M.; M’Hallah, R., A literature review on circle and sphere packing problems: models and methodologies, Advances in Operational Research, 150624, 22 (2009) · Zbl 1198.90337 |
| [23] | Hifi, M.; M’Hallah, R., Adaptive and restarting techniques-based algorithms for circular packing problems, Computational Optimization and Applications, 39, 1, 17-35 (2008) · Zbl 1147.90390 |
| [24] | Hifi, M.; M’Hallah, R., A dynamic adaptive local search algorithm for the circular packing problem, European Journal of Operational Research, 183, 3, 1280-1294 (2008) · Zbl 1135.90037 |
| [25] | Huang, W. Q.; Fu, Z. H.; Xu, R. C., Tabu search algorithm combined with global perturbation for packing arbitrary sized circles into a circular container, Science China-Information Sciences, 56, 9 (2013) |
| [26] | Huang, W. Q.; Li, Y.; Akeb, H.; Li, C. M., Greedy algorithms for packing unequal circles into a rectangular container, Journal of the Operational Research Society, 56, 5, 539-548 (2005) · Zbl 1095.90095 |
| [27] | Huang, W. Q.; Li, Y.; Li, C. M.; Xu, R. C., New heuristics for packing unequal circles into a circular container, Computers & Operations Research, 33, 8, 2125-2142 (2006) · Zbl 1086.90063 |
| [28] | Huang, W. Q.; Li, Y.; Xu, R. C., A quasi-physical method of solving packing problem, Proceedings of the 4th metaheuristics international conference (MIC’2001), Porto, Portugal (2001) |
| [29] | Huang, W. Q.; Zhan, S. H., A quasi-physical method of solving packing problems, Mathematical Reviews, American Mathematical Society, 82h, 52002 (1982) |
| [30] | Kallrath, J., Cutting circles and polygons from area-minimizing rectangles, Journal of Global Optimization, 43, 2-3, 299-328 (2009) · Zbl 1169.90434 |
| [31] | Kochetov, Y.; Kononova, P.; Paschenko, M., Formulation space search approach for the teacher/class timetabling problem, Yugoslav Journal of Operations Research, 18, 1, 1-11 (2008) · Zbl 1235.90064 |
| [32] | Kubach, T.; Bortfeldt, A.; Gehring, H., Parallel greedy algorithms for packing unequal circles into a strip or a rectangle, Central European Journal of Operations Research, 17, 4, 461-477 (2009) · Zbl 1204.90083 |
| [33] | Liu, J.; Xue, S.; Liu, Z.; Xu, D., An improved energy landscape paving algorithm for the problem of packing circles into a larger containing circle, Computers & Industrial Engineering, 57, 3, 1144-1149 (2009) |
| [34] | Liu, J.; Yao, Y.; Zheng, Y.; Geng, H.; Zhou, G., An effective hybrid algorithm for the circles and spheres packing problems, Combinatorial optimization and its applications. Combinatorial optimization and its applications, Lecture Notes in Computer Science volume 5573, 2009, 135-144 (2009) · Zbl 1246.52020 |
| [35] | López, C. O.; Beasley, J. E., A heuristic for the circle packing problem with a variety of containers, European Journal of Operational Research, 214, 3, 512-525 (2011) · Zbl 1226.90088 |
| [36] | López, C. O.; Beasley, J. E., Packing unequal circles using formulation space search, Computers & Operations Research, 40, 5, 1276-1288 (2013) · Zbl 1352.90085 |
| [37] | López, C. O.; Beasley, J. E., A note on solving MINLP’s using formulation space search, Optimization Letters, 8, 3, 1167-1182 (2014) · Zbl 1292.90213 |
| [38] | Lu, Z. P.; Huang, W. Q., PERM for solving circle packing problem, Computers & Operations Research, 35, 5, 1742-1755 (2008) · Zbl 1211.90198 |
| [40] | Mladenović, N.; Plastria, F.; Urošević, D., Reformulation descent applied to circle packing problems, Computers & Operations Research, 32, 9, 2419-2434 (2005) · Zbl 1066.90092 |
| [41] | Mladenović, N.; Plastria, F.; Urošević, D., Formulation space search for circle packing problems, Engineering stochastic local search algorithms. designing, implementing and analyzing effective heuristics. Engineering stochastic local search algorithms. designing, implementing and analyzing effective heuristics, Lecture Notes in Computer Science volume 4638, 212-216 (2007) · Zbl 1134.90477 |
| [43] | Pardo, E. G.; Mladenović, N.; Pantrigo, J. J.; Duarte, A., Variable formulation search for the cutwidth minimization problem, Applied Soft Computing, 13, 5, 2242-2252 (2013) |
| [45] | Stoyan, Y.; Yaskov, G., Packing unequal circles into a strip of minimal length with a jump algorithm, Optimization Letters, 8, 3, 949-970 (2014) · Zbl 1292.90259 |
| [46] | Stoyan, Y. G.; Yaskov, G., A mathematical model and a solution method for the problem of placing various-sized circles into a strip, European Journal of Operational Research, 156, 3, 590-600 (2004) · Zbl 1056.90018 |
| [47] | Szabó, P. G.; Markót, M. C.; Csendes, T.; Specht, E.; Casado, L. G.; Garcia, I., New approaches to circle packing in a square: with program codes, Springer Optimization and its Applications, 6 (2007) · Zbl 1128.52012 |
| [48] | Wang, H.; Huang, W.; Zhang, Q.; Xu, D., An improved algorithm for the packing of unequal circles within a larger containing circle, European Journal of Operational Research, 141, 2, 440-453 (2002) · Zbl 1081.90593 |
| [49] | Zhang, D.; Deng, A., An effective hybrid algorithm for the problem of packing circles into a larger containing circle, Computers & Operations Research, 32, 8, 1941-1951 (2005) · Zbl 1068.90095 |
| [50] | Zhang, D.; Huang, W., A simulated annealing algorithm for the circles packing problem, (Bubak, M.; van Albada, G. D.; Slott, P. M.A.; Dongarra, J. J., Computational science - ICCS 2004. Computational science - ICCS 2004, Lecture Notes in Computer Science, 3036 (2004)), 206-214 · Zbl 1095.90591 |
| [51] | Zhang, D.; Liu, Y.; Chen, S., Packing different-sized circles into a rectangular container using simulated annealing algorithm, International Journal of Computational Intelligence, 1, 1, 1-12 (2004) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
