CIS Colloquium, Feb 22, 2008, 11:00AM – 12:00PM, Wachman 447
Combining Multiple Heuristics Online
Dr. Matthew Streeter, Carnegie Mellon University
Heuristics for solving NP-hard problems often have complementary strengths and weaknesses. For example, algorithms developed by statistical physicists are extremely fast at solving satisfiable random Boolean formulae, while algorithms based on chronological backtracking are faster on unsatisfiable and structured formulae. What if we could combine several heuristics into a meta-heuristic with better mean running time, on-the-fly while solving a sequence of problem instances? This talk will present an online algorithm that can be used to do exactly that.
Specifically, this talk will present a near-optimal algorithm for the following online problem. Suppose you are given a pool of (randomized) heuristics and are fed, one at a time, a sequence of instances of some decision problem. To solve each instance, you may interleave the execution of the heuristics according to an arbitrary schedule, and may periodically restart each heuristic with a fresh random seed. Your goal is to minimize the average time required to solve each instance.
Using data from eight recent solver competitions, I will show that this online algorithm and its offline counterpart can be used to improve the performance of state-of-the-art solvers in a number of problem domains, including Boolean satisfiability, zero-one integer programming, A.I. planning, and theorem proving.
Matthew Streeter is currently a postdoctoral fellow at the Robotics Institute. He received his Ph.D. in Computer Science from Carnegie Mellon University in December, 2008. He received his B.S. and M.S. degrees in Computer Science from Worcester Polytechnic Institute in 2000 and 2001, respectively. Matthew’s current research interests include Artificial Intelligence, optimization, online algorithms, operations research, planning and scheduling, and evolutionary computation theory.