Ir al contenido

Documat

Construct, merge, solve and adapt

  • Christian Blum [1]
    1. [1] Artificial Intelligence Research Institute (IIIA-CSIC), Campus UAB, Bellaterra, Spain
  • Localización: Top, ISSN-e 1863-8279, ISSN 1134-5764, Vol. 33, Nº. Extra 2, 2025 (Ejemplar dedicado a: Metaheuristics), págs. 357-377
  • Idioma: inglés
  • DOI: 10.1007/s11750-024-00689-5
  • Enlaces
  • Resumen

    • The CMSA algorithm for combinatorial optimization is a hybrid technique based on repeatedly solving sub-instances to the original problem instance. The incumbent sub-instance is extended at each iteration by the probabilistic generation of valid solutions to the original problem instance and by adding the components found in these solutions to the sub-instance. In addition, the incumbent sub-instance is reduced at each iteration by removing seemingly useless solution components. In recent years the usefulness of the CMSA algorithm has been shown by a range of applications to different combinatorial optimization problems. In this work, we provide a gentle introduction to CMSA by describing the application to the so-called minimum global domination problem as an example

  • Referencias bibliográficas
    • Akbay MA, Kalayci CB, Blum C (2022a) Application of CMSA to the electric vehicle routing problem with time windows, simultaneous pickup and...
    • Akbay MA, López Serrano A, Blum C (2022) A self-adaptive variant of CMSA: application to the minimum positive influence dominating set problem....
    • Akbay MA, Kalayci CB, Blum C (2023) Application of Adapt-CMSA to the two-echelon electric vehicle routing problem with simultaneous pickup...
    • Allan RB, Laskar R (1978) On domination and independent domination numbers of a graph. Disc Math 23(2):73–76
    • Alves Viana LG (2022) Uma meta-heurística híbrida para o problema de cobertura de discos ponderados. Bachelor’s thesis, Universidade Federal...
    • Arora D, Maini P, Pinacho-Davidson P, et al (2019) Route planning for cooperative air-ground robots with fuel constraints: an approach based...
    • Blum C (2020) Minimum common string partition: on solving large-scale problem instances. Int Trans Oper Res 27(1):91–111
    • Blum C, Blesa MJ (2016) Construct, merge, solve and adapt: application to the repetition-free longest common subsequence problem. In: Evolutionary...
    • Blum C, Blesa MJ (2018) A comprehensive comparison of metaheuristics for the repetition-free longest common subsequence problem. J Heurist...
    • Blum C, Gambini Santos H (2019) Generic CP-supported CMSA for binary integer linear programs. In: Hybrid Metaheuristics: 11th International...
    • Blum C, Ochoa G (2021) A comparative analysis of two matheuristics by means of merged local optima networks. Eur J Oper Res 290(1):36–56
    • Blum C, Pereira J (2016) Extension of the CMSA algorithm: an LP-based way for reducing sub-instances. Proc Gen Evolut Comput Confer 2016:285–292
    • Blum C, Pinacho P, López-Ibáñez M et al (2016) Construct, merge, solve and adapt: a new general algorithm for combinatorial optimization....
    • Brigham RC, Dutton RD (1990) Factor domination in graphs. Disc Math 86(1–3):127–136
    • Calvo B, Santafé G (2016) scmamp: statistical comparison of multiple algorithms in multiple problems. R J 8(1)
    • Demšar J (2006) Statistical comparisons of classifiers over multiple data sets. J Mach Learn Res 7:1–30
    • Desormeaux WJ, Gibson PE, Haynes TW (2015) Bounds on the global domination number. Quaest Math 38(4):563–572
    • Djukanovi´c M, Kartelj A, Blum C (2023) Self-adaptive CMSA for solving the multidimensional multi-way number partitioning problem. Expert...
    • Dupin N, Talbi EG (2021) Matheuristics to optimize refueling and maintenance planning of nuclear power plants. J Heurist 27(1–2):63–105
    • Enciso RI, Dutton RD (2008) Global domination in planar graphs. J Combin Math Combin Comput 66:273– 278
    • Erdös P, Rényi A (1959) On random graphs I. Publ Math Debrecen 6(290–297):18
    • Ferrer J, Chicano F, Ortega-Toro JA (2021) CMSA algorithm for solving the prioritized pairwise test data generation problem in software product...
    • Garcia S, Herrera F (2008) An extension on “statistical comparisons of classifiers over multiple data sets” for all pairwise comparisons....
    • García S, Fernández A, Luengo J et al (2010) Advanced nonparametric tests for multiple comparisons in the design of experiments in computational...
    • Ghirardi M, Salassa F (2022) A simple and effective algorithm for the maximum happy vertices problem. Top 30(1):181–193
    • Hawa A (2020) Exact and evolutionary algorithms for the score-constrained packing problem. PhD thesis, Cardiff University
    • Lewis R, Thiruvady D, Morgan K (2019) Finding happiness: an analysis of the maximum happy vertices problem. Comput Oper Res 103:265–276
    • Lizárraga E, Blesa MJ, Blum C (2017) Construct, merge, solve and adapt versus large neighborhood search for solving the multi-dimensional...
    • López-Ibáñez M, Dubois-Lacoste J, Cáceres LP et al (2016) The irace package: iterated racing for automatic algorithm configuration. Oper Res...
    • Martí R, Parreño F, Mortes J (2024) Mathematical models and solving methods for diversity and equity optimization. J Heurist. (In press)
    • de Oliveira EB, da Silva Batista M, Pinheiro RGS (2023) Uma abordagem híbrida CMSA para o problema da cadeia de caracteres mais próxima. In:...
    • Parra Inza E, Vakhania N, Sigarreta Almira JM, et al (2023) Algorithms for the global domination problem. Tech. rep. arXiv preprint arXiv:2312.04526
    • Pinacho Davidson P, Blum C, Lozano JA (2018) The weighted independent domination problem: integer linear programming models and metaheuristic...
    • Pinacho-Davidson P, Bouamama S, Blum C (2019) Application of CMSA to the minimum capacitated dominating set problem. In: Proceedings of the...
    • Pisinger D, Ropke S (2010) Large neighborhood search. Springer, Boston, MA, pp 399–419. https://doi. org/10.1007/978-1-4419-1665-5_13
    • Rosati RM, Kletzander L, Blum C, et al (2022) Construct, merge, solve and adapt applied to a bus driver scheduling problem with complex break...
    • Rosati RM, Bouamama S, Blum C (2023) Construct, merge, solve and adapt applied to the maximum disjoint dominating sets problem. In: Di Gaspero...
    • Rosati RM, Bouamama S, Blum C (2024) Multi-constructor CMSA for the maximum disjoint dominating sets problem. Comput Oper Res 161:106450
    • Sampathkumar E (1989) The global domination number of a graph. J Math Phys Sci 23:377–385
    • Thiruvady D, Lewis R (2022) Recombinative approaches for the maximum happy vertices problem. Swarm Evolut Comput 75:101188
    • Thiruvady D, Blum C, Ernst AT (2019) Maximising the net present value of project schedules using CMSA and parallel ACO. In: Hybrid Metaheuristics:...
    • Zhou J, Zhang P (2024) Simple heuristics for the rooted max tree coverage problem. In: Wu W, Guo J (eds) Combinatorial optimization and applications....
Fundación Dialnet

Mi Documat

Opciones de artículo

Opciones de compartir

Opciones de entorno