Construct, Merge, Solve and Adapt: Application to Unbalanced Minimum Common String Partition

[EN]In this paper we present the application of a recently proposed, general, algorithm for combinatorial optimization to the unbalanced minimum common string partition problem. The algorithm, which is labelled Construct, Merge, Solve & Adapt, works on sub-instances of the tackled problem instances. At each iteration, the incumbent sub-instance is modified by adding solution components found in probabilistically constructed solutions to the tackled problem instance. Moreover, the incumbent sub-instance is solved to optimality (if possible) by means of an integer linear programming solver. Finally, seemingly unuseful solution components are removed from the incumbent sub-instance based on an ageing mechanism. The results obtained for the unbalanced minimum common string partition problem indicate that the proposed algorithm outperforms a greedy approach. Moreover, they show that the algorithm is competitive with CPLEX for problem instances of small and medium size, whereas it outperforms CPLEX for larger problem instances.his work was supported by project TIN2012-37930-C02-02 (Spanish Ministry for Economy and Competitiveness, FEDER funds from the European Union). Additionally, we acknowledge support from IKERBASQUE. Our experiments have been executed in the High Performance Computing environment managed by RDlab (http://rdlab.cs.upc.edu) and we would like to thank them for their support.Peer reviewe