E. Lizarraga, M. Blesa, C. Blum, G. Raidl:

"Large Neighborhood Search for the Most Strings with Few Bad Columns Problem";

Journal of Heuristics,21(2016), 1 - 15.

In 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.

http://dx.doi.org/10.1007/s00500-016-2379-4

Created from the Publication Database of the Vienna University of Technology.