The Hybrid Metaheuristic CMSA

Christian Blum () and Jaume Reixach ()
Additional contact information
Christian Blum: Artificial Intelligence Research Institute (IIIA-CSIC)
Jaume Reixach: Artificial Intelligence Research Institute (IIIA-CSIC)

Chapter 14 in Handbook of Heuristics, 2025, pp 363-386 from Springer

Abstract: Abstract In this chapter, we describe the Construct, Merge, Solve & Adapt (CMSA) algorithm, a metaheuristic framework designed to address hard combinatorial optimization problems. CMSA combines the probabilistic construction of solutions within an adaptive, iterative process with solution merging and exact optimization techniques. The algorithm probabilistically constructs solutions through heuristic methods, which are then merged into a reduced subproblem. This subproblem is solved using exact optimization approaches, mostly integer programming. Based on the feedback from this solving phase, the algorithm adapts its construction and merging strategies in subsequent iterations, progressively finding solutions of improving quality over time. CMSA’s hybrid nature allows it to balance between the speed of heuristic construction and the accuracy of exact methods, making it particularly effective for large-scale problems. After a general description of standard CMSA, we outline a recent self-adaptive variant and a variant that uses reinforcement learning to improve the search process. All three algorithm variants are applied to the classical maximum independent set problem. Moreover, an experimental evaluation is provided to show their comparative behavior.

Keywords: Hybrid metaheuristic; Combinatorial optimization; Maximum independent set (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-3-032-00385-0_79

Ordering information: This item can be ordered from
http://www.springer.com/9783032003850

DOI: 10.1007/978-3-032-00385-0_79

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().