Portal de Periódicos da CAPES

Quadratic Binary Programming Models in Computational Biology

2008; Volume: 3; Issue: 2 Linguagem: Inglês

1712-1582

Richard J. Forrester, Harvey J. Greenberg,

Algorithms and Data Compression

In this paper we formulate four problems in computational mo lecular biology as 0-1 quadratic programs. These problems are all NP-hard, and the current solution methods u sed in practice consist of heuristics or approximation algorithms tailored to each problem. Using test problems fr scientific databases, we address the question, “Can a general-purpose solver obtain good answers in reasonable t ime?” In addition, we use the latest heuristics as incumbent solutions to address the question, “Can a general-purpose s olver confirm optimality or find an improved solution in reasonable time?” Our computational experiments compar e four different reformulation methods: three forms of linearization and one form of quadratic convexification.