Combining Multiple Heuristics Online
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.
Cite
Text
Streeter et al. "Combining Multiple Heuristics Online." AAAI Conference on Artificial Intelligence, 2007.Markdown
[Streeter et al. "Combining Multiple Heuristics Online." AAAI Conference on Artificial Intelligence, 2007.](https://mlanthology.org/aaai/2007/streeter2007aaai-combining/)BibTeX
@inproceedings{streeter2007aaai-combining,
title = {{Combining Multiple Heuristics Online}},
author = {Streeter, Matthew J. and Golovin, Daniel and Smith, Stephen F.},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2007},
pages = {1197-1203},
url = {https://mlanthology.org/aaai/2007/streeter2007aaai-combining/}
}