English   español  
Please use this identifier to cite or link to this item: http://hdl.handle.net/10261/157744
logo share SHARE logo core CORE   Add this article to your Mendeley library MendeleyBASE

Visualizar otros formatos: MARC | Dublin Core | RDF | ORE | MODS | METS | DIDL
Exportar a otros formatos:


Large neighborhood search for the most strings with few bad columns problem

AuthorsLizarraga, Evelia; Blesa, Maria J.; Blum, Christian ; Raidl, Gunther
KeywordsMost strings with few bad columns
Integer linear programming
Large neighborhood search
Issue Date2017
CitationSoft Computing 21: 4901- 4915 (2017)
AbstractIn this work, we consider the following NP-hard combinatorial optimization problem from computational biology. Given a set of input strings of equal length, the goal is to identify a maximum cardinality subset of strings that differ maximally in a pre-defined number of positions. First of all, we introduce an integer linear programming model for this problem. Second, two variants of a rather simple greedy strategy are proposed. Finally, a large neighborhood search algorithm is presented. A comprehensive experimental comparison among the proposed techniques shows, first, that larger neighborhood search generally outperforms both greedy strategies. Second, while large neighborhood search shows to be competitive with the stand-alone application of CPLEX for small- and medium-sized problem instances, it outperforms CPLEX in the context of larger instances. © 2016, Springer-Verlag Berlin Heidelberg.
Identifiersdoi: 10.1007/s00500-016-2379-4
issn: 14327643
Appears in Collections:(IIIA) Artículos
Files in This Item:
File Description SizeFormat 
accesoRestringido.pdf15,38 kBAdobe PDFThumbnail
Show full item record
Review this work

WARNING: Items in Digital.CSIC are protected by copyright, with all rights reserved, unless otherwise indicated.