HEURISTICS, METAHEURISTICS, MACROHEURISTICS

Some Basic Heuristics

1. Approximate solving schemes
2. Greedy algorithms
3. Genetic algorithms
4. Randomization
5. Simulated annealing
6. Tabu-search
7. GRASP
8. Ant Systems
9. Memetic alorithms
10. Nature inspired heuristics
11. Neural networks
12. Space-filling curves (Prof. John J. Bartholdi III, School of Industrial and Systems Engineering, Georgia Institute of Technology)
13. Interchange techniques
14. Evolutionary multiobjective optimization
15. Cross-Entropy (CE) Method (Prof. Reuven Y. Rubinstein, Technion, Israel)
16. Randomized algorithms
17. Anytime algorithms (Prof. Shlomo Zilberstein)
18. Partitioning /Synthesis Morphological Macroheuristics
19. Sublinear time algorithms (Prof. Ronitt Rubinfeld)
20. Data corecting approach (Prof. Boris Goldengorin)
21. Self-assembly algorihm systems
22. Autonomous search
23. Combinatorial search
24. Hyperheuristics

Research Groups / Researchers

  • Lab. for Experimental Algorithms (Univ. of Trento, Italy)
  • EU/ME the European chapter on metaheuristics (EURO Working Group)
  • Dorit Hochbaum (Univ. of California at Berkeley) (approximation algorithms)
  • Vijay V. Vazirani (Georgia Tech.) (general, approximation algorithms, etc.)
  • David B. Shmoys (Cornell Univ.) (approximation algorithms)
  • Eva Tardos (Cornell Univ.) (general, approximation algorithms, networking, network design, routing, clustering, facility location, etc.)
  • Carla P. Gomes (Cornell Univ.) (general, algorithm porfolio, approximation, randomization, etc.)
  • Evolutionary Multi-Objective Optimization (Carlos A. Coello Coello)
  • Slomo Zilberstein (Univ. of Massachusetts at Amherst) (anytime algorithms, etc.)
  • Ronitt Rubinfeld (MIT) (sublinear time algorithms, etc.)
  • Sartaj K. Sahni (Univ. of Florida) (approximate algorithms, knapsack, scheduling, etc.)
  • Maxim Sviridenko (approximate algorithms, etc.) ( site at IBM Research ) ( site at Univ. of Warwick )
  • Gregory Z. Gutin (Univ. of London) (TSP, generalized TSP, multidimentional assignment, longest path problem, domination analysis, memetic algorithms, heuristics, etc.)
  • Abraham P. Punnen (Simon Fraser Univ.) (domination analysis, large scale neighborhood search, assignment problems, TSP, spanning problems, etc.)
  • Uri Zwick (Tel Aviv Univ.) (approximation algorithms, dynamic algorithms, online algorihtms, parallel algorithms, routing, selecting the median algorithms, etc.)
  • Reuven Bar-Yehuda (Technion) (approximation algorithms, practical aspects of VLSI, etc.)
  • Asaf Levin (Technion) (approximate algorithms, etc.)
  • Gilbert Laporte (HEC Montreal) (metaheuristics, etc.)
  • John R. Koza (genetic programming)
  • Michel X. Goemans (MIT) (approximation algorithms, primal-dual algorithms, randomized algorithms, TSP, spanning trees, covering, general assignment problem, networking, scheduling, semidefinite programming, etc.)
  • Fred W. Glover (Univ. of Colorado) (metaheuristics, Tabu-search, etc.)
  • Ibrahim Osman (School of Business, American Univ. of Beirut) (metaheuristics, etc.)
  • Christian Blum (Tehcnical Univ. of Catalonia) (hybrid metaheuristics, evolutionary algorithms, variable neighborhood search, swarm intelligence, etc.)
  • Zbigniew Michalewicz (Univ. of Adelaide, Australia) (genetic algorithms, evolutionary computation, etc.)
  • Andrea Roli (Univ. of Bologna) (hybrid metaheuristics, large neighborhood search, genetic algorihtms, stochastic search algorithms, etc.)
  • Boris I. Goldengorin (High School of Economics, Russia, Nuzhny Novgorod) (data correcting approach, TSP, assignment problems, multidimensional assignment, facility location, enumerative algorithms, etc.)
  • Natalio Krasnogor (Univ. of Nottingham) (genetic algorithms and evolutionary computation, nature inspired heuristics, self-assembly algorihm systems, memetic algorithms, applications in bioinformatics, system biology, chemistry, etc. )
  • Moshe Dror (Univ. of Arizona) (routing, scheduling, assignment, approximation, multicriteria combinatorial optimization problems, etc.)
  • Andrzej Jaszkiewicz (Poznan Univ. of Tehcnology, Poland) (knapsack, multiple choice problem, TSP, multicriteria combinatorial optimization, metaheuristics, memetic algorithms, multiobjective evolutionary algorithms, etc.)
  • Hershel M. Safer (Tel Aviv Univ.) (multicriteria combinatorial optimization, approximation algorithms, bioinformatics, etc.)
  • Matthias Erhgott (The Univ. of Auckland) (multicriteria combinatorial optimization, approximation algorithms, etc.)
  • Xavier Gandibleux (The Univ. of Nantes) (multicriteria combinatorial optimization, global optimization, evolutionary multiobjective optimization, approximation algorithms, application in transportation, communication, etc.)
  • Vitaly Strusevich (Univ. of Greenwich, UK) (general, scheduling, knapsack, approximation algorihtms, supply chains, etc.)
  • Frank Werner (Univ. of Magdeburg) (scheduling, heuristics, etc.)
  • Chris N. Potts (Univ. of Southhampton) (scheduling, heuristics, variable neighborhood search, etc.)
  • Edmund K. Burke (Univ. of Nottingham) (scheduling, timetabling, packing, meta-heuristics, hyper-heuristics, bioinformatics, etc.)
  • Vangelis Th., Paschos (LAMSADE, Univ. Paris-Dauphine) (general, graph coloring,, Steiner problem, TSP, approximation algorithms, on-line algorithms, reoptimization, etc.)
  • Yury Kochetov (Sobolev Inst. of Mathematics, Novosibirsk, Russia) (location, local search, neighborhood search, metaheuristics, etc.)

    Journals

  • Journal of Heuristics
  • ACM Journal of Experimental Algorithmics
  • J. of the ACM
  • Memetic Computing
  • J. of Algorithms
  • Eur. J. of Operational Research
  • Computers and Operations Research
  • Natural Computing
  • Networks
  • Algorithmica
  • INFOR
  • Applied Intelligence
  • Informatica (Lith.)
  • TOP

    Bibliography

  • Books
    1. E. Alba, (Ed.). Parallel metaheuristics: a new class of algorithms. Wiley, 2005.
    2. E.G. Coffman, Jr. (ed.), Scheduling in Computer and Job Shop Systems, New York: J.Wiley & Sons, 1976.
    3. K. Deb, Multi-Objective Optimization using Evolutionary Algorithms. Wiley, Chichester, UK, 2001.
    4. S. Edelkamp, S, Schroedl, Heuristic Search: Thepory and Applications. Morgan Kaufmann, 2011.
    5. M.R. Garey, D.S. Johnson, Computers and Intractability. The Guide to the Theory of NP-Completeness. San-Francisco: W.H. Freeman and Company, 1979.
    6. F. Glover, G. Kochenberger (Eds.), Handbook of Metaheuristics. vol. 57, Kluwer, 2002.
    7. F. Glover, G.A. Kochenberger, (Eds.). Handbook of Metaheuristics. Kluwer, 2003.
    8. F. Glover, M. Laguna, Tabu Search. Kluwer, 1997.
    9. D.E. Goldberg, Genetic Algorithm in Search, Optimization and Machine Learning. Mass: Addison-Wesley, Reading, 1989.
    10. D. Hochbaum (Ed.), Approximate Algorithms for NP-Hard Problems. PWS, 192-235, 1997.
    11. J.H. Holland, Adaptation in Natural and Artificial Systems. Ann Arbor, Michigan: Univ. of Michigan Press, 1975.
    12. H. Kellerer, U. Pferschy, D. Pisinger, Knapsack Problems. Berlin: Springer-Verlag, 2004.
    13. J.R. Koza, Genetic Programming. MIT Press, 1992.
    14. E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan, and D.B. Shmoys, (eds.), The Traveling Salesman Problem. Chichester: J.Wiley&Sons, 1985.
    15. M.Sh. Levin, Combinatorial Engineering of Decomposable Systems. Dordrecht, Kluwer, 1998.
    16. V. Maniezzo, T. Stutzle, S. Voss, (Eds.), Metaheuristics: Hybridizing Metaheuristics and Mathematical Programming. Springer, 2010.
    17. S. Martello, P. Toth, Knapsack Problem: Algorithms and Computer Implementation, J.Wiley & Sons, New York, 1990.
    18. Z. Michalewicz, Genetic Algorithms + Data Structure = Evolutionary Programs, 3rd ed., Berlin: Springer-Verlag, 1996.
    19. Z. Michalewicz, and D.B. Fogel, How To Solve It: Modern Heeuristics. Berlin: Springer-Verlag, 2000.
    20. Z. Michalewicz, Th. Baeck, and D.B. Fogel, (Eds.), Handbook of Evolutionary Computation. London: Oxford Univ. Press, 1997.
    21. Z. Michalewicz, and D. Dasgupta, (Eds.), Evolutionary Aalgorithms in Engineering Application. Berlin: Springer-Verlag, 1997.
    22. M. Mitchell, An Introduction to Genetic Algorithms. MIT Press, 1998.
    23. R. Motwani, P. Raghavan, Randomized Algorithms. Cambridge Univ. Press, 1995.
    24. I.H. Osman, J.P. Kelly, (Eds.), Meta-heuristics: Theory and Applications. Kluwer, 1996.
    25. V.J. Rayward, I.H. Osman, C.R. Reeves (eds.), Modern Heuristic Search Methods. J.Wiley & Sons, New York, 1996.
    26. G. Reinelt, The Traveling Salesman, Berlin: Springer-Verlag, 1994.
    27. E. Talbi, Metaheuristics: From Design To Implementation. Wiley, 2009.
    28. V.V. Vazirani, Approximation Algorithms. Springer, 2002.
    29. D.P. Williamson, D.B. Shmoys, The Design of Approximation Algorithms. Cambridge Univ. Press, 2011.
    30. Youssef Hamadi, Eric Monfroy (Eds.), Autonomous Search. Springer, 2012.
    31. Youssef Hamadi, Combinatorial Search: From Algorithms to Systems. Springer, 2013.
    32. S. Bandyopadhyay, S. Saha, Unsupervised Classification: Similarity Measures, Classical and Metaheuristic Approaches. Springer, 2013.
    33. Franz Rothlauf, Design of Modern Heuristics: Principles and Application. Springer, 2011.
    34. Yossi Borenstein, Alberto Moraglio (Eds.), Theory and Principled methods for the Design of Metaheuristics. Springer, 2014.
    35. Patrick Siarry, Zbigniew Michalewicz (Eds.), Advances in Metaheuristics. Springer, 2008.
    36. Enrique Alba, Parallel Metaheuristics: A New Class of Algorithms. Wiley, 2005.

  • Journal Special Issues
    1. X. Gandibleux, A. Jaszkiewicz, A. Freville, R. Slowinski (Eds.). Special Issue "Multiple Objective MetaHeuristics", J. of Heuristics, 6(3), 2000.
    2. G. Gutin, A.P. Punnen (Eds.), Foundations of Heuristics in Combinatorial Optimization. Special Issue of J. "Discrete Applied Mathematics", Elsevier, 2002.
    3. G. Laporte, and I. Osman, (Eds.) Metaheuristics in Combinatorial Optimization. Annals of Operations Research, Vol. 69, Amsterdam: Baltzer, 1995.

  • Surveys
    1. R.K. Ahuja, O. Ergun, J.B. Orlin, A.B. Punnen, A survey of very large-scale neighborhood search techniques. Discrete Applied Mathematics, 123(1-3), 75-102, 2002.
    2. M. Ball, and M. Magazine, The Design and Analysis of Heuristics, Networks, Vol. 11, No. 2, pp. 215-219, 1981.
    3. C. Blum, A. Roli, Metaheuristics in Combinatorial Optimization: Overview and Conceptual Comparison. ACM Computing Surveys, 35(3), 268-308, 2003.
    4. E.K. Burke, M. Hyde, G. Kendall, G. Ochoa, E. Zcan, J. Woodward, Handbook of Metaheuristics, second ed., Springer, 2010. pp. 449–468 (Chapter: A Classification of Hyper-heuristic Approaches).
    5. E.K. Burke, M. Gendreau, M. Hyde, G. Kendall, G. Ochoa, E. Ozcan, et al., Hyper-heuristics: A survey of the state of the art. J. of the ORS, 64(12), 1695-1724, 2013.
    6. T.G. Cranic, M. Toulouse, Parallel strategies for meta-heuristics. In: F. Glover, G. Kochenberger (Eds.), Handbook of Metaheuristics. vol. 57, Kluwer, 2002.
    7. C.A. Coello Coello, An update survey of GA-based multiobjective optimization tehcniques. ACM Comput. Surveys, 32(2), 109-143, 2000.
    8. Matthias Ehrgott, Approximate algorithms for combinatorial multiobjective optimization problems. Int. Transactions in Operational Research, 7(1), 5-31, 2000.
    9. Matthias Ehrgott, Xavier Gandibleux, Approximate solution methods for multiobjective combinatorial optimization. TOP, 12(1), 1-89, 2004.
    10. B. Escoffier, V.Th. Paschos, A survey on the structure of approximation classes. Computer Science Review, 4(1), 19-40, 2010.
    11. G.V. Gens, E.V. Levner, Approximation algorithms for certain universal problems in scheduling theory. Engineering Cybernetics, 16(6), 31-36, 1978.
    12. D.F. Jones, S.K. Mirrazavi, Multi-objective meta-heuristics: An overview of the curent state- of-the-art. Eur. J. of Oper. Res., 137(1), 1-9, 2002.
    13. I.H. Osman, G. Laporte, Metaheuristics: A bibliography. Ann. Oper. Res. 63, 513-623, 1996
    14. S. Sahni, E. Horowitz, Combinatorial problems: reducibility and approximation. Operations Research, 26, 718-759, 1978.
    15. D.B. Shmoys, Computing near optimal solutions to combinatorial optimization problems. In: W. Cook, L. Lovasz, P.D. Seymour (Eds.), Combinatorial Optimization. AMS, 355-397, 1995.
    16. D.B. Shmoys, Approximation algorithms for cut problems and their application to divide-and-conquer. In: D. Hochbaum (Ed.), Approximate Algorithms for NP-Hard Problems. PWS, 192-235, 1997.
    17. A.S. Schulz, D.B. Shmoys, D.P. Williamson, Approximation algorithms. Proc. of National Academy of Sciences, 84, 12734-12735, 1997.
    18. E.-G. Talbi, A Taxonomy of Hybrid Metaheuristics. J. of Heuristics, 8(5), 541-564, 2002.

  • Some Basic Papers
    1. R. Karp, Probabilistic Analysis of Partitioning Algorithms for the Traveling Salesman Problem in the Plan. Mathematics of the Operations Research, Vol. 2, No. 3, pp. 209-224, 1977.
    2. S. Lin, B.W. Kernighan, An effective heuristic algorithm for the Traveling Salesman problem. Operations Research, 21, 498-516, 1973.
    3. J.J. Bartholdi, III, and L.K. Platzman, Spacefilling Curves and the Planar Traveling Salesman Problem. J. of the ACM, 36(4), 719-737, 1989.
    4. O.H. Ibarra, C.E. Kim, Fast approximation algorithms for the knapsack and sum of subsets problems. J. of the ACM, 22, 463-468, 1975.
    5. S. Sahni, Approximate algorithms for the knapsack problem. J. of the ACM, 22(1), 115-124, 1975.
    6. D. Karger, R. Motwani, M. Sudan, Approximate Graph Coloring by Semidefinite Programming, J. of the ACM, 45(2), 246-265, 1998.
    7. S. Zilberstein, S. Russell, Approximate reasoning using anytime algorithms. In: S. Natarajan (Ed.), Imprecise and Approximate Computation. Kluwer, 1995
    8. L.A. Wolsey, Heuristic analysis, linear programming and branch and bound. Mathematical Programming Study, 13, 121-134, 1980.
    9. M. Yannakakis, On the approximation of maximum satisfiability. J. of Algorithms, 17, 475-502, 1994.
    10. D.B. Fogel, An introduction to simulated evolutionary optimization. IEEE Trans. Neural Networks, 5(1), 3-14, 1994.
    11. P. Moscato, Memetic algorithms: A short introduction. In: F.G.D. Corne, M/ Dorigo, (Eds.), New Ideas in Optimization. McGraw-Holl, 1999.
    12. A.P. Punnen, S.N. Kabadi, Domination analysis of some heuristics for the traveling salesman problem. Discrete Applied Mathematics, 119(1-2), 117-128, 2002.
    13. J.B. Orlin, A.P. Punnen, Y.P. Aneja, Approximate local search in combinatorial optimization. SIAM J. Computing, 33(5), 1201-1214, 2004.
    14. S. Voss, Steiner's problem in graphs: Heuristic methods. Discr. Appl. Math., 40(1), 45-72, 1992.
    15. B. Goldengorin, D. Gosh, G. Sieksma, Data Correcting: A Methodology for Obtaining Near-Optimal Solutions. In: Operations Research with Economic and Industrial Applications: Emerging Trends. New Delhi, Anamaya Publishers, 2005.
    16. E. Zitzler, L. Thiele, Multiobjective evolutionary algorithms: a comparative case study and the strength Pareto approach. IEEE Trans. on Evolutionary Computation, 3(4), 257-271, 1999.
    17. G. Gens, E. Levner, An approximate binary search algorithm for the multiple-choice knapsack problem. Inf. Proc. lett., 67(5), 261-265, 1998.
    18. Piotr Czyzzak, Adrezej Jaszkiewicz, Pareto simulated annealing - a metaheuristic technique for multiple-objective combinatorial optimization. J. of Multi-Criteria Decision Analysis, 7(1), 34-47, 1998.
    19. Jourdan, M. Basseur, E.-G. Talbi, Hybridizing exact methods and metaheuristics: A taxonomy. EJOR 199(3), 620-629, 2009.
    20. C. Gomes, B. Selman, Algorithm portfolio. Artif. Intell., 126(1-2), 43-62, 2001.
    21. E. Ozcan, B. Bilgin, E. Korkmaz, A comprehensive analysis of hyper-heuristics. Intelligent Data Analysis 12(1), 2-23, 2008.
    22. P. Cowling, G. Kendall, E. Soubeira, Hyperheuristics: A tool for rapid prototyping in scheduling and optimization. In: S. Cagnoni, J. Gottlieb, E. Hart, M. Middendorf, G.R. Raidl (eds), Proc. of Applications of Evolutionary Computing, EvoWorkshop 2002, LNCS 2279, Springer, 1-10, 2002.
    23. M. Maashi, E. Ozcan, G. Kendall, A multi-objective heuristic based on choice function. Expert Systems with Applications 41(9), 4475-4493, 2014.
    24. M. Maashi, G. Kendall, E. Ozcan, Choice function based hyper-heuristics for multi-objective optimization. Applied Soft Computing 28, 312-326, 2015.
    25. R. Qu, E.K. Burke, B. McCollum, A. Meisels, S. Petrovic, A Graph-Based Hyper-Heuristic for Educational Timetabling Problems. EJOR, 176, 177-192, 2007.
    26. R. Qu, N. Pham, R. Bai, G. Kendall, Hybridising heuristics within an estimation distribution algorithm for examination timetabling. Applied Intellgience, 2015. (in press)

  • Tehcnical Reports/Working Papers
    1. Hershel M. Safer, James B. Orlin, Fast Approximation Schemes for Multi-Criteria Flow, Knapsack, and Scheduling Problems. Working Paper WP # 37855-95, Operations Research Center, MIT, 1995a.
    2. Hershel M. Safer, James B. Orlin, Fast Approximation Schemes for Multi-Criteria Combinatorial Optimization. Working Paper WP # 37856-95, Operations Research Center, MIT, 1995b.
    3. Hershel M. Safer, James B. Orlin, Moshe Dror, Fully Polynomial Approximation in Multi-Criteria Combinatorial Optimization. Working Paper WP8, MIT, 53 pp., 2004.
    4. H, Kellerer, K. Rustogi, V.A. Strusevich, Approximation Schemes on a Single Machine Subject to Comulative Deterioration and Maintenance. Report SORG-02-2011, Univ. of Greenwich, School of Computing and Mathematical Sciences, 16 pp., 2011.
    5. E.S. Sin, N.S.M. Khan, Hyper heuristic based on great deluge and its variants for exam timetabling problem. Electronic preprint, arXiv: 1202.1891, 2012. http: //arxiv.org/abs/1202.1891

  • PhD Theses
    1. E. Zitzler, Evolutionary Algorithms for Multiobjective Optimization: Methods and Applications. PhD Thesis, Swiss Federal Inst. of Technology (ETH) Zurich, Switzerland, 1999.
    2. S.C. Hiremath, New heuristic and metaheuristic approaches applied to the multiple-choice multidimensional knapsack problem. PhD thesis, Wright State. Univ., USA, 2008.
    3. Matthew Streeter, Using Online Algorithms to Solve NP-Hard Problems More Efficiently in Practice. PhD Thesis, School fo CS, CMU, CMU-CS-07-172, Dec. 2007.
    4. S. Zilberstein, Operational Rationality Through Compilation of Anytime Algorithms. PhD Dissertation, Univ. of California, Berkley, 1993.
    5. Clifford Stein, Approximation algorithms for multicommodity flow and shop scheduling problems. PhD thesis, MIT, 1992.
    6. Fabian Chudak, Approximation algorithms for the uncapacitated facility location problem. PhD thesis, Cornell Univ., 1998.
    7. Tim Games, Approximation algorithms via the Primal-Dual schema: Applications of the simple dual-ascent method to problems from logistics. PhD thesis, Cornell Univ., 2009.
    8. D. Levine, A Parallel Genetic Algorithm for the Set Partitioning Problem. PhD Thesis, Argonne National Laboratory, Illinois Inst. of Technology, Argonne, 1994.
    9. W.E. Hart, Adaptive Global Optimization with Local Search. PhD Thesis, Univ. of California, San Diego, 1994.
    10. Maxim Sviridenko, Approximation Algorithms for Discrete Facility Location Problems. PhD thesis, Sobolev Inst. of Mathematics, Novosibirsk, Russia, Jan. 1999.
    11. M. Skutella, Approximation and Randomization in Scheduling. PhD thesis, Technical Univ. of Berlin, 1998.
    12. N, Hussin, Tabu Search Based Hyper-heuristic Approach for Examination Timetabling. PhD Thesis, The Univ. of Nottingham, UK, 2005.

  • MS Theses
    1. M. Petrik, Learning Parallel Portfolios of Algorithms. MS thesis, Comenius Univ., Bratislava, Slovakia, 2005.
    2. S.-M. Foo, An Approach of Combining Simulated Annealing and Genetic Algorithms. MS thesis, Univ. of Illinoise, Urbana-Champaign, 1991.
    3. Donald Arthur Parish, A Genetic Algorithm Approach to Automatic Satellite Range Scheduling. MS thesis, Graduate School of Engineering, Air Force Institute of Technology, USA, March 1994.