A portfolio approach to algorithm select
Kevin Leyton‐Brown, Eugene Nudelman, Galen Andrew, Jim McFadden, Yoav Shoham · International Joint Conference on Artificial Intelligence · 2003
Although some algorithms are better than others on average, there is rarely a best algorithm for a given problem. Instead, it is often the case that different algorithms perform well on different problem instances. Not surprisingly, this phenomenon is most pronounced among algorithms for solving NP-Hard problems, because runtimes for these algorithms are often highly variable from instance to instance. When algorithms exhibit high runtime variance, one is faced with the problem of deciding which algorithm to use; in 1976 Rice dubbed this the “algorithm selection problem” [8]. In the nearly three decades that have followed, the issue of algorithm selection has failed to receive widespread attention, though of course some excellent work does exist. By far, the most common approach to algorithm selection has been to measure different algorithms’ performance on a given problem distribution, and then to use only the algorithm having the lowest average runtime. This “winner-take-all” approach has driven recent advances in algorithm design and refinement, but has resulted in the neglect of many algorithms that, while uncompetitive on average, may offer excellent performance on particular problem instances. Our consideration of the algorithm selection literature, and our dissatisfaction with the winner-take-all approach, has led us to ask the following two questions. First, what general techniques can we use to perform per-instance (rather than per-distribution) algorithm selection? Second, once we have rejected the notion of winner-take-all algorithm evaluation, how ought novel algorithms to be evaluated? We offer the following answers: