Abstract
Solutions to combinatorial optimization, such as p-median problems of locating facilities, frequently rely on heuristics to minimize the objective function. The minimum is sought iteratively and a criterion is needed to decide when the procedure (almost) attains it. However, pre-setting the number of iterations dominates in OR applications, which implies that the quality of the solution cannot be ascertained. In this paper we compare the methods proposed previous literate of estimating minimum, and propose some thought of it.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Beasley, J.E.: OR library: Distributing test problems by electronic mail. Journal of Operational Research Society, 41 41(11), 1067–1072 (1990)
Chiyoshi, F.Y., Galvão, R.D.: A statistical analysis of simulated annealing applied to the p-median problem. Annals of Operations Research 96, 61–74 (2000)
Dannenbring, D.G.: Procedures for estimating optimal solution values for large combinatorial problems. Management Science 23(12), 1273–1283 (1977)
Hakimi, S.L.: Optimum locations of switching centers and the absolute centers and medians of a graph. Operations Research 12(3), 450–459 (1964)
Hakimi, S.L.: Optimum Distribution of Switching Centers in a Communication Network and Some Related Graph Theoretic Problems. Operations Research 13(3), 462–475 (1965)
Kotz, S., Nadarajah, S.: Extreme value distributions, theory and applications. Imperial College Press (2000)
Levanova, T., Loresh, M.A.: Algorithm of ant system and simulated annealing for the p-median problem. Automation and Remote Control 65, 431–438 (2004)
Quenouille, M.H.: Notes on bias in estimation. Biometrika 43, 353–360 (1956)
Robson, D.S., Whitlock, J.H.: Estimation of a truncation point. Biometrika 51, 33–39 (1964)
Wilson, A.D., King, R.E., Wilson, J.R.: Case study on statistically estimating minimum makespan for flow line scheduling problems. European Journal of Operational Research 155, 439–454 (2004)
Zhigljavsky, A., Hamilton, E.: Stopping rules in k-adaptive global random search algorithms. Journal of Global Optimization 48(1), 87–97 (2010)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Meng, X., Carling, K. (2014). How to Decide Upon Stopping a Heuristic Algorithm in Facility-Location Problems?. In: Huang, Z., Liu, C., He, J., Huang, G. (eds) Web Information Systems Engineering – WISE 2013 Workshops. WISE 2013. Lecture Notes in Computer Science, vol 8182. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-54370-8_23
Download citation
DOI: https://doi.org/10.1007/978-3-642-54370-8_23
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-54369-2
Online ISBN: 978-3-642-54370-8
eBook Packages: Computer ScienceComputer Science (R0)