Combining Multiple Heuristics Online

July 2007

Combining Multiple Heuristics Online

Authors:

M. Streeter, D. Golovin, and S. F. Smith

Abstract:

We present black-box techniques for learning how to interleave the execution of multiple heuristics in order to improve average-case performance. In our model, a user is given a set of heuristics whose only observable behavior is their running time. Each heuristic can compute a solution to any problem instance, but its running time varies across instances. The user solves each instance by interleaving runs of the heuristics according to a task-switching schedule. We present (i) exact and approximation algorithms for computing an optimal task-switching schedule offline, (ii) sample complexity bounds for learning a task-switching schedule from training data, and (iii) a no-regret strategy for selecting task-switching schedules online. We demonstrate the power of our results using data from recent solver competitions. We outline how to extend our results to the case in which the heuristics are randomized, and the user may periodically restart each heuristic with a fresh random seed.
@conference{Streeter-2007-120467,
author = {M. Streeter And D. Golovin And S. F. Smith},
title = {Combining Multiple Heuristics Online},
booktitle = {Proceedings of 22nd National Conference on Artificial Intelligence (AAAI '07)},
year = {2007},
month = {July},
volume = {2},
pages = {1197 - 1203},
}
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.