Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Classification of applied methods of combinatorial optimization

  • Systems Analysis
  • Published:
Cybernetics and Systems Analysis Aims and scope

The paper reviews most popular approaches to the development of applied methods of combinatorial optimization. A number of characteristics and criteria are proposed that underlie the classification of approximate algorithms. The classification continues the previous investigations in combinatorial optimization and allows determining key components of computational schemes used in constructing efficient hybrid metaheuristics.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  1. T. Stützle, “Local search algorithms for combinatorial problems — analysis, improvements and new applications,” PhD. Thesis, Technische Univ. Darmstadt, Darmstadt (1998).

  2. R. J. M. Vaessens, E. H. L. Aarts, and J. K. Lenstra, “A local search template,” Comput. Oper. Res., 25, No. 11, 969–979 (1998).

    Article  MATH  MathSciNet  Google Scholar 

  3. M. Birattari, L. Paquete, T. Stützle, and K. Varrentrapp, “Classification of metaheuristics and design of experiments for the analysis of components,” Techn. Rep., N AIDA-01-05, Techn. Univ. Darmstadt, Darmstadt (2001).

  4. C. Blum and A. Roli, “Metaheuristics in combinatorial optimization: overview and conceptual comparison,” ACM Computing Surveys, 35, No. 3, 268–308 (2003).

    Article  Google Scholar 

  5. M. Gendreau and J.-Y. Potvin, “Metaheuristics in combinatorial optimization,” Ann. Oper. Res., 140, No. 1, 189–213 (2005).

    Article  MATH  MathSciNet  Google Scholar 

  6. V. K. Leont’ev, “Discrete optimization,” J. Comp. Math. Math. Phys., 47, No. 2, 328–340 (2007).

    Article  MathSciNet  Google Scholar 

  7. H. H. Hoos and T. Stützle, Stochastic Local Search: Foundations and Applications, Morgan Kaufmann Publ., San Francisco (2005).

    MATH  Google Scholar 

  8. G. R. Raidl, “A unified view on hybrid metaheuristics,” in: Lect. Notes Comput. Sci., 4030, Springer-Verlag, Berlin (2006), pp. 1–12.

    Book  Google Scholar 

  9. L. F. Gulyanitskii and I. V. Sergienko, “Metaheuristic downhill simplex method in combinatorial optimization,” Cybern. Syst. Analysis, 43, No. 6, 822–829 (2007).

    Article  MATH  MathSciNet  Google Scholar 

  10. C. H. Papadimitriou and K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Englewood Cliffs, Prentice Hall (1982).

    MATH  Google Scholar 

  11. I. V. Sergienko, Mathematical Models and Methods to Solve Discrete Optimization Problems [in Russian], Naukova Dumka, Kyiv (1988).

    Google Scholar 

  12. V. S. Mikhalevich and A. I. Kuksa, Methods of Sequential Optimization in Discrete Network Problems of Optimal Resource Allocation [in Russian], Nauka, Moscow (1983).

    Google Scholar 

  13. A. A. Pavlov and E. B. Misyura, “Efficient accurate PDS-algorithm to solve a total delay problem for one device,” Systemni Doslidzh. Inform. Tekhnol., No. 4, 30–59 (2004).

  14. P. Pardalos and M. G. C. Resende (eds.), Handbook of Applied Optimization, Oxford Univ. Press, Oxford (2002).

    MATH  Google Scholar 

  15. T. F. Gonzalez (ed.), Handbook of Approximation Algorithms and Metaheuristics, CRC Press, Boca Raton (FL) (2007).

    MATH  Google Scholar 

  16. I. V. Sergienko and M. F. Kaspshitskaya, Models and Methods for Computer Solution of Combinatorial Optimization Problems [in Russian], Naukova Dumka, Kyiv (1981).

    Google Scholar 

  17. I. V. Sergienko and V. P. Shilo, Discrete Optimization Problems [in Russian], Naukova Dumka, Kyiv (2003).

    Google Scholar 

  18. K. A. De Jong, Evolutionary Computation: A Unified Approach, MIT Press, Cambridge (MA) (2006).

    MATH  Google Scholar 

  19. G. Leguizamon, C. Blum, and E. Alba. “Evolutionary computation,” in: T.F. Gonzalez (ed.), Handbook of Approximation Algorithms and Metaheuristics, CRC Press, Boca Raton (FL) (2007), pp. 372–386.

    Google Scholar 

  20. J. Kennedy, R. C. Eberhart, and Y. Shi, Swarm Intelligence, Morgan Kaufmann, San Francisco (CA) (2001).

    Google Scholar 

  21. S. Khuller, B. Raghavachari, and N. E. Young, “Greedy methods,” in: T.F. Gonzalez (ed.), Handbook of Approximation Algorithms and Metaheuristics, CRC Press, Boca Raton (FL) (2007), pp. 67–80.

    Google Scholar 

  22. I. V. Sergienko, “A method to solve extremum problems,” Avtomatika, No. 5, 15–21 (1964).

  23. Yu. A. Kochetov, “Computational bounds for local search in combinatorial optimization,” J. Comp. Math. Math. Phys., 48, No. 5, 747–763 (2008).

    Article  MathSciNet  Google Scholar 

  24. L. F. Hulianytskyi and A. N. Khodzinskii, “Features of the implementation of branch-and-bound algorithm and descent-vector method in VEKTOR–1B,” in: Computational Aspects in Application Software Packages [in Russian], Inst. Cybern. AS USSR, Kyiv (1979), pp. 25–30.

    Google Scholar 

  25. N. Mladenović and P. Hansen, “Variable neighbourhood search,” Comput. Oper. Res., No. 24, 1097–1100 (1997).

    Google Scholar 

  26. P. Hansen, N. Mladenovic, and J. A. Moreno-Pérez, “Variable neighbourhood search: methods and applications,” Quarterly J. Oper. Res., 6, No. 4, 319–360 (2008).

    Article  MATH  Google Scholar 

  27. C. Voudouris and E. P. K. Tsang, “Guided local search,” in: F. Glover (ed.), Handbook of Metaheuristics, Kluwer Acad. Publ., Norwell (MA) (2003), pp. 185–218.

    Google Scholar 

  28. B. W. Kernighan and S. Lin, “An efficient heuristic procedure for partitioning graphs,” Bell System Techn. J., No. 49, 291–307 (1970).

  29. S. Kirkpatrik, C. D. Gelatt, and M. P. Vecchi, “Optimization by simulated annealing,” Science, 220, No. 4598, 671–680 (1983).

    Article  MathSciNet  Google Scholar 

  30. E. Aarts, J. Korst, and W. Michiels, “Simulated annealing,” in: T. F. Gonzalez (ed.), Handbook of Approximation Algorithms and Metaheuristics, CRC Press, Boca Raton (FL) (2007), pp. 387–397.

    Google Scholar 

  31. L. F. Hulianytskyi, “Using algorithms of fast probabilistic modeling to solve combinatorial optimization problems,” in: Computational Mathematics [in Russian], V. M. Glushkov Inst. of Cybernetics NASU, No. 1, 64–72 (2004).

  32. H. R. Lourenço, O. Martin, and T. Stützle, “Iterated local search,” in: F. Glover and G. Kochenberger (eds.), Handbook of Metaheuristics, Kluwer Acad. Publ., Norwell (MA) (2002), pp. 321–353.

    Google Scholar 

  33. F. Glover, “Future paths for integer programming and links to artificial intelligence,” Comput. Oper. Res., No. 5, 533–549 (1986).

  34. F. Glover and M. Laguna, Tabu Search, Kluwer Acad. Publ., Norwell (MA) (1997).

    MATH  Google Scholar 

  35. A. Das and B. K. Chakrabarti (eds.), Quantum Annealing and Related Optimization Methods, Lect. Notes Physics, 679, Springer, Heidelberg (2005).

    MATH  Google Scholar 

  36. T. A. Feo and M. G. C. Resende, “A probabilistic heuristic for a computationally difficult set covering problem,” Oper. Res. Letters, 8, No. 2, 67–71 (1989).

    Article  MATH  MathSciNet  Google Scholar 

  37. L. Pitsoulis and M. G. C. Resende, “Greedy randomized adaptive search procedures,” in: P.M. Pardalos and M. G. C. Resende (eds.), Handbook of Applied Optimization, Oxford Univ. Press, Oxford (2002), pp. 168–181.

    Google Scholar 

  38. Yu. G. Stoyan and S. V. Yakovlev, Mathematical Models and Optimization Methods of Geometric Design [in Russian], Naukova Dumka, Kyiv (1986).

    Google Scholar 

  39. J. H. Holland, Adaptation in Natural and Artificial Systems, Univ. of Michigan Press, Ann Arbor (MI) (1975).

    Google Scholar 

  40. P. Moscato, “On evolution, search, optimization, genetic algorithms and martial arts: Towards memetic algorithms,” Techn. Rep., N C3P 826, California Inst. of Technology, Pasadena (CA) (1989).

  41. P. Moscato and C. Cotta, “Memetic algorithms,” in: T. F. Gonzalez (ed.), Handbook of Approximation Algorithms and Metaheuristics, CRC Press, Boca Raton (FL) (2007), pp. 412–423.

    Google Scholar 

  42. V. Cutello and G. Nicosia, “An immunological approach to combinatorial optimization problems,” in: Lect. Notes Comput. Sci., No. 2527 (2002), pp. 361–370.

  43. L. N. de Castro and J. Timmis, Artificial Immune Systems: A New Computational Intelligence Approach, Springer, London (2002).

    MATH  Google Scholar 

  44. F. Glover, M. Laguna, and R. Marti’,“Scatter search and path relinking: foundations and advanced designs,” in: G. Onwubolu and B. V. Babu (eds.), New Optimization Techniques in Engineering, Springer-Verlag, Berlin (2004), pp. 87–100.

    Google Scholar 

  45. H. Mühlenbein and G. Paab, “From recombination of genes to the estimation of distributions. I. Binary parameters,” in: Lect. Notes Comput. Sci.: Parallel Problem Solving from Nature, No. 4 (1996), pp. 178–187.

  46. P. Larrañnaga and J. A. Lozano (eds.), Estimation of Distribution Algorithms. A New Tool for Evolutionary Computation, Kluwer Acad. Publ., Boston (MA) (2001).

    Google Scholar 

  47. M. Dorigo, G. Di Caro, and L. M. Gambardella, “Ant algorithms for discrete optimization,” Artif. Life, 5, No. 2, 137–172 (1999).

    Article  Google Scholar 

  48. M. Dorigo and T. Stützle, Ant Colony Optimization, MIT Press, Cambridge (MA) (2004).

    MATH  Google Scholar 

  49. R. C. Eberhart and J. Kennedy, “Particle swarm optimization,” in: Proc. IEEE Intern. Conf. on Neural Networks, 4, IEEE Service Center, Piscataway (NJ) (1995), pp. 1942–1948.

    Google Scholar 

  50. M. Clerc, Particle Swarm Optimization, Wiley-Interscience, Hoboken (NJ) (2006).

    MATH  Google Scholar 

  51. D. Teodorovic, P. Lucic, G. Markovic, and M. D’Orco, “Bee colony optimization: principles and applications,” in: 8th Seminar on Neural Network Applications in Electrical Engineering, Belgrade, Serbia (2006), pp. 151–156.

  52. K. De Meyer, S. J. Nasuto, and J. M. Bishop, “Stochastic diffusion search: partial function evaluation in swarm intelligence dynamic optimisation,” in: A. Abraham, C. Grosam, and V. Ramos (eds.), Stigmergic Optimization, Springer–Verlag, Berlin (2006), pp. 185–208.

    Google Scholar 

  53. L. F. Hulianytskyi, “Deformation method in discrete optimization,” Issled. Oper. ASU, No. 34, 30–33 (1989).

  54. Yu. I. Zhuravlev, “Correct algebras over sets of incorrect (heuristic) algorithms,” Kibernetika, No. 4, 5–17 (1977).

  55. D. P. Bertsekas, J. N. Tsitsiklis, and C. Wu, “Rollout algorithms for combinatorial optimization,” J. Heuristics, No. 3, 245–262 (1997).

    Google Scholar 

  56. E. Burke, E. Hart, G. Kendall, et al., “Hyperheuristics: An emerging direction in modern search technology,” in: F. Glover and G. Kochenberger (eds.), Handbook of Metaheuristics, Kluwer Acad. Publ., Norwell (MA) (2003), pp. 457–474.

    Google Scholar 

  57. E. Ozcan, E. Bilgin, and E. E. Korkmaz, “A comprehensive analysis of hyper-heuristics,” Intelligent Data Analysis, 12, No. 1, 3–23 (2008).

    Google Scholar 

  58. L. F. Hulianytskyi, “A family of iterative discrete optimization algorithms,” in: Developing Mathematical and Engineering Tools in ACS [in Russian], IK AN USSR, Kyiv (1978), pp. 25–30.

    Google Scholar 

  59. F. Glover, “Ejection chains, reference structures and alternating path methods for traveling salesman problems,” Discrete Appl. Math., No. 65, 223–253 (1996).

  60. P. Morris, “The breakout method for escaping from local minima,” in: Proc. 11th Conf. on Artif. Intelligence, MIT Press, Cambridge (MA) (1993), pp. 40–45.

    Google Scholar 

  61. R. Battiti and M. Brunato, “Reactive search: Machine learning for memory-based heuristics,” Techn. Rep., N DIT-05-058, Univ. di Trento, Trento (2005).

  62. R. Battiti and R. Tecchiolli, “The reactive tabu search,” ORSA J. Computing, 6, No. 2, 126–140 (1994).

    MATH  Google Scholar 

  63. Y.-S. Ong, M.-H. Lim, N. Zhu, and K.-W. Wong, “Classification of adaptive memetic algorithms: A comparative study,” IEEE Trans. Systems, Man, and Cybernetics. Part B, Cybernetics, 36, No. 1, 141–152 (2006).

    Article  Google Scholar 

  64. M. Zlochin, M. Birattari, N. Meuleau, and M. Dorigo, “Model-based search for combinatorial optimization: A critical survey,” Ann. Oper. Res., No. 131, 373–395 (2004).

    Google Scholar 

  65. R. Y. Rubinstein and D. P. Kroese, The Cross-Entropy Method: A Unified Approach to Combinatorial Optimization, Monte Carlo Simulation, and Machine Learning, Springer-Verlag, New York (2004).

    MATH  Google Scholar 

  66. L. F. Hulianytskyi, “Developing cooperative metaheuristics,” in: Abstr. Int. Conf. “Problems of Decision Making under Uncertainties (PDMU–2009)” (April 27-30, 2009, Skhidnytsia, Ukraine), Kyiv (2009), pp. 90–91.

  67. E.-G. Talbi (ed.), Parallel Combinatorial Optimization, Wiley-Interscience, Hoboken (NJ) (2006).

    Google Scholar 

  68. E. Alba (ed.), Parallel Metaheuristics: A New Class of Algorithms, Wiley-Interscience, Hoboken (NJ) (2006).

    Google Scholar 

  69. C. Choi and J. Lee, “Chaotic local search algorithm,” Artif. Life Robotics, 2, No. 1, 41–47 (1998).

    Article  Google Scholar 

  70. S. Boettcher, A. G. Percus, “Extremal optimization: Methods derived from co-evolution,” in: Proc. Genetic and Evolutionary Computation Conf. (GECCO) (1999), pp. 825–832.

  71. C. Bourjot, V. Chevrier, and V. Thomas, “A new swarm mechanism based on social spiders colonies: from web weaving to region detection,” Web Intelligence and Agent Systems, 1, No. 1, 47–64 (2003).

    Google Scholar 

  72. H. Wakuya, “A new search method for combinatorial optimization problem inspired by the spin glass system,” Intern. Congress Series, No. 1291, 201–204 (2006).

  73. P. Cortés, J. M. Garci’a, J. Muñnuzuri, and L. Onieva, “Viral systems: A new bio-inspired optimisation approach,” Comput. Oper. Res., No. 35, 2840–2860 (2008).

    Google Scholar 

  74. M. G. H. Omran and M. Mahdavi, “Global-best harmony search,” Appl. Math. Comput., No. 198, 643–656 (2008).

Download references

Author information

Authors and Affiliations

  1. V. M. Glushkov Institute of Cybernetics, National Academy of Sciences of Ukraine, Kyiv, Ukraine

    I. V. Sergienko, L. F. Hulianytskyi & S. I. Sirenko

Authors
  1. I. V. Sergienko
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. L. F. Hulianytskyi
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. S. I. Sirenko
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to I. V. Sergienko.

Additional information

Translated from Kibernetika i Sistemnyi Analiz, No. 5, pp. 71–83, September–October 2009.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Sergienko, I.V., Hulianytskyi, L.F. & Sirenko, S.I. Classification of applied methods of combinatorial optimization. Cybern Syst Anal 45, 732–741 (2009). https://doi.org/10.1007/s10559-009-9134-0

Download citation

  • Received:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10559-009-9134-0

Keywords

Search

Navigation