Skip to main content

Heuristics for NP-hard optimization problems - simpler is better!? Cover

.blurhash-client-img { display: none !important; }

Heuristics for NP-hard optimization problems - simpler is better!?

Logistics, Supply Chain, Sustainability and Global Challenges

Volume 6 (2015): Issue 1 (November 2015)

By: Janez Žerovnik

Open Access

|Dec 2015

Abstract

We provide several examples showing that local search, the most basic metaheuristics, may be a very competitive choice for solving computationally hard optimization problems. In addition, generation of starting solutions by greedy heuristics should be at least considered as one of very natural possibilities. In this critical survey, selected examples discussed include the traveling salesman, the resource-constrained project scheduling, the channel assignment, and computation of bounds for the Shannon capacity.

References

1. E. H. L. Aarts and J. K. Lenstra, Local Search Algorithms, John Wiley & Sons, Chichester, 1997.
Search in Google Scholar
2. J. Brest and J. Žerovnik, “An approximation algorithm for the asymmetric traveling salesman problem,” Ricerca operativa, vol. 28, pp. 59-67, 1999.
Search in Google Scholar
3. H. Cohn and M. Fielding, “Simulated annealing: searching for an optimal temperature schedule,” SIAM J. Optim., Vol. 9, pp. 779-802, 1999.10.1137/S1052623497329683
Search in Google Scholar
4. A. G. Ferreira and J. Žerovnik, “Bounding the probability of success of stochastic methods for global optimization,” Computers & mathematics with applications, vol. 25, pp. 1-8, 1993.10.1016/0898-1221(93)90275-Z
Search in Google Scholar
5. B. Hajek and G. Sasaki, “Simulated annealing - to cool or not,” System Control Lett., vol.12, pp. 443-447, 1989.10.1016/0167-6911(89)90081-9
Search in Google Scholar
6. R. Kolisch and S. Hartmann, “Heuristic algorithms for solving the resource-constrained project scheduling problem - classification and computational analysis,” in Handbook on recent advances in project scheduling, J. Weglarz, Ed., Kluwer, 1999, pp. 147-178.10.1007/978-1-4615-5533-9_7
Search in Google Scholar
7. R. Kolisch and S. Hartmann, “Experimental investigation of heuristics for resource-constrained project scheduling: An update,” European Journal of Operational Research, vol. 174, pp. 23-37, 2006.10.1016/j.ejor.2005.01.065
Search in Google Scholar
8. B. Korte and J. Vygen, Combinatorial optimization: Theory and algorithms, Springer, Berlin, 2002.10.1007/978-3-662-21711-5
Search in Google Scholar
9. T. Kramberger, G. Štrubelj and J. Žerovnik, “Chinese postman problem with priority nodes, ” Foundations of computing and decision sciences, 2009, vol. 34, no. 4, pp. 233-264, 2009.
Search in Google Scholar
10. T. Kramberger and J. Žerovnik, “Priority constrained Chinese postman problem”, Logistics & sustainable transport, vol. 1, pp. 21-35 , 2008.
Search in Google Scholar
11. P.J. van Laarhoven and E.H. Aarts, Simulated Annealing: Theory and Applications, Kluwer, Dordrecht, 1987.10.1007/978-94-015-7744-1
Search in Google Scholar
12. E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan, and D.B Shmoys, The traveling salesman problem, Wiley & Sons, Chichester, 1985.
Search in Google Scholar
13. L. Lovasz, “On the Shannon capacity of a graph, ” IEEE Trans. Inform. Theory, vol. 25, 1-7, 1979.10.1109/TIT.1979.1055985
Search in Google Scholar
14. D. Mitra, F. Romeo and A. Sangiovanni-Vincentelli, “Convergence and finite time behavior of simulated annealing, ” Adv. in Appl. Probab., vol. 18, pp. 747-771, 1986.10.1017/S0001867800016050
Search in Google Scholar
15. N. Mladenović and P. Hansen: “Variable neighborhood search, ” Computers & OR, vol. 24, pp. 1097-1100, 1997.
Search in Google Scholar
16. I. Pesek, A. Schaerf, and J. Žerovnik, “Hybrid local search techniques for the resource-constrained project scheduling problem,” Lecture notes in computer science, vol. 4771, pp. 57-68, 2007.
Search in Google Scholar
17. A. Petford and D. Welsh, “A randomised 3-colouring algorithm, ” Discrete Mathematics, vol. 74, pp. 253-261, 1989.10.1016/S0167-5060(08)70314-5
Search in Google Scholar
18. C. E. Shannon, “The zero-error capacity of a noisy channel, ” IRE Trans. Inform. Theory, vol. 2, pp. 8-19, 1956.10.1109/TIT.1956.1056798
Search in Google Scholar
19. J. Shawe-Taylor and J. Žerovnik, “Analysis of the mean field annealing algorithm for graph colouring,” Journal of artificial neural networks, vol. 2, pp. 329-340, 1995.
Search in Google Scholar
20. J. Shawe-Taylor and J. Žerovnik, “Adapting temperature for some randomized local search algorithms,” in: Advances in scientific computing, computational intelligence and applications, N. Mastorakis, Ed. WSES Press, 2001, pp. 82-87.
Search in Google Scholar
21. E.-G. Talbi, Metaheuristics: From Design to Implementation, John Wiley & Sons, 2009.10.1002/9780470496916
Search in Google Scholar
22. S. Ubeda and J. Žerovnik, “A randomized algorithm for a channel assignment problem,” Speedup, vol. 11, pp. 14-19, 1997.
Search in Google Scholar
23. A. Vesel and J. Žerovnik, “How well can ants colour graphs?” CIT, vol. 8, pp. 131-136, 2000.10.2498/cit.2000.02.04
Search in Google Scholar
24. A. Vesel and J. Žerovnik, “Improved lower bound on the Shannon capacity of C7,” Information processing letters, 2002, vol. 81, pp. 277-282, 2002.10.1016/S0020-0190(01)00229-0
Search in Google Scholar
25. G. Žerovnik and J. Žerovnik, “Constructive heuristics for the canister filling problem,” Central European Journal of Operations Research, 2011, vol. 19, pp. 371-389, 2011.10.1007/s10100-010-0164-5
Search in Google Scholar
26. J. Žerovnik, “A heuristics for the probabilistic traveling salesman problem,” in Symposium on Operation Research '95, V. Rupnik and M. Bogataj, Eds. Ljubljana: Slovenian Society Informatika, 1995, pp. 165-172.
Search in Google Scholar
27. J. Žerovnik, “A randomized algorithm for k-colorability,” Discrete Mathematics, vol. 131, pp. 379-393, 1994.10.1016/0012-365X(94)90402-2
Search in Google Scholar
28. J. Žerovnik, “On temperature schedules for generalized Boltzmann machine,” Neural network world, vol. 10, pp. 495-503, 2000.
Search in Google Scholar
29. J. Žerovnik, “Simulated annealing type metaheuristics - to cool or not to cool,” in 7th International Symposium on Operational Research in Slovenia, L. Zadnik Stirn, M. Bastič and S. Drobne, Eds. Ljubljana: Slovenian Society Informatika, 2003, 6 pp.
Search in Google Scholar
30. http://en.wikipedia.org/wiki/Combinatorial_optimization
Search in Google Scholar
31. http://www.claymath.org/millenium-problems/p-vs-np-problem
Search in Google Scholar
32. http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/
Search in Google Scholar
33. http://129.187.106.231/psplib/
Search in Google Scholar
34. http://fap.zib.de/index.php
Search in Google Scholar
35. http://en.wikipedia.org/wiki/Greedy_randomized_adaptive_search_procedure
Search in Google Scholar
36. H. Zupan, N. Herakovič, and J. Žerovnik, “A hybrid metaheuristic for job-shop scheduling with machine and sequence-dependent setup times,” in 13th International Symposium on Operational Research in Slovenia, L. Zadnik Stirn, M. et al., Eds. Ljubljana: Slovenian Society Informatika, 2015, pp. 129-134.
Search in Google Scholar
37. D. Kaljun, and J. Žerovnik, “On modelling of spatial light distribution of LED with attached secondary optics,” in 13th International Symposium on Operational Research in Slovenia, L. Zadnik Stirn, M. et al., Eds. Ljubljana: Slovenian Society Informatika, 2015 , pp. 363-368.
Search in Google Scholar
38. D. Kaljun, D. Rupnik Poklukar, and J. Žerovnik, Janez. “Heuristics for optimization of LED spatial light distribution model,” Informatica, vol. 39, pp. 147-159, 2015. http://www.informatica.si/index.php/informatica/article/view/831/625.
Search in Google Scholar

Articles in this issue

DOI: https://doi.org/10.1515/jlst-2015-0006 | Journal eISSN: 2784-7497

Journal RSS Feed

Language: English

Page range: 1 - 10

Published on: Dec 9, 2015

Published by: University of Maribor

In partnership with: Paradigm Publishing Services

Publication frequency: 2 issues per year

Keywords:

> Optimization,

metaheuristics,

greedy construction,

traveling salesman problem

Related subjects:

Business and economics,

Business management,

Business management, other,

Transportation, logistics, air traffic, shipping,

Environmental management,

Business informatics,

Process management

© 2015 Janez Žerovnik, published by University of Maribor
This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.

Volume 6 (2015): Issue 1 (November 2015)