This paper deals with an NP-hard string problem from the bio-informatics field: the repetition-free longest common subsequence problem. This problem has enjoyed an increasing interest in recent years, which has resulted in the application of several pure as well as hybrid metaheuristics. However, the literature lacks a comprehensive comparison between those approaches. Moreover, it has been shown that general purpose integer linear programming solvers are very efficient for solving many of the problem instances that were used so far in the literature. Therefore, in this work we extend the available benchmark set, adding larger instances to which integer linear programming solvers cannot be applied anymore. Moreover, we provide a comprehensive comparison of the approaches found in the literature. Based on the results we propose a hybrid between two of the best methods which turns out to inherit the complementary strengths of both methods.

}, doi = {http://dx.doi.org/10.1007/s10732-017-9329-x}, author = {Blum, Christian and Blesa, Maria J} } @conference {56018, title = {On the comparison of CMSA versus LNS for solving Combinatorial Optimization problems with different solution sizes}, booktitle = {Metaheuristics International Conference (MIC)}, year = {2017}, pages = {676-678}, abstract = {Both, Construct, Merge Solve and Adapt (CMSA) and Large Neighborhood Search (LNS), are hybrid algorithms that are based on iteratively solving sub-instances of the original problem instances, if possible, to optimality. This is done by reducing the search space of the tackled problem instance in algorithm-specific ways which differ from one technique to the other. In this paper we provide first experimental evidence for the intuition that, conditioned by the way in which the search space is reduced, LNS should generally work better than CMSA in the context of problems in which solutions are rather large, and the opposite is the case for problems in which solutions are rather small. The size of a solution is hereby measured by the number of components of which the solution is composed, in comparison to the total number of solution components. In this ongoing work we are conducting experiments in the context of the multi-dimensional knapsack problem, the minimum-weight dominating set, and the single-source capacitated facility location problem.

}, author = {Liz{\'a}rraga, Evelia and Blesa, Maria J and Blum, Christian} } @proceedings {55973, title = {Construct, Merge, Solve and Adapt Versus Large Neighborhood Search for Solving the Multi-dimensional Knapsack Problem: Which One Works Better When?}, journal = {EvoCOP 2017 -- 17th European Conference on Evolutionary Computation in Combinatorial Optimization}, volume = {10197 (Lecture Notes in Computer Science)}, year = {2017}, pages = {60--74}, publisher = {Springer Verlag}, address = {Amsterdam}, abstract = {Both, Construct, Merge, Solve and Adapt (CMSA) and Large Neighborhood Search (LNS), are hybrid algorithms that are based on iteratively solving sub-instances of the original problem instances, if possible, to optimality. This is done by reducing the search space of the tackled problem instance in algorithm-specific ways which differ from one technique to the other. In this paper we provide first experimental evidence for the intuition that, conditioned by the way in which the search space is reduced, LNS should generally work better than CMSA in the context of problems in which solutions are rather large, and the opposite is the case for problems in which solutions are rather small. The size of a solution is hereby measured by the number of components of which the solution is composed, in comparison to the total number of solution components. Experiments are conducted in the context of the multi-dimensional knapsack problem.

}, doi = {https://doi.org/10.1007/978-3-319-55453-2_5}, author = {Liz{\'a}rraga, Evelia and Blesa, Maria J and Blum, Christian} }