Vorträge und Posterpräsentationen (mit Tagungsband-Eintrag):
E. Lizarraga, M. Blesa, C. Blum, G. Raidl:
"On Solving the Most Strings With Few Bad Columns Problem: An ILP Model and Heuristics";
Vortrag: INISTA 2015,
Madrid, Spain;
02.08.2015
- 05.08.2015; in: "Innovations in Intelligent Systems and Applications (INISTA), 2015 International Symposium on",
D. Camacho et al. (Hrg.);
(2015),
ISBN: 978-1-4673-7751-5;
S. 1
- 8.
Kurzfassung englisch:
The most strings with few bad columns problem is an NP-hard combinatorial optimization problem from the bioinformatics field. This paper presents the first integer linear programming model for this problem. Moreover, a simple greedy heuristic and a more sophisticated extension, namely a greedy-based pilot method, are proposed. Experiments show that, as expected, the greedy-based pilot method improves over the greedy strategy. For problem instances of small and medium size the best results were obtained by solving the integer linear programming model by CPLEX, while the greedy-based pilot methods scales much better to large problem instances.
Schlagworte:
most strings with few bad columns problem, heuristics, ilp model
Erstellt aus der Publikationsdatenbank der Technischen Universität Wien.