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.
展开▼
