|
Título:
|
Construct, Merge, Solve and Adapt: Application to the repetition-free longest common subsequence problem
|
|
Autor/a:
|
Blum, Christian; Blesa Aguilera, Maria Josep
|
|
Otros autores:
|
Universitat Politècnica de Catalunya. Departament de Ciències de la Computació; Universitat Politècnica de Catalunya. ALBCOM - Algorismia, Bioinformàtica, Complexitat i Mètodes Formals |
|
Abstract:
|
In this paper we present the application of a recently proposed, general, algorithm for combinatorial optimization to the repetition-free longest common subsequence problem. The applied algorithm, which is labelled Construct, Merge, Solve & Adapt, generates sub-instances based on merging the solution components found in randomly constructed solutions. These sub-instances are subsequently solved by means of an exact solver. Moreover, the considered sub-instances are dynamically changing due to adding new solution components at each iteration, and removing existing solution components on the basis of indicators about their usefulness. The results of applying this algorithm to the repetition-free longest common subsequence problem show that the algorithm generally outperforms competing approaches from the literature. Moreover, they show that the algorithm is competitive with CPLEX for small and medium size problem instances, whereas it outperforms CPLEX for larger problem instances. |
|
Abstract:
|
Peer Reviewed |
|
Materia(s):
|
-Àrees temàtiques de la UPC::Informàtica::Informàtica teòrica
-Combinatorial optimization
-Hybrid algorithm
-Combining metaheuristics with ILP solvers
-Repetition-free longest common subsequence problem
-Optimització combinatòria |
|
Derechos:
|
|
|
Tipo de documento:
|
Artículo - Versión presentada
Artículo |
|
Compartir:
|
|
