Personal tools
You are here: Home Publications Solving the Double Digestion Problem as a Mixed-Integer Linear Program
Document Actions

Zhijun Wu and Yin Zhang (2001)

Solving the Double Digestion Problem as a Mixed-Integer Linear Program

Rice University, Department of Computational and Applied Mathematics, 6100 Main Street, Houston, TX 77005.

The double digestion problem for DNA restriction mapping is known to be NP-complete. Several approaches to the problem have been used including exhaustive search, simulated annealing, branch-and-bound. In this paper, we consider a mixed-integer linear programming formulation of the problem and show that with this formulation the problem can be solved efficiently to a fairly large size using state-of-the-art integer programming techniques. In particular, we present computational results obtained by using the CPLEX mixed-integer linear programming software on a set of randomly generated, large-scale double digestion problems.

by admin last modified 2007-12-10 21:06
« September 2010 »
Su Mo Tu We Th Fr Sa
1234
567891011
12131415161718
19202122232425
2627282930
 

Powered by Plone

LACSI Collaborators include:

Rice University LANL UH UNM UIUC UNC UTK