Comparison of Algorithms for Nonlinear Integer Optimization: Application to Monitoring Network Design
Publication: Journal of Environmental Engineering
Volume 122, Issue 6
Abstract
This paper presents an empirical comparison of eight heuristic algorithms for solving nonlinear integer optimization problems. The algorithms are first applied to a simple network location problem to assess their relative performance. The best performing algorithms are then applied to a more complex test problem involving an irregular correlation surface and partitioned spatial domain, typical of a ground-water monitoring network design application. Simulated annealing and TABU search exhibit superior performance among the six heuristic methods and two supplemental nonlinear integer optimization solvers that were tested.
Get full access to this article
View all available purchase options and get full access to this article.
References
1.
Aarts, E., and Korst, J. (1989). Simulated annealing and Boltzmann machines: a stochastic approach to combinatorial optimization and neural computing . John Wiley & Sons, Inc., New York, N.Y.
2.
Cressie, N. A. C. (1993). Statistics for spatial data . John Wiley & Sons, Inc., New York, N.Y.
3.
de Marsily, G. (1989). Quantitative hydrogeology: groundwater hydrology for engineers . Academic Press, Inc., Orlando, Fla.
4.
de Werra, D., and Hertz, A.(1989). “Tabu search techniques: a tutorial and an application to neural networks.”OR Spektrum, 11, 131–141.
5.
Dougherty, D. E., and Marryott, R. A.(1991). “Optimal groundwater management: 1. simulated annealing.”Water Resour. Res., 27(10), 2493–2508.
6.
Eglese, R. W.(1990). “Simulated annealing: a tool for operational research.”European J. of Operational Res., 46, 271–281.
7.
Glover, F., and Greenberg, H. J.(1989). “New approaches for heuristic search: a bilateral linkage with artificial intelligence.”European J. Operations Res., 39, 119–130.
8.
Glover, F.(1993). “A user's guide to tabu search.”Ann. of Operations Res., 41, 3–28.
9.
Glover, F.(1990). “Tabu search: a tutorial.”Interfaces, 20, 74–94.
10.
Journel, A. G., and Huijbregts, C. J. (1978). Mining geostatistics . Academic Press, London, England.
11.
Kirkpatrick, S., Gelatt, C. D., and Vecchi, M. P.(1983). “Optimization by simulated annealing.”Science, 220(4598), 671–680.
12.
Lee, Y.-M. (1995). “Entropy/kriging-based formulations for ground water monitoring network design,” PhD dissertation, The Johns Hopkins University, Baltimore, Md.
13.
Marryott, R. A., Dougherty, D. E., and Stollar, R. L.(1993). “Optimal groundwater management: 2. application of simulated annealing to a field-scale contamination site.”Water Resour. Res., 29(4), 847–860.
14.
Mirchandani, P. B. (1990). “The p-median problem and generalizations.”Discrete location theory, P. B. Mirchandani and R. L. Francis, eds., John Wiley & Sons, Inc., New York, N.Y., 55–118.
15.
Press, W. H., Flannery, B. P., Teukolsky, S. A., and Vetterling, W. T. (1989). Numerical recipes, the art of scientific computing . Cambridge Univ. Press, New York, N.Y.
16.
Reeves, C. R., ed. (1993). Modern techniques for combinatorial problems . Blackwell Scientific Publications, London, England.
17.
Rouhani, S.(1986). “Resilience of a statistical sampling scheme.”J. of Hydrol., 89, 1–11.
18.
Rouhani, S., and Hall, T. J.(1988). “Geostatistical scheme for groundwater sampling.”J. of Hydrol., 103, 85–102.
19.
Rouhani, S.(1985). “Variance reduction analysis.”Water Resour. Res., 21(6), 837–846.
20.
Sacks, J., and Schiller, S. (1988). “Spatial designs.”Statistical design theory and related topics IV 2, S. S. Gupts and J. O. Berger, eds., Springer-Verlag, New York, N.Y., 385–399.
21.
Vignaux, G. A., and Michalewicz, Z.(1991). “A genetic algorithm for linear transportation problem.”IEEE Trans. on Syst., Man, and Cybernetics, 20(2), 445–452.
22.
Weber, D., and Englund, E.(1992). “Evaluation and comparison of spatial interpolators.”Math. Geology, 24(4), 381–391.
Information & Authors
Information
Published In
Journal of Environmental Engineering
Volume 122 • Issue 6 • June 1996
Pages: 524 - 531
Copyright
Copyright © 1996 American Society of Civil Engineers.
History
Published online: Jun 1, 1996
Published in print: Jun 1996
Authors
Metrics & Citations
Metrics
Citations
Download citation
If you have the appropriate software installed, you can download article citation data to the citation manager of your choice. Simply select your manager software from the list below and click Download.