TY - JOUR
AU - Forrester, Richard John
AU - Greenberg, Harvey J
PY - 2008/07/21
Y2 - 2024/07/24
TI - Quadratic Binary Programming Models in Computational Biology
JF - Algorithmic Operations Research
JA - AOR
VL - 3
IS - 2
SE - Articles
DO -
UR - https://journals.lib.unb.ca/index.php/AOR/article/view/5930
SP -
AB - In this paper we formulate four problems in computational molecular biology as 0-1 quadratic programs. These problems are all NP-hard and the current solution methods used in practice consist of heuristics or approximation algorithms tailored to each problem. Using test problems from scientific databases, we address the question, “Can a general-purpose solver obtain good answers in reasonable time?” In addition, we use the latest heuristics as incumbent solutions to address the question, “Can a general-purpose solver confirm optimality or find an improved solution in reasonable time?” Our computational experiments compare four different reformulation methods: three forms of linearization and one form of quadratic convexification.
ER -