ILP-Based Reduced Variable Neighborhood Search for Large-Scale Minimum Common String Partition

The minimum common string partition problem is a challenging NP-hard optimization problem from the bioinformatics field. In this work we, first, present a modification which allows to apply the current state-of-the-art technique from the literature to much larger problem instances. Second, also based on the introduced modification, we develop a reduced variable neighborhood search algorithm for tackling large-scale problem instances. The skaking step of this algorithm destroys the incumbent solution partially, in a randomized way, and generates a complete solution on the basis of the partial solution by means of integer linear programming techniques. The proposed algorithm is compared to the state-of-the-art technique from the literature. The results show that the proposed algorithm consistently outperforms the state-of-the-art algorithm in the context of problem instances based on large alphabet sizes. © 2018 Elsevier B.V.This work was funded by proyect TIN2015-66863-C2-1-R (Spanish Ministry for Economy and Competitiveness, FEDER funds from the European Union)Peer Reviewe