A Comparative Analysis of Two Matheuristics by Means of Merged Local Optima Networks



Blum C & Ochoa G (2021) A Comparative Analysis of Two Matheuristics by Means of Merged Local Optima Networks. European Journal of Operational Research, 290 (1), pp. 36-56.

We present a comparative analysis of two hybrid algorithms for solving combinatorial optimisation problems. The first one is a specific variant of an established family of techniques known as large neighbourhood search (LNS). The second one is a much more recent algorithm known as construct, merge, solve & adapt (CMSA). Both approaches generate, in different ways, reduced sub-instances of the tackled problem instance at each iteration. The experimental analysis is conducted on two NP-hard combinatorial subset selection problems: the multidimensional knapsack problem and minimum common string partition. The results support the intuition that CMSA has advantages over the LNS variant in the context of problems for which solutions contain rather few items. Moreover, they show that the opposite may be the case for problems in which solutions contain rather many items. The analysis is supported by a new way of visualising the trajectories of the compared algorithms in terms of merged monotonic local optima networks.

Management Science and Operations Research; Modelling and Simulation; Information Systems and Management

European Journal of Operational Research: Volume 290, Issue 1

FundersMinistry of Economy and Competitiveness (Spain)
Publication date01/04/2021
Publication date online13/08/2020
Date accepted by journal04/08/2020
PublisherElsevier BV

People (1)


Professor Gabriela Ochoa

Professor Gabriela Ochoa

Professor, Computing Science

Research centres/groups