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

Christian Blum, Pedro Pinacho, Manuel Lopez-Ibanez, Jose A Lozano

Research output: Contribution to journalArticlepeer-review

488 Downloads (Pure)

Abstract

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 the literature as Generate-And-Solve, which is based on the following general idea. First, generate a reduced sub-instance of the original problem instance, in a way such that a solution to the sub-instance is also a solution to the original problem instance. Second, apply an exact solver to the reduced sub-instance in order to obtain a (possibly) high quality solution to the original problem instance. And third, make use of the results of the exact solver as feedback for the next algorithm iteration. The minimum common string partition problem and the minimum covering arborescence problem are chosen as test cases in order to demonstrate the application of the proposed algorithm. The obtained results show that the algorithm is competitive with the exact solver for small to medium size problem instances, while it significantly outperforms the exact solver for larger problem instances.
Original languageEnglish
Pages (from-to)75-88
Number of pages13
JournalComputers & Operations Research
Volume68
DOIs
Publication statusPublished - Apr 2016

Keywords

  • Metaheuristics; Exact solver; Hybrid algorithms; Minimum common string partition; Minimum covering arborescence

Fingerprint

Dive into the research topics of 'Construct, Merge, Solve & Adapt A new general algorithm for combinatorial optimization'. Together they form a unique fingerprint.

Cite this