Perturbation-Based Thresholding Search for Packing Equal Circles and Spheres

References

• Addis B, Locatelli M, Schoen F (2008) Disk packing in a square: A new global optimization approach. INFORMS J. Comput. 20(4):516–524.Link, Google Scholar
• Akiyama J, Mochizuki R, Mutoh N, Nakamura G (2002) Maximin distance for n points in a unit square or a unit circle. Akiyama J, Kano M, eds. Proc. Japanese Conf. on Discrete and Comput. Geometry (Springer, Berlin), 9–13.Google Scholar
• Amore P, Morales T (2022) Efficient algorithms for the dense packing of congruent circles inside a square. Discrete Comput. Geometry, ePub ahead of print August 18, https://doi.org/10.1007/s00454-022-00425-5.Crossref, Google Scholar
• Bagattini F, Schoen F, Tigli L (2019) Clustering methods for large scale geometrical global optimization. Optim. Methods Software 34(5):1099–1122.Crossref, Google Scholar
• Bierlaire M, Thémans M, Zufferey N (2010) A heuristic for nonlinear global optimization. INFORMS J. Comput. 22(1):59–70.Link, Google Scholar
• Birgin EG, Sobral F (2008) Minimizing the object dimensions in circle and sphere packing problems. Comput. Oper. Res. 35(7):2357–2375.Crossref, Google Scholar
• Boll DW, Donovan J, Graham RL, Lubachevsky BD (2000) Improving dense packings of equal disks in a square. Electronic J. Combinatorial 7:R46–R46.Crossref, Google Scholar
• Casado LG, García I, Szabo PG, Csendes T (1998) Packing equal circles packing in square. II. New results for up to 100 circles using the TAMSASS-PECS algorithm. Giannessi F, Pardalos PM, Rapcsák T, eds. Optimization Theory: Recent Developments from Mátraháza, Applied Optimization Series, vol. 59 (Kluwer Academic Publishers, Dordrecht, Netherlands), 207–224.Google Scholar
• Castillo I, Kampas FJ, Pintér JD (2008) Solving circle packing problems by global optimization: Numerical results and industrial applications. Eur. J. Oper. Res. 191(3):786–802.Crossref, Google Scholar
• Clare B, Kepert D (1991) The optimal packing of circles on a sphere. J. Math. Chemistry 6(1):325–349.Crossref, Google Scholar
• Costa A (2013) Valid constraints for the point packing in a square problem. Discrete Appl. Math. 161(18):2901–2909.Crossref, Google Scholar
• Costa A, Hansen P, Liberti L (2013) On the impact of symmetry-breaking constraints on spatial branch-and-bound for circle packing in a square. Discrete Appl. Math. 161(1–2):96–106.Crossref, Google Scholar
• Dai Z, Xu K, Ornik M (2021) Repulsion-based p-dispersion with distance constraints in non-convex polygons. Ann. Oper. Res. 307:75–91.Crossref, Google Scholar
• Demaine ED, Fekete SP, Lang RJ (2010) Circle packing for origami design is hard. Preprint, submitted September 20, https://arxiv.org/abs/1008.1224v2.Google Scholar
• Dimnaku A, Kincaid R, Trosset MW (2005) Approximate solutions of continuous dispersion problems. Ann. Oper. Res. 136(1):65–80.Crossref, Google Scholar
• Doye JP, Leary RH, Locatelli M, Schoen F (2004) Global optimization of Morse clusters by potential energy transformations. INFORMS J. Comput. 16(4):371–379.Link, Google Scholar
• Drezner Z, Erkut E (1995) Solving the continuous p-dispersion problem using non-linear programming. J. Oper. Res. Soc. 46:516–520.Crossref, Google Scholar
• Dueck G, Scheuer T (1990) Threshold accepting: A general purpose optimization algorithm appearing superior to simulated annealing. J. Comput. Phys. 90(1):161–175.Crossref, Google Scholar
• Fiacco AV, McCormick GP (1964) Computational algorithm for the sequential unconstrained minimization technique for nonlinear programming. Management Sci. 10(4):601–617.Link, Google Scholar
• Gensane T (2004) Dense packings of equal spheres in a cube. Electronic J. Combinatorial 11(1):R33.Crossref, Google Scholar
• Goldberg M (1970) The packing of equal circles in a square. Math. Magazine 43(1):24–30.Crossref, Google Scholar
• Goldberg M (1971) On the densest packing of equal spheres in a cube. Math. Magazine 44(4):199–208.Crossref, Google Scholar
• Graham R, Lubachevsky B (1996) Repeated patterns of dense packings of equal disks in a square. Electronic J. Combinatorial 3(R16):2.Google Scholar
• Grosso A, Jamali A, Locatelli M, Schoen F (2010) Solving the problem of packing equal and unequal circles in a circular container. J. Global Optim. 47(1):63–81.Crossref, Google Scholar
• Hager WW, Zhang H (2005) A new conjugate gradient method with guaranteed descent and an efficient line search. SIAM J. Optim. 16(1):170–192.Crossref, Google Scholar
• Hardin D, Saff E (2005) Minimal riesz energy point configurations for rectifiable d-dimensional manifolds. Adv. Math. 193(1):174–204.Crossref, Google Scholar
• Hifi M, Yousef L (2019) A local search-based method for sphere packing problems. Eur. J. Oper. Res. 274(2):482–500.Crossref, Google Scholar
• Hoos HH, Stützle T (2000) Local search algorithms for SAT: An empirical evaluation. J. Automated Reasoning 24(4):421–481.Crossref, Google Scholar
• Huang W, Ye T (2010) Greedy vacancy search algorithm for packing equal circles in a square. Oper. Res. Lett. 38(5):378–382.Crossref, Google Scholar
• Huang W, Ye T (2011) Global optimization method for finding dense packings of equal circles in a circle. Eur. J. Oper. Res. 210(3):474–481.Crossref, Google Scholar
• Hujter M (1999) Some numerical problems in discrete geometry. Comput. Math. Appl. 38(9–10):175–178.Crossref, Google Scholar
• Joós A (2009) On the packing of fourteen congruent spheres in a cube. Geometry Dedicata 140(1):49–80.Crossref, Google Scholar
• Kolossváry I, Bowers KJ (2010) Global optimization of additive potential energy functions: Predicting binary Lennard-Jones clusters. Phys. Rev. E 82(5):056711.Crossref, Google Scholar
• Lai X, Hao JK, Xiao R, Glover F (2022a) Circlepacking Version v2022.0004. Accessed January 28, 2023, https://github.com/INFORMSJoC/2022.0004.Google Scholar
• Lai X, Hao JK, Yue D, Lü Z, Fu ZH (2022b) Iterated dynamic thresholding search for packing equal circles into a circular container. Eur. J. Oper. Res. 299(1):137–153.Crossref, Google Scholar
• Leary RH (2000) Global optimization on funneling landscapes. J. Global Optim. 18(4):367–383.Crossref, Google Scholar
• Liu DC, Nocedal J (1989) On the limited memory BFGS method for large scale optimization. Math. Programming 45(1):503–528.Crossref, Google Scholar
• Locatelli M, Raber U (2002) Packing equal circles in a square: A deterministic global optimization approach. Discrete Appl. Math. 122(1–3):139–166.Crossref, Google Scholar
• López CO, Beasley JE (2011) A heuristic for the circle packing problem with a variety of containers. Eur. J. Oper. Res. 214(3):512–525.Crossref, Google Scholar
• Maranas CD, Floudas CA, Pardalos PM (1995) New results in the packing of equal circles in a square. Discrete Math. 142(1–3):287–293.Crossref, Google Scholar
• Markót MC (2021) Improved interval methods for solving circle packing problems in the unit square. J. Global Optim. 81(3):773–803.Crossref, Google Scholar
• Markót MC, Csendes T (2005) A new verified optimization technique for the “packing circles in a unit square” problems. SIAM J. Optim. 16(1):193–219.Crossref, Google Scholar
• Martínez L, Andrade R, Birgin EG, Martínez JM (2009) PACKMOL: A package for building initial configurations for molecular dynamics simulations. J. Comput. Chemistry 30(13):2157–2164.Crossref, Google Scholar
• M’Hallah R, Alkandari A (2012) Packing unit spheres into a cube using VNS. Electronic Notes Discrete Math. 39:201–208.Crossref, Google Scholar
• Mladenović N, Plastria F, Urošević D (2005) Reformulation descent applied to circle packing problems. Comput. Oper. Res. 32(9):2419–2434.Crossref, Google Scholar
• Moscato P, Fontanari JF (1990) Stochastic vs. deterministic update in simulated annealing. Phys. Lett. A 146(4):204–208.Crossref, Google Scholar
• Nurmela KJ, Östergård PR (1997) Packing up to 50 equal circles in a square. Discrete Comput. Geometry 18(1):111–120.Crossref, Google Scholar
• Nurmela KJ, Ostergard PRJ (1999) More optimal packings of equal circles in a square. Discrete Comput. Geometry 22(3):439–457.Crossref, Google Scholar
• Pei J, Dražić Z, Dražić M, Mladenović N, Pardalos PM (2019) Continuous variable neighborhood search (C-VNS) for solving systems of nonlinear equations. INFORMS J. Comput. 31(2):235–250.Link, Google Scholar
• Pintér JD, Kampas FJ, Castillo I (2018) Globally optimized packings of non-uniform size spheres in Rd: A computational study. Optim. Lett. 12(3):585–613.Crossref, Google Scholar
• Schaer J (1965) The densest packing of 9 circles in a square. Canadian Math. Bull. 8(3):273–277.Crossref, Google Scholar
• Schaer J (1966) On the densest packing of spheres in a cube. Canadian Math. Bull. 9(3):265–270.Crossref, Google Scholar
• Schwartz B (1970) Separating points in a square. J. Recreational Math. 3:195–204.Google Scholar
• Specht E (2021) Packomania website. Accessed October 28, 2021, http://www.packomania.com.Google Scholar
• Stoyan Y, Yaskov G, Romanova T, Litvinchev I, Yakovlev S, Cantú JMV (2020) Optimized packing multidimensional hyperspheres: A unified approach. Math. Biosci. Engrg. 17(6):6601–6630.Crossref, Google Scholar
• Szabó PG, Markót MC, Csendes T, Specht E, Casado LG, García I (2007) New Approaches to Circle Packing in a Square: With Program Codes, vol. 6 of Optimization and Its Applications (Springer, Berlin).Google Scholar
• Szabó PG, Specht E (2007) Packing up to 200 equal circles in a square. Models and Algorithms for Global Optimization, vol. 4 of Optimization and Its Applications (Springer, Berlin), 141–156 (Springer).Crossref, Google Scholar
• Van Dam ER, Husslage B, Den Hertog D, Melissen H (2007) Maximin Latin hypercube designs in two dimensions. Oper. Res. 55(1):158–169.Link, Google Scholar
• Wales DJ, Doye JP (1997) Global optimization by basin-hopping and the lowest energy structures of Lennard-Jones clusters containing up to 110 atoms. J. Phys. Chemistry A 101(28):5111–5116.Crossref, Google Scholar
• Weaire D, Aste T (2008) The Pursuit of Perfect Packing (CRC Press, Boca Raton, FL).Crossref, Google Scholar
• Wengerodt G (1983) Die dichteste packung von 16 kreisen in einem quadrat. Contributions Algebra Geometry 16:173–190.Google Scholar
• Wengerodt G (1987) Die dichteste packung von 14 kreisen in einem quadrat. Contributions Algebra Geometry 25:25–46.Google Scholar
• Wengerodt G, Kirchner K (1987) Die dichteste packung von 36 kreisen in einem quadrat. Contributions Algebra Geometry 25:147–160.Google Scholar