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)
Reformulation descent applied to circle packing problems. (English) Zbl 1066.90092
Summary: Several years ago classical Euclidean geometry problems of densest packing of circles in the plane have been formulated as nonconvex optimization problems, allowing to find heuristic solutions by using any available NLP solver. In this paper we try to improve this procedure. The faster NLP solvers use first order information only, so stop in a stationary point. A simple switch from Cartesian coordinates to polar or vice versa, may destroy this stationarity and allow the solver to descend further. Such formulation switches may of course be iterated. For densest packing of equal circles into a unit circle, this simple feature turns out to yield results close to the best known, while beating second order methods by a time-factor well over 100. This technique is formalized as a general reformulation descent (RD) heuristic, which iterates among several formulations of the same problem until local searches obtain no further improvement. We also briefly discuss how RD might be used within other metaheuristic schemes.

90C26Nonconvex programming, global optimization
90C59Approximation methods and heuristics
Full Text: DOI
[1] Gardner M. Fractal music, hypercards and more ..., (Mathematical recreations from Scientific American). New York: W.H. Freeman and Co.; 1992. p. 156, Fig. 68.
[2] Kravitz, S.: Packing cylinders into cylindrical containers. Mathematics magazine 40, 65-70 (1967) · Zbl 0192.28801
[3] Pirl, U.: Der mindestabstand von n in der einheitskreisscheibe gelegenen punkten. Mathematishe nachrichten 40, 111-124 (1969) · Zbl 0182.25102
[4] Drezner, Z.; Erkut, E.: On the continuous p-dispersion problem. Journal of the operational research society 46, 516-520 (1995) · Zbl 0830.90088
[5] Graham, R. L.; Lubaschevski, B. D.; Nurmela, K. J. Ö; Stergård, P. R.: Dense packings of congruent circles in a circle. Discrete mathematics 181, 139-154 (1998) · Zbl 0901.52017
[6] Minos, Stanford Business Software Inc., website http://www.sbsi-sol-optimize.com/products_minos5_5.htm
[7] Murtagh BA, Saunders MA. MINOS user’s guide, Report SOL 77-9, Department of Operations Research, Stanford University, CA, 1997.
[8] Murtagh, B. A.; Saunders, M. A.: Large scale linearly constrained optimization. Mathematical programming 14, 41-72 (1978) · Zbl 0383.90074
[9] Gill, P. E.; Murray, W.; Wright, M. H.: Practical optimization. (1981) · Zbl 0503.90062
[10] Andrei, N.: Penalty-barrier algorithms for nonlinear optimization: preliminary computational results. Studies in informatics and control 7, 15-36 (1998)
[11] Specht E. The best known packings of equal circles in the unit circle (up to N = 500), website (last update used dated 28 oct 2002) http://hydra.nat.uni-magdeburg.de/packing/cci/cci.html
[12] Mladenović N, Plastria F, Urošević D. Reformulation descent for packing circles into the unit circle. Cahiers du GERAD, G-2003-68, Montreal, October 2003. http://www.gerad.ca/fichiers/cahiers/G-2003-68.pdf
[13] Baum EB. Toward practical ’neural’ computation for combinatorial optimization problems. In: Denker J, editor. Neural networks for computing. Boston: American Institute of Physics; 1986.
[14] Boese, K. D.; Kahng, A. B.; Muddu, S.: A new adaptive multi-start technique for combinatorial global optimization. Operations research letters 16, 101-113 (1994) · Zbl 0812.90126
[15] Hansen, P.; Mladenović, N.: Variable neighborhood search for the p-median. Location sciences 5, 207-226 (1997) · Zbl 0928.90043
[16] Hansen P, Mladenović N. Variable neighborhood search. In: Glover F, Kochenberger G, editors. Handbook of Metaheuristics. Dordrecht: Kluwer Academic Publisher; 2003. p. 145--84. · Zbl 1102.90371
[17] Glover F, Kochenberger G, editor. Handbook of metaheuristics. Dordrecht: Kluwer Academic Publisher; 2003. · Zbl 1058.90002
[18] Mladenović, N.; Hansen, P.: Variable neighborhood search. Computers and operations research 24, 1097-1100 (1997) · Zbl 0889.90119
[19] Polyak, R.: Modified barrier functions (theory and methods). Mathematical programming 54, 177-222 (1992) · Zbl 0756.90085