zbMATH — the first resource for mathematics

Geometry Search for the term Geometry in any field. Queries are case-independent.
Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact.
"Topological group" Phrases (multi-words) should be set in "straight quotation marks".
au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted.
Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff.
"Quasi* map*" py: 1989 The resulting documents have publication year 1989.
so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14.
"Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic.
dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles.
py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses).
la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
any anywhere an internal document identifier
au author, editor ai internal author identifier
ti title la language
so source ab review, abstract
py publication year rv reviewer
cc MSC code ut uncontrolled term
dt document type (j: journal article; b: book; a: book article)
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.

90C26Nonconvex programming, global optimization
90B85Continuous location
Full Text: DOI
[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 · doi:10.1007/s001860200197
[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 · doi:10.1016/j.ejor.2003.06.018
[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 · emis:journals/EJC/Volume_7/Abstracts/v7i1r46.html
[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 · doi:10.1057/palgrave.jors.2601647
[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 · doi:10.1111/1475-3995.00334
[9] Cui, Y.: Generating optimal t-shape cutting patterns for circular blanks, Computers & operations research 32, 143-152 (2005) · Zbl 1076.90560 · doi:10.1016/S0305-0548(03)00208-9
[10] Dowsland, K. A.: Optimising the palletisation of cylinders in cases, OR spectrum 13, 204-212 (1991) · Zbl 0729.90912 · doi:10.1007/BF01719396
[11] Dowsland, K. A.; Dowsland, W. B.: Packing problems, European journal of operational research 56, 2-14 (1992) · Zbl 0825.90355 · doi:10.1016/0377-2217(92)90288-K
[12] Drezner, Z.: Discon: A new method for the layout problem, Operations research 28, 1375-1384 (1980) · Zbl 0447.90025 · doi:10.1287/opre.28.6.1375
[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 · doi:10.1016/0377-2217(90)90350-K
[15] Erkut, E.: The discrete p-dispersion problem, European journal of operational research 46, 48-60 (1990) · Zbl 0702.90050 · doi:10.1016/0377-2217(90)90297-O
[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 · doi:10.1016/0377-2217(94)90410-3
[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 · doi:10.1016/0377-2217(95)00032-L
[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 · doi:10.1016/S0012-365X(97)00050-2
[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 · doi:10.1016/0377-2217(91)90293-5
[21] Hifi, M.; M’hallah, R.: Approximate algorithms for constrained circular cutting problems, Computers & operations research 31, 675-694 (2004) · Zbl 1061.90095 · doi:10.1016/S0305-0548(03)00020-0
[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 · doi:10.1016/S0377-2217(03)00417-X
[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, , 868-872 (2003)
[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. · Zbl 1095.90095
[25] Kravitz, S.: Packing cylinders into cylindrical containers, Mathematics magazine 40, 65-71 (1967) · Zbl 0192.28801 · doi:10.2307/2688509
[26] 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 · doi:10.1016/S0166-218X(01)00359-6
[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 · doi:10.1007/PL00009314
[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 · doi:10.1137/S1052623403425617
[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>.
[31] 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 · doi:10.1016/j.cor.2004.03.010
[33] Nurmela, K. J.; Österga&dot, P. R. J.; Rd: 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) · Zbl 0842.90110
[35] Pintér, J. D.; Lgo: A model development and solver system for continuous global optimization, user guide, (2005)
[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, Global optimization: from theory to implementation, 263-280 (2006) · 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)
[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 · doi:10.1016/S0377-2217(03)00137-1
[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, Optimization theory: recent developments from mátraháza (2001) · Zbl 1014.90081
[42] Szabó, P. G.; Markót, M. C.; Csendes, T.: Global optimization in geometry -- circle packing into the square, Essays and surveys in global optimization (2005) · 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 · doi:10.1016/0045-7825(95)00795-3
[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 · doi:10.1016/S0377-2217(01)00241-7
[45] 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 · doi:10.1016/j.cor.2003.12.006