Solving circle packing problems by global optimization: numerical results and industrial applications. (English) Zbl 1156.90013
Summary: A (general) circle packing is an optimized arrangement of \(N\) arbitrary sized circles inside a container (e.g., a rectangle or a circle) such that no two circles overlap. In this paper, we present several circle packing problems, review their industrial applications, and some exact and heuristic strategies for their solution. We also present illustrative numerical results using ‘generic’ global optimization software packages. Our work highlights the relevance of global optimization in solving circle packing problems, and points towards the necessary advancements in both theory and numerical practice.
References:
| [1] | Adickes, M. D.; Billo, R. E.; Norman, B. A.; Banerjee, S.; Nnaji, B. O.; Rajgopal, J., Optimization of indoor wireless communication network layouts, IIE Transactions, 34, 823-836 (2002) |
| [2] | Anjos, M. F.; Vannelli, A., An attractor-repeller approach to floorplanning, Mathematical Methods of Operations Research, 56, 3-27 (2002) · Zbl 1023.90036 |
| [3] | Birgin, E. G.; Martinez, J. M.; Ronconi, D. P., Optimizing the packing of cylinders into a rectangular container: A nonlinear approach, European Journal of Operational Research, 160, 19-33 (2005) · Zbl 1067.90133 |
| [4] | Boll, D. W.; Donovan, J.; Graham, R. L.; Lubachevsky, B. D., Improving dense packings of equal disks in a square, The Electronic Journal of Combinatorics, 7, R46 (2000) · Zbl 0962.52004 |
| [5] | Buffa, E. S.; Armour, G. C.; Vollmann, T. E., Allocating facilities with CRAFT, Harvard Business Review, 42, 136-158 (1964) |
| [6] | Castillo, I.; Sim, T., A spring-embedding approach for the facility layout problem, Journal of the Operational Research Society, 55, 73-81 (2004) · Zbl 1095.90069 |
| [7] | Correia, M. H.; Oliveira, J. F.; Ferreira, J. S., Cylinder packing by simulated annealing, Pesquisa Operacional, 20, 269-286 (2000) · Zbl 1181.90231 |
| [8] | Correia, M. H.; Oliveira, J. F.; Ferreira, J. S., A new upper bound for the cylinder packing problem, International Transactions in Operational Research, 8, 571-583 (2001) · Zbl 0992.90056 |
| [9] | Cui, Y., Generating optimal t-shape cutting patterns for circular blanks, Computers & Operations Research, 32, 143-152 (2005) · Zbl 1076.90560 |
| [10] | Dowsland, K. A., Optimising the palletisation of cylinders in cases, OR Spectrum, 13, 204-212 (1991) · Zbl 0729.90912 |
| [11] | Dowsland, K. A.; Dowsland, W. B., Packing problems, European Journal of Operational Research, 56, 2-14 (1992) · Zbl 0825.90355 |
| [12] | Drezner, Z., Discon: A new method for the layout problem, Operations Research, 28, 1375-1384 (1980) · Zbl 0447.90025 |
| [13] | Drezner, Z.; Erkut, E., Solving the continuous p-dispersion problem using non-linear programming, Journal of the Operational Research Society, 46, 516-520 (1995) · Zbl 0830.90088 |
| [14] | Dyckhoff, H., A typology of cutting and packing problems, European Journal of Operational Research, 44, 145-159 (1990) · Zbl 0684.90076 |
| [15] | Erkut, E., The discrete p-dispersion problem, European Journal of Operational Research, 46, 48-60 (1990) · Zbl 0702.90050 |
| [16] | Fraser, H. J.; George, J. A., Integrated container loading software for pulp and paper industry, European Journal of Operational Research, 77, 466-474 (1994) · Zbl 0800.90656 |
| [17] | George, J. A., Multiple container packing: A case study of pipe packing, Journal of the Operational Research Society, 47, 1098-1109 (1996) · Zbl 0869.90059 |
| [18] | George, J. A.; George, J. M.; Lamar, B. W., Packing different-sized circles into a rectangular container, European Journal of Operational Research, 84, 693-712 (1995) · Zbl 0928.90077 |
| [19] | Graham, R. L.; Lubachevsky, B. D.; Nurmela, K. J.; Ostergard, P. R.J., Dense packings of congruent circles in a circle, Discrete Mathematics, 181, 139-154 (1998) · Zbl 0901.52017 |
| [20] | Haessler, R. W.; Sweeney, P. E., Cutting stock problems and solution procedures, European Journal of Operational Research, 54, 141-150 (1991) · Zbl 0736.90062 |
| [21] | Hifi, M.; M’Hallah, R., Approximate algorithms for constrained circular cutting problems, Computers & Operations Research, 31, 675-694 (2004) · Zbl 1061.90095 |
| [22] | Hifi, M.; Paschos, V. T.; Zissimopoulos, V., A simulated annealing approach for the circular cutting problem, European Journal of Operational Research, 159, 430-448 (2004) · Zbl 1065.90082 |
| [23] | Huang, W.; Li, Y.; Jurkowiak, B.; Li, C. M.; Xu, R. C., A two-level search strategy for packing unequal circles into a circle container, (Proceedings of the International Conference on Principles and Practice of Constraint Programming (2003), Springer-Verlag: Springer-Verlag Ireland), 868-872 |
| [24] | Huang, W., Li, Y., Akeb, H., Li, C., forthcoming. Greedy algorithms for packing unequal circles into a rectangular container. Journal of the Operational Research Society.; Huang, W., Li, Y., Akeb, H., Li, C., forthcoming. Greedy algorithms for packing unequal circles into a rectangular container. Journal of the Operational Research Society. · Zbl 1095.90095 |
| [25] | Kravitz, S., Packing cylinders into cylindrical containers, Mathematics Magazine, 40, 65-71 (1967) · Zbl 0192.28801 |
| [26] | Lindo Systems. LINGO (release version: 9.0). Lindo Systems, Inc., 2004.; Lindo Systems. LINGO (release version: 9.0). Lindo Systems, Inc., 2004. |
| [27] | Locatelli, M.; Raber, U., Packing equal circles in a square: A deterministic global optimization approach, Discrete Applied Mathematics, 122, 139-166 (2002) · Zbl 1019.90033 |
| [28] | Lubachevsky, B. D.; Graham, R. L., Curved hexagonal packings of equal disks in a circle, Discrete & Computational Geometry, 18, 179-194 (1997) · Zbl 0881.52010 |
| [29] | Markót, M. C.; Csendes, T., A new verified optimization technique for the “packing circles in a unit square” problems, SIAM Journal on Optimization, 16, 193-219 (2005) · Zbl 1089.90045 |
| [30] | Martin, C.F. 2004. How many robots can talk at the same time? Department of Mathematics, The Royal Institute of Technology, Stockholm. <http://www.math.kth.se/optsyst/seminar/martinIII.html>; Martin, C.F. 2004. How many robots can talk at the same time? Department of Mathematics, The Royal Institute of Technology, Stockholm. <http://www.math.kth.se/optsyst/seminar/martinIII.html> |
| [31] | Melissen, J.B.M. 1997. Packing and covering with circles. Ph.D. Dissertation, Universiteit Utrecht.; Melissen, J.B.M. 1997. Packing and covering with circles. Ph.D. Dissertation, Universiteit Utrecht. · Zbl 0880.52008 |
| [32] | Mladenovic, N.; Plastria, F.; Uroevi, D., Reformulation descent applied to circle packing problems, Computers & Operations Research, 32, 2419-2434 (2005) · Zbl 1066.90092 |
| [33] | Nurmela, K. J.; Österga˙rd, P. R.J., Packing up to 50 equal circles in a square, Discrete & Computational Geometry, 18, 111-120 (1997) · Zbl 0880.90116 |
| [34] | Pintér, J. D., Global Optimization in Action (1996), Kluwer Academic Publishers · Zbl 0842.90110 |
| [35] | Pintér, J. D.; LGO, A Model Development and Solver System for Continuous Global Optimization, User Guide (2005), Pintér Consulting Services, Inc. |
| [36] | Pintér, J. D.; Kampas, F. J., Nonlinear optimization in Mathematica with MathOptimizer professional, Mathematica in Education and Research, 10, 1-18 (2005) |
| [37] | Pintér, J. D.; Kampas, F. J., MathOptimizer professional: Key features and illustrative applications, (Liberti, L.; Maculan, N., Global Optimization: From Theory to Implementation (2006), Springer Science + Business Media: Springer Science + Business Media New York), 263-280 · Zbl 1100.90046 |
| [38] | Riskin, M. D.; Bissette, K. C.; Castillo, I., A logarithmic barrier approach to solving the dashboard planning problem, INFOR, 41, 245-257 (2003) · Zbl 07682305 |
| [39] | Stoyan, Y. G.; Yaskov, G. N., Mathematical model and solution method of optimization problem of placement of rectangles and circles taking into account special constraints, International Transactions in Operational Research, 5, 45-57 (1998) · Zbl 0910.90240 |
| [40] | Stoyan, Y. G.; Yaskov, G. N., A mathematical model and a solution method for the problem of placing various-sized circles into a strip, European Journal of Operational Research, 156, 590-600 (2004) · Zbl 1056.90018 |
| [41] | Szabó, P. G.; Csendes, T.; Casado, L. G.; García, I., Equal circles packing in a square I - Problem setting and bounds for optimal solutions, (Giannessi, F.; Pardalos, P. M.; Rapcsak, T., Optimization Theory: Recent Developments from Mátraháza (2001), Kluwer: Kluwer Dordrecht) · Zbl 1014.90081 |
| [42] | Szabó, P. G.; Markót, M. C.; Csendes, T., Global optimization in geometry – circle packing into the square, (Audet, C.; Hansen, P.; Savard, G., Essays and Surveys in Global Optimization (2005), Kluwer: Kluwer Dordrecht) · Zbl 1136.90445 |
| [43] | Theodoracatos, V. E.; Grimsley, J. L., The optimal packing of arbitrarily-shaped polygons using simulated annealing and polynomial-time cooling schedules, Computer Methods in Applied Mechanics and Engineering, 125, 53-70 (1995) · Zbl 0945.90012 |
| [44] | 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, 440-453 (2002) · Zbl 1081.90593 |
| [45] | Wolfram Research. Mathematica (release version: 5.2). Wolfram Research, Inc., 2005.; Wolfram Research. Mathematica (release version: 5.2). Wolfram Research, Inc., 2005. |
| [46] | Zhang, D.; Deng, A., An effective hybrid algorithm for the problem of packing circles into a larger containing circle, Computers & Operations Research, 32, 1941-1951 (2005) · Zbl 1068.90095 |
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.
