An Efficient Optimization Model and Tabu Search–Based Global Optimization Approach for the Continuous p-Dispersion Problem

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. Discrete Comput. Geometry (Springer, Berlin), 9–13.Google Scholar
• Amore P (2023) Circle packing in regular polygons. Phys. Fluids 35(2):027130.Crossref, Google Scholar
• Baur C, Fekete SP (2001) Approximation of geometric dispersion problems. Algorithmica 30:451–470.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
• 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
• Chelouah R, Siarry P (2000) Tabu search applied to global optimization. Eur. J. Oper. Res. 123(2):256–270.Crossref, Google Scholar
• Chen J, Li B, Li Y (2019) Efficient approximations for the online dispersion problem. SIAM J. Comput. 48(2):373–416.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
• 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
• 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
• Drezner Z, Kalczynski P, Salhi S (2019) The planar multiple obnoxious facilities location problem: A Voronoi based heuristic. Omega 87:105–116.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
• Geißler B, Morsi A, Schewe L, Schmidt M (2018) Solving highly detailed gas transport MINLPs: Block separability and penalty alternating direction methods. INFORMS J. Comput. 30(2):309–323.Link, Google Scholar
• Glover F, Laguna M (1998) Tabu search. Handbook of Combinatorial Optimization (Springer, Berlin), 2093–2229.Crossref, Google Scholar
• Goldberg M (1970) The packing of equal circles in a square. Math. Magazine 43(1):24–30.Crossref, Google Scholar
• Graham R, Lubachevsky B, Nurmela K, Östergård P (1998) Dense packings of congruent circles in a circle. Discrete Math. 181(1):139–154.Crossref, 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
• Hoos HH, Stützle T (2000) Local search algorithms for SAT: An empirical evaluation. J. Automated Reason 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
• Lai X, Hao JK, Xiao R, Glover F (2023a) Perturbation based thresholding search for packing equal circles and spheres. INFORMS J. Comput. 35(4):725–746.Link, Google Scholar
• Lai X, Lin Z, Hao JK, Wu Q (2024) An efficient optimization model and tabu search-based global optimization approach for continuous p-dispersion problem. http://dx.doi.org/10.1287/ijoc.2023.0089.cd, https://github.com/INFORMSJoC/2023.0089.Google Scholar
• Lai X, Hao JK, Yue D, Lü Z, Fu ZH (2022) Iterated dynamic thresholding search for packing equal circles into a circular container. Eur. J. Oper. Res. 299(1):137–153.Crossref, Google Scholar
• Lai X, Yue D, Hao JK, Glover F, Lü Z (2023b) Iterated dynamic neighborhood search for packing equal circles on a sphere. Comput. Oper. Res. 151:106121.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
• 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
• López-Sánchez A, Sánchez-Oro J, Laguna M (2021) A new scatter search design for multiobjective combinatorial optimization with an application to facility location. INFORMS J. Comput. 33(2):629–642.Abstract, Google Scholar
• Machchhar J, Elber G (2017) Dense packing of congruent circles in free-form non-convex containers. Comput. Aided Geometric Design 52:13–27.Crossref, Google Scholar
• Melissen H (1993) Densest packings of congruent circles in an equilateral triangle. Amer. Math. Monthly 100(10):916–925.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
• Mu W, Xiong S (2017) On algorithmic construction of maximin distance designs. Comm. Statist. Simulation Comput. 46:7972–7985.Crossref, Google Scholar
• Schwartz B (1970) Separating points in a square. J. Recreational Math. 3:195–204.Google Scholar
• Specht E (2023) Packomania website. Accessed March 21, 2023, http://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, Optimization and Its Applications, vol. 6 (Springer Science & Business Media, Boston).Google Scholar
• Ugray Z, Lasdon L, Plummer J, Glover F, Kelly J, Martí R (2007) Scatter search and local NLP solvers: A multistart framework for global optimization. INFORMS J. Comput. 19(3):328–340.Link, 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
• Wang W, Li J, Wu E (2005) 2D point-in-polygon test by classifying edges into layers. Comput. Graphics 29(3):427–439.Crossref, Google Scholar
• Weaire D, Aste T (2008) The Pursuit of Perfect Packing (CRC Press, Boca Raton, FL).Crossref, Google Scholar
• Yuan Z, Zhang Y, Dragoi M, Bai X (2018) Packing circle items in an arbitrary marble slab. Proc. IOP Conf. Series Material Sci. Engrg. (IOP Publishing, Bristol, UK), 399.Google Scholar