Learning dynamic algorithm portfolios

Matteo Gagliolo, Jürgen Schmidhuber

Research output: Chapter in Book/Report/Conference proceedingConference contribution

78 Scopus citations

Abstract

Algorithm selection can be performed using a model of runtime distribution, learned during a preliminary training phase. There is a trade-off between the performance of model-based algorithm selection, and the cost of learning the model. In this paper, we treat this trade-off in the context of bandit problems. We propose a fully dynamic and online algorithm selection technique, with no separate training phase: all candidate algorithms are run in parallel, while a model incrementally learns their runtime distributions. A redundant set of time allocators uses the partially trained model to propose machine time shares for the algorithms. A bandit problem solver mixes the model-based shares with a uniform share, gradually increasing the impact of the best time allocators as the model improves. We present experiments with a set of SAT solvers on a mixed SAT-UNSAT benchmark; and with a set of solvers for the Auction Winner Determination problem. © Springer Science+Business Media, Inc. 2007.
Original languageEnglish (US)
Title of host publicationAnnals of Mathematics and Artificial Intelligence
Pages295-328
Number of pages34
DOIs
StatePublished - Aug 1 2006
Externally publishedYes

ASJC Scopus subject areas

  • Artificial Intelligence
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Learning dynamic algorithm portfolios'. Together they form a unique fingerprint.

Cite this