Seminar: A Formalization of the Use of Bounds with Applications in Biology and Engineering
Sharlee Climer
Washington University in St. Louis
Department of Computer Science & Engineering
Faculty Host: Oliver Brock
"A Formalization of the Use of Bounds with Applications in Biology and Engineering"
In this presentation, we reflect on the history of the use of bounds and observe that previous research has focused on bounds derived from relaxations of constraints. However, bounds can be derived by tightening constraints, adding or deleting variables, or modifying the objective function. A formalization of the use of bounds as a two-step procedure, called limit crossing, is presented.
We used limit crossing to produce an original search strategy called cut-and-solve. We compared a simple, generic implementation of cut-and-solve with state-of-the-art solvers for seven real-world Traveling Salesman Problem classes. Cut-and-solve was faster when solving large instances for five of the problem classes and able to solve larger (sometimes substantially larger) instances for four classes.
We are currently implementing cut-and-solve for the biological problem of inferring haplotypes. A haplotype is a set of nucleotide sites gathered from a stretch of DNA. Genetic association studies use haplotypes to identify correlations between diseases and genes. There are two components to the haplotype inferencing problem: determining a biologically sound model and devising an algorithm that is capable of solving this model within reasonable time allowances. Our model for haplotype inferencing is based on characteristics that can be expected from human populations and we are using cut-and-solve to reduce computation time.
Sharlee Climer is a doctoral candidate at Washington University in St. Louis. Her advisors are Weixiong Zhang, in the department of Computer Science, and Alan Templeton, in the department of Biology. She holds degrees in Physics (BA), Civil/Structural Engineering (BS), and Computer Science (BS and MS). She is a computational scientist with a focus on combinatorial optimization problems. Sharlee has presented tutorials on her dissertatin work at both the 19th International Joint Conference on Artificial Intelligence (IJCAI'05) and the 20th National Conference on Artificial Intelligence (AAAI'05). She has served on program committees for the 20th National Conference on Artificial Intelligence (AAAI'05) and the 2002, 2005, and 2006 Olin Conferences. Sharlee is the recipient of a National Defense Science and Engineering Graduate (NDSEG) Fellowship and an Olin Fellowship.
