Draft:Construct, Merge, Solve and Adapt

Construct Merge Solve and Adapt (CMSA) is a Metaheuristic for Combinatorial optimization introduced by Blum et al. in 2016. It employs an exact solver, which is used at each iteration for solving a sub-instance of the problem instance under consideration. This sub-instance is modified throughout the execution of the algorithm, with the objective of having high-quality solutions contained in it. An iteration of the algorithm can be split into four steps, which give its name: Construct, Merge, Solve and Adapt.

Description

S_{bsf} = null, C' = \emptyset
while CPU time limit not reached 
    for i = 1,...,n_a
        S = probabilistic_solution_generation(C)
        for c \in C and c\not\in C
            age[c] = 0
            C'=C'\cup\{c\}
        end for
    end for
    <math>S'_{opt}</math> = apply_exact_solver(C')
    if S'_{opt} is better than S_{bsf} then S_{bsf} = S'_{opt}
    adapt(C', S'_{opt}, age)
end while