TitleMinimum Common String Partition: On Solving Large-Scale Problem Instances
Publication TypeJournal Article
Year of Publication2020
AuthorsBlum C
JournalInternational Transactions in Operational Research

Minimum common string partition is an NP-hard combinatorial optimization problem from the bioinformatics field. The current state-of-the-art algorithm is a hybrid technique known as construct, merge, solve & adapt (CMSA). This algorithm combines two main algorithmic components: generating solutions in a probabilistic way, and solving reduced subinstances obtained from the tackled problem instances, if possible, to optimality. However, the CMSA algorithm as described in (Blum et al., 2016) was not aimed for the application to very large problem instances. Therefore, in this paper we present a technique that makes CMSA, and other available algorithms for this problem, applicable to problem instances that are about one order of magnitude larger than the so far largest considered problem instances. Moreover, a reduced variable neighborhood search (RVNS) for solving the tackled problem, based on integer programming, is introduced. The experimental results show that the modified CMSA algorithm is very strong for problem instances based on rather small alphabets. With growing alphabet size, it turns out that RVNS has a growing advantage over CMSA.