Algorithm portfolios

Carla P. Gomes

doi:10.1016/S0004-3702(00)00081-3

2001-02-01

274

Carla P. Gomes

Bart Selman

DOI：10.1016/S0004-3702(00)00081-3

原文链接

查看原文

摘要

En 中文

Stochastic algorithms are among the best methods for solving computationally hard search and reasoning problems. The run time of such procedures can vary significantly from instance to instance and, when using different random seeds, on the same instance. One can take advantage of such differences by combining several algorithms into a portfolio, and running them in parallel or interleaving them on a single processor. We provide an evaluation of the portfolio approach on distributions of hard combinatorial search problems. We show under what conditions the portfolio approach can have a dramatic computational advantage over the best traditional methods. In particular, we will see how, ina portfolio setting, it can be advantageous to use a more risk-seeking strategy with a high variance in run time, such as a randomized depth-first search approach in mixed integer programming versus the more traditional best-bound approach. We hope these insights will stimulate the development of novel randomized combinatorial search methods. (C) 2001 Published by Elsevier Science B.V.

Keyword:

algorithm portfolios

randomized algorithms

cost profiles

anytime algorithms

empirical evaluation