Combinatorial Optimization Problems and Metaheuristics: Review, Challenges, Design, and Development
Source abstract
Abstract
In the past few decades, metaheuristics have demonstrated their suitability in addressing complex problems over different domains. This success drives the scientific community towards the definition of new and better-performing heuristics and results in an increased interest in this research field. Nevertheless, new studies have been focused on developing new algorithms without providing consolidation of the existing knowledge. Furthermore, the absence of rigor and formalism to classify, design, and develop combinatorial optimization problems and metaheuristics represents a challenge to the field’s progress. This study discusses the main concepts and challenges in this area and proposes a formalism to classify, design, and code combinatorial optimization problems and metaheuristics. We believe these contributions may support the progress of the field and increase the maturity of metaheuristics as problem solvers analogous to other machine learning algorithms.
Source: crossref · Quality: baseline
Research context
OpenAlex topics: Metaheuristic Optimization Algorithms Research · Scheduling and Timetabling Solutions · Advanced Multi-Objective Optimization Algorithms
SciVX discovery tags are terminology-based. OpenAlex topics are source-provided classifications.
Affiliations
Campus de Campolide, Nova Information Management School (NOVA IMS), Universidade NOVA de Lisboa, 1070-312 Lisboa, Portugal
Funding
Fundação para a Ciência e a Tecnologia · Javna Agencija za Raziskovalno Dejavnost RS
References (93)
Show source-provided references
1. Meta-Heuristic Algorithms for K-Means Clustering: A Review
2. A Survey on Optimization Metaheuristics10.1016/j.ins.2013.02.041 ↗
3. Fister, I., Yang, X.-S., Fister, I., Brest, J., and Fister, D. (2013). A Brief Review of Nature-Inspired Algorithms for Optimization. arXiv.
4. Metaheuristic Optimization Frameworks: A Survey and Benchmarking10.1007/s00500-011-0754-8 ↗
5. Metaheuristic-Based Extreme Learning Machines: A Review of Design Formulations and Applications10.1007/s13042-018-0833-6 ↗
6. Metaheuristic Research: A Comprehensive Survey10.1007/s10462-017-9605-z ↗
7. Metaheuristics: Review and Application10.1080/0952813X.2013.782347 ↗
8. Review of Optimization Techniques Applied for the Integration of Distributed Generation from Renewable Energy Sources10.1016/j.renene.2017.05.087 ↗
9. Brownlee, A.E.I., Woodward, J.R., and Swan, J. (2015, January 11–15). Metaheuristic Design Pattern: Surrogate Fitness Functions. Proceedings of the Companion Publication of the 2015 Annual Conference on Genetic and Evolutionary Computation, Madrid, Spain.10.1145/2739482.2768499 ↗
10. A Review of Simheuristics: Extending Metaheuristics to Deal with Stochastic Combinatorial Optimization Problems
11. Juan, A.A., Kelton, W.D., Currie, C.S.M., and Faulin, J. (2018, January 9–12). Simheuristics Applications: Dealing with Uncertainty in Logistics, Transportation, and Other Supply Chain Areas. Proceedings of the 2018 Winter Simulation Conference (WSC), Gothenburg, Sweden.10.1109/WSC.2018.8632464 ↗
12. Comprehensive Taxonomies of Nature- and Bio-Inspired Optimization: Inspiration versus Algorithmic Behavior, Critical Analysis and Recommendations10.1007/s12559-020-09730-8 ↗
13. Bio-Inspired Computation: Where We Stand and What’s Next10.1016/j.swevo.2019.04.008 ↗
14. Glover, F., and Kochenberger, G.A. (2003). Handbook of Metaheuristics, Springer.10.1007/b101874 ↗
15. Sorensen, K., Sevaux, M., and Glover, F. (2017). A History of Metaheuristics. arXiv.10.1007/978-3-319-07153-4_4-1 ↗
16. An Overview of Metaheuristics: Accurate and Efficient Methods for Optimisation10.1504/IJMHEUR.2014.068914 ↗
17. No Free Lunch Theorems for Optimization10.1109/4235.585893 ↗
18. Regarding the Rankings of Optimization Heuristics Based on Artificially-Constructed Benchmark Functions10.1016/j.ins.2014.11.023 ↗
19. Stegherr, H., Heider, M., and Hähner, J. (2020). Classifying Metaheuristics: Towards a Unified Multi-Level Classification System. Nat. Comput., 1–17.10.1007/s11047-020-09824-0 ↗
20. Swan, J., Adriaensen, S., Brownlee, A.E.I., Hammond, K., Johnson, C.G., Kheiri, A., Krawiec, F., Merelo, J.J., Minku, L.L., and Özcan, E. (2021). Metaheuristics “In the Large”. arXiv.10.1016/j.ejor.2021.05.042 ↗
21. Mitchell, T.M. (1997). Machine Learning, McGraw-Hill.
22. Antoniou, A., Murray, W., and Wright, M.H. (2007). Practical Optimization: Algorithms and Engineering Applications, Springer.
23. Ponce-Ortega, J.M., and Hernández-Pérez, L.G. (2019). Optimization of Process Flowsheets through Metaheuristic Techniques, Springer International Publishing.10.1007/978-3-319-91722-1 ↗
24. Tang, K.S. (2012). Multiobjective Optimization Methodology: A Jumping Gene Approach, CRC Press.
25. Metaheuristic Optimization10.4249/scholarpedia.11472 ↗
26. Yang, X.-S. (2014). Nature-Inspired Optimization Algorithms, Elsevier. [1st ed.].10.1016/B978-0-12-416743-8.00010-5 ↗
27. A Survey on Metaheuristics for Stochastic Combinatorial Optimization10.1007/s11047-008-9098-4 ↗
28. Stork, J., Eiben, A.E., and Bartz-Beielstein, T. (2020). A New Taxonomy of Continuous Global Optimization Algorithms. Nat. Comput., 1–24.10.1007/s11047-020-09820-4 ↗
29. Gendreau, M., and Potvin, J.-Y. (2019). Handbook of Metaheuristics, Springer International Publishing.10.1007/978-3-319-91086-4 ↗
30. Korte, B., and Vygen, J. (2012). Combinatorial Optimization, Springer. Algorithms and Combinatorics.10.1007/978-3-642-24488-9 ↗
31. Quadratic Assignment Problem and Its Relevance to the Real World: A Survey
32. Theory of Problem Solving10.1016/j.sbspro.2015.01.970 ↗
33. Sengupta, R., Gupta, A., and Dutta, J. (2016). Metaheuristic Techniques. Decision Sciences, CRC Press.10.1201/9781315183176 ↗
34. Hybrid Metaheuristics: An Introduction10.1007/978-3-540-78295-7_1 ↗
35. Combinatorial Optimization:Algorithms and Complexity10.1109/TASSP.1984.1164450 ↗
36. Metaheuristics in Combinatorial Optimization: Overview and Conceptual Comparison10.1145/937503.937505 ↗
37. A Critical Review of Discrete Filled Function Methods in Solving Nonlinear Discrete Optimization Problems
38. Multi-Objective Metaheuristics for Discrete Optimization Problems: A Review of the State-of-the-Art10.1016/j.asoc.2020.106382 ↗
39. Problems of Discrete Optimization: Challenges and Main Approaches to Solve Them10.1007/s10559-006-0086-3 ↗
40. Interactive Multiobjective Optimization: A Review of the State-of-the-Art10.1109/ACCESS.2018.2856832 ↗
41. Sawaragi, Y., Nakayama, H., and Tanino, T. (1985). Theory of Multiobjective Optimization, Acadamic Press.
42. Peitz, S., and Dellnitz, M. (2018). A Survey of Recent Trends in Multiobjective Optimal Control—Surrogate Models, Feedback Control and Objective Reduction. Math. Comput. Appl., 23.10.20944/preprints201805.0221.v2 ↗
43. Boissier, M., Schlosser, R., and Uflacker, M. (2018, January 16–19). Hybrid Data Layouts for Tiered HTAP Databases with Pareto-Optimal Data Placements. Proceedings of the 2018 IEEE 34th International Conference on Data Engineering (ICDE), Paris, France.10.1109/ICDE.2018.00028 ↗
44. Chinchuluun, A., Pardalos, P.M., Migdalas, A., and Pitsoulis, L. (2008). Pareto Optimality, Game Theory and Equilibria, Springer. Springer Optimization and Its Applications.10.1007/978-0-387-77247-9 ↗
45. Pareto or Non-Pareto: Bi-Criterion Evolution in Multiobjective Optimization10.1109/TEVC.2015.2504730 ↗
46. A Hybrid Meta-Heuristic for Multi-Objective Optimization: MOSATS10.1007/s10852-006-9041-6 ↗
47. Metaheuristic Search Techniques for Multi-Objective and Stochastic Problems: A History of the Inventions of Walter J. Gutjahr in the Past 22 Years10.1007/s10100-018-0522-2 ↗
48. Bonyadi, M.R., Michalewicz, Z., Przybylek, M.R., and Wierzbicki, A. (2014, January 12–16). Socially Inspired Algorithms for the Travelling Thief Problem. Proceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation, Vancouver, BC, Canada.10.1145/2576768.2598367 ↗
49. Przybylek, M.R., Wierzbicki, A., and Michalewicz, Z. (2016, January 20–24). Multi-Hard Problems in Uncertain Environment. Proceedings of the Genetic and Evolutionary Computation Conference 2016, Denver, CO, USA.10.1145/2908812.2908814 ↗
50. Decomposition Algorithms for a Multi-Hard Problem10.1162/evco_a_00211 ↗
51. Oliva, D., Copado, P., Hinojosa, S., Panadero, J., Riera, D., and Juan, A.A. (2020). Fuzzy Simheuristics: Solving Optimization Problems under Stochastic and Uncertainty Scenarios. Mathematics, 8.10.3390/math8122240 ↗
52. Neumann, F., and Witt, C. (2010). Combinatorial Optimization and Computational Complexity, Springer.10.1007/978-3-642-16544-3_2 ↗
53. A Comprehensive Review of Firefly Algorithms10.1016/j.swevo.2013.06.001 ↗
54. Heuristics and Metaheuristics Approaches for Facility Layout Problems: A Survey
55. A Review of Metaheuristic Techniques for Optimal Integration of Electrical Units in Distribution Networks10.1109/ACCESS.2020.3048438 ↗
56. Almonacid, B. (2021). AutoMH: Automatically Create Evolutionary Metaheuristic Algorithms Using Reinforced Learning. Math. Comput. Sci.10.20944/preprints202101.0048.v1 ↗
57. Metaheuristics-the Metaphor Exposed10.1111/itor.12001 ↗
58. Exploration and Exploitation in Evolutionary Algorithms: A Survey10.1145/2501654.2501658 ↗
59. Xu, J., and Zhang, J. (2014, January 28–30). Exploration-Exploitation Tradeoffs in Metaheuristics: Survey and Analysis. Proceedings of the 33rd Chinese Control Conference, Nanjing, China.10.1109/ChiCC.2014.6896450 ↗
60. A Comprehensive Database of Nature-Inspired Algorithms10.1016/j.dib.2020.105792 ↗
61. Lones, M.A. (2014, January 12–16). Metaheuristics in Nature-Inspired Algorithms. Proceedings of the Companion Publication of the 2014 Annual Conference on Genetic and Evolutionary Computation, Vancouver, BC, Canada.10.1145/2598394.2609841 ↗
62. Mitigating Metaphors: A Comprehensible Guide to Recent Nature-Inspired Algorithms10.1007/s42979-019-0050-8 ↗
63. Akhtar, A. (2019). Evolution of Ant Colony Optimization Algorithm—A Brief Literature Review. arXiv.
64. Parameter Estimation in Biochemical Pathways: A Comparison of Global Optimization Methods10.1101/gr.1262503 ↗
65. A New Cooperative Framework for Parallel Trajectory-Based Metaheuristics10.1016/j.asoc.2018.01.022 ↗
66. A Taxonomy of Hybrid Metaheuristics10.1023/A:1016540724870 ↗
67. Talbi, E.-G. (2009). Metaheuristics: From Design to Implementation, John Wiley & Sons.10.1002/9780470496916 ↗
68. An Adaptive Multi-Population Optimization Algorithm for Global Continuous Optimization10.1109/ACCESS.2021.3054636 ↗
69. A Taxonomy for Management and Optimization of Multiple Resources in Edge Computing
70. A Survey of Nature Inspired Algorithms
71. Swarm Intelligence: A Review of Algorithms10.1007/978-3-319-50920-4_19 ↗
72. Rajakumar, R., Dhavachelvan, P., and Vengattaraman, T. (2016, January 21–22). A Survey on Nature Inspired Meta-Heuristic Algorithms with Its Domain Specifications. Proceedings of the 2016 International Conference on Communication and Electronics Systems (ICCES), Coimbatore, India.10.1109/CESYS.2016.7889811 ↗
73. Crespo-Cano, R., Cuenca-Asensi, S., Fernández, E., and Martínez-Álvarez, A. (2019). Metaheuristic Optimisation Algorithms for Tuning a Bioinspired Retinal Model. Sensors, 19.10.3390/s19224834 ↗
74. A Bio-Inspired, Incremental Clustering Algorithm for Semantics-Based Web Service Discovery
75. Application of Bio-Inspired Algorithms in Maximum Power Point Tracking for PV Systems under Partial Shading Conditions—A Review10.1016/j.rser.2017.08.034 ↗
76. Unsupervised Feature Selection Based on Bio-Inspired Approaches10.1016/j.swevo.2019.100618 ↗
77. A Survey on New Generation Metaheuristic Algorithms10.1016/j.cie.2019.106040 ↗
78. Survey of Metaheuristic Algorithms for Combinatorial Optimization
79. Bhattacharyya, S. (2018). Hybrid Metaheuristics for Image Analysis, Springer International Publishing.10.1007/978-3-319-77625-5 ↗
80. Hybrid Metaheuristics10.1007/978-1-4419-1644-0_9 ↗
81. Muthuraman, S., and Venkatesan, V.P. (2017, January 2–4). A Comprehensive Study on Hybrid Meta-Heuristic Approaches Used for Solving Combinatorial Optimization Problems. Proceedings of the 2017 World Congress on Computing and Communication Technologies (WCCCT), Tiruchirappalli, India.10.1109/WCCCT.2016.53 ↗
82. Hybrid Meta-Heuristics for Combinatorial Optimization10.1007/s10601-015-9209-7 ↗
83. A Survey of Hybrid Metaheuristics for the Resource-Constrained Project Scheduling Problem10.1016/j.ejor.2019.01.063 ↗
84. Birattari, M., Paquete, L., and Stützle, T. (2001). Classification of Metaheuristics and Design of Experiments for the Analysis of Components, Darmstadt University of Technology.
85. Designing and Reporting on Computational Experiments with Heuristic Methods10.1007/BF02430363 ↗
86. How to Present a Paper on Experimental Work with Algorithms10.1145/337885.337899 ↗
87. A Survey of Automatic Parameter Tuning Methods for Metaheuristics10.1109/TEVC.2019.2921598 ↗
88. Weinand, J.M., Sörensen, K., Segundo, P.S., Kleinebrahm, M., and McKenna, R. (2021). Research Trends in Combinatorial Optimization. Int. Trans. Oper. Res.10.1111/itor.12996 ↗
89. Recent Advances in Metaheuristic Algorithms: Does the Makara Dragon Exist?10.1007/s11227-015-1592-8 ↗
90. Since CEC 2005 Competition on Real-Parameter Optimisation: A Decade of Research, Progress and Comparative Analysis’s Weakness10.1007/s00500-016-2471-9 ↗
91. Is a Comparison of Results Meaningful from the Inexact Replications of Computational Experiments?10.1007/s00500-014-1493-4 ↗
92. Common Benchmark Functions for Metaheuristic Evaluation: A Review
93. A Re-characterization of Hyper-Heuristics10.1007/978-3-319-58253-5_5 ↗