Construct, Merge, Solve & Adapt A new general algorithm for combinatorial optimization

[EN]This paper describes a general hybrid metaheuristic for combinatorial optimization labelled Construct,Merge, Solve & Adapt. The proposed algorithm is a specific instantiation of a framework known from theliterature as Generate-And-Solve, which is based on the following general idea. First, generate a reducedsub-instance of the original problem instance, in a way such that a solution to the sub-instance is also asolution to the original problem instance. Second, apply an exact solver to the reduced sub-instance inorder to obtain a (possibly) high quality solution to the original problem instance. And third, make use ofthe results of the exact solver as feedback for the next algorithm iteration. The minimum common stringpartition problem and the minimum covering arborescence problem are chosen as test cases in order todemonstrate the application of the proposed algorithm. The obtained results show that the algorithm iscompetitive with the exact solver for small to medium size problem instances, while it significantlyoutperforms the exact solver for larger problem instancesC. Blum was supported by project TIN2012-37930-02 of the Spanish Government. In addition, support is acknowledged from IKERBASQUE (Basque Foundation for Science). J.A. Lozano was partially supported by the IT609-13 program (Basque Government) and project TIN2013-41272P (Spanish Ministry of Science and Innovation)Peer reviewe