×

Approximate solutions of continuous dispersion problems. (English) Zbl 1114.90066

Summary: The problem of positioning \(p\) points so as to maximize the minimum distance between them has been studied in both location theory (as the continuous \(p\)-dispersion problem) and the design of computer experiments (as the maximin distance design problem). This problem can be formulated as a nonlinear program, either exactly or approximately. We consider formulations of both types and demonstrate that, as \(p\) increases, it becomes dramatically more expensive to compute solutions of the exact formulation than to compute solutions of the approximate formulation.

MSC:

90B85 Continuous location
90C30 Nonlinear programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Boll, D.W., J. Donovan, R.L. Graham, and B.D. Lubachevsky. (2000). ”Improving Dense Packings of Equal Disks in a Square.” Electronic Journal of Combinatorics R46. · Zbl 0962.52004
[2] Booker, A.J. (1996). ”Case Studies in Design and Analysis of Computer Experiments.” In Proceedings of the Section on Physical and Engineering Sciences. American Statistical Association, pp. 244–248.
[3] Dimnaku, A. (2000). ”Approximate Solutions of Continuous p-Dispersion Using Non-linear Programming.” Master’s thesis, College of William & Mary. This research project was completed in partial fulfillment of the requirements for a master’s degree in Computational Operations Research.
[4] Drezner, Z. and E. Erkut. (1995). ”Solving the Continuous p-Dispersion Problem Using Non-linear Programming.” Journal of the Operational Research Society 46, 516–520. · Zbl 0830.90088
[5] Erkut, E., Y. Ülküsal, and O. Yeniçerioğlu. (1994). ”A Computational Comparison of p-Dispersion Heuristics.” Computers and Operations Research 21, 1103–1113. · Zbl 0814.90059 · doi:10.1016/0305-0548(94)90041-8
[6] Fourer, R., D.M. Gay, and B.W. Kernighan. (1993). AMPL: A Modeling Language for Mathematical Programming. Duxbury Press, Pacific Grove, CA. · Zbl 0701.90062
[7] Gill, P.E., M.A. Saunders, and W. Murray. (1997). ”SNOPT: An SQP Algorithm for Large-scale Constrained Optimization.” Report NA 97-2, Department of Mathematics, University of California at San Diego. · Zbl 1210.90176
[8] Gockenbach, M.S. and A.J. Kearsley. (1999). ”Optimal Signal Sets for Non-Gaussian Detectors.” SIAM Journal on Optimization 9, 316–326. · Zbl 1032.90531 · doi:10.1137/S1052623496306553
[9] Johnson, M.E., L.M. Moore, and D. Ylvisaker. (1990). ”Minimax and Maximin Distance Designs.” Journal of Statistical Inference and Planning 26, 131–148. · doi:10.1016/0378-3758(90)90122-B
[10] Koehler, J.R. and A.B. Owen. (1996). ”Computer Experiments.” In S. Ghosh and C.R. Rao (eds.), Handbook of Statistics, Vol. 13, Elsevier Science, New York, pp. 261–308. · Zbl 0919.62089
[11] Locatelli, M. and U. Raber. (1998). ”Packing Equal Circles in a Square: I. Solution Properties.” Unpublished manuscript. · Zbl 1019.90033
[12] Locatelli, M. and U. Raber. (2002). ”Packing Equal Circles in a Square: II. A Deterministic Global Optimization Approach.” Discrete Applied Mathematics (to appear). · Zbl 1019.90033
[13] McKay, M., R. Beckman, and W. Conover. (1979). ”A Comparison of Three Methods for Selecting Values of Input Variables in the Analysis of Output from a Computer Code.” Technometrics 21, 239–245. · Zbl 0415.62011 · doi:10.2307/1268522
[14] Mittelmann, H.D. and P. Spellucci. (2003). ”Decision Tree for Optimization Software.” World Wide Web, http://plato-asu.edu/guide.html.
[15] Moré, J.J. and S.J. Wright. (1993). Optimization Software Guide. Society for Industrial and Applied Mathematics, Philadelphia. See http://www-fp.mcs.anl.gov/otc/Guide/ SoftwareGuide for updated information. · Zbl 0830.65050
[16] Morris, M.D. and T.J. Mitchell. (1995). ”Exploratory Designs for Computational Experiments.” Journal of Statistical Inference and Planning 43, 381–402. · Zbl 0813.62065 · doi:10.1016/0378-3758(94)00035-T
[17] Owen, A.B. (1992). ”Orthogonal Arrays for Computer Experiments, Integration and Visualization.” Statistica Sinica 2, 439–452. · Zbl 0822.62064
[18] Owen, A.B. (1994). ”Lattice Sampling Revisited: Monte Carlo Variance of Means over Randomized Orthogonal Arrays.” Annals of Statistics 22, 930–945. · Zbl 0807.62059 · doi:10.1214/aos/1176325504
[19] Sacks, J., W.J. Welch, T.J. Mitchell, and H.P. Wynn. (1989). ”Design and Analysis of Computer Experiments.” Statistical Science 4, 409–435. Includes discussion. · Zbl 0955.62619 · doi:10.1214/ss/1177012413
[20] Tang, B. (1993). ”Orthogonal Array-based Latin Hypercubes.” Journal of the American Statistical Association 88, 1392–1397. · Zbl 0792.62066 · doi:10.2307/2291282
[21] Trosset, M.W. (1999). ”Approximate Maximin Distance Designs.” In Proceedings of the Section on Physical and Engineering Sciences. American Statistical Association, pp. 223–227.
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.