Algorithm portfolios

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

Return

Algorithm portfolios

2001-02-01

274

Carla P. Gomes

Bart Selman

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

Original

Save

View PDF

Abstract

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.

Keywords:

algorithm portfolios

randomized algorithms

cost profiles

anytime algorithms

empirical evaluation

AI Summary

Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.