December 10, 2007
Matthew Streeter
3:30 PM, 4623 Wean Hall
Title: Using Online Algorithms to Solve NP-Hard Problems More Efficiently in Practice
Abstract:
This thesis develops online algorithms that can be used to solve a variety of NP-hard problems more efficiently in practice, by taking existing algorithms as input and adapting the algorithms to the sequence of problem instance(s) they are run on.
We first consider the following problem. We are given k algorithms, and are fed, one at a time, a sequence of problem instances to solve. We may solve each instance using any of the k algorithms, we may interleave the execution of the algorithms, and, if the algorithms are randomized, we may periodically restart them with a fresh random seed. We consider two objectives: minimizing the average CPU time required to solve the instances, and maximizing the number of instances solved in time at most T. We present an online algorithm that (asymptotically) performs near-optimally in terms of both objectives. In fact, this algorithm solves a more abstract online resource allocation problem, with applications to database query processing and sensor placement. Using data from eight recent solver competitions, we show that our 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, constraint satisfaction, and theorem proving.
We next consider algorithms that solve an optimization problem by making a sequence of calls to a decision procedure that answers questions of the form “Is there a solution of cost at most k?” We present a principled approach to determining the questions to ask and the maximum time to spend waiting for an answer to each question. Applying our approach to recent algorithms for A.I. planning and job shop scheduling allows them to find approximately optimal solutions more quickly.
Lastly, we develop algorithms for solving the max k-armed bandit problem, a variant of the classical k-armed bandit problem in which one seeks to maximize the highest payoff received on any single trial, rather than the cumulative payoff. Our max k-armed bandit strategy can be used to effectively allocate trials among multi-start heuristics for the resource-constrained project scheduling problem.
Thesis Committee:
Stephen F. Smith, Chair
Avrim Blum
Tuomas Sandholm
John N. Hooker
Carla P. Gomes, Cornell University
