[Zurück]

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), S. 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