Search and Optimization

Many problems require searching through an exponentially large space of possibilities to find a feasible or optimal solution. Sometimes these problems allow efficient algorithms, whereas in other cases sophisticated techniques from areas such as search, integer programming, and branch decomposition can still be quite effective in practice. Researchers at Duke have used these techniques for solving large games, allocating resources efficiently, ranking alternatives, dead-end elimination, constraint satisfaction in protein structure determination, predicting antimicrobial resistance, and design of therapeutic proteins that are currently in clinical trials.