|Títol||ILP-Based Reduced Variable Neighborhood Search for Large-Scale Minimum Common String Partition|
|Publication Type||Journal Article|
|Year of Publication||2018|
|Journal||Electronic Notes in Discrete Mathematics|
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.
- Quant a IIIA