×

zbMATH — the first resource for mathematics

Algorithm portfolios. (English) Zbl 0969.68047
Summary: 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, in a 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.

MSC:
68P10 Searching and sorting
Software:
Walksat
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Aldous, D.; Vazirani, U., Go with the winners algorithms, (), 492-501
[2] Alt, H.; Guibas, L.; Mehlhorn, K.; Karp, R.; Wigderson, A., A method for obtaining randomized algorithms with small tail probabilities, Algorithmica, 16, 4-5, 543-547, (1996) · Zbl 0857.68057
[3] Anderson, L., Completing partial Latin squares, Mathematisk fysiske meddelelser, 41, 23-69, (1985)
[4] Brelaz, D., New methods to color the vertices of a graph, Comm. ACM, 22, 4, 251-256, (1979) · Zbl 0394.05022
[5] Colbourn, C., Embedding partial Steiner triple systems is NP-complete, J. combin. theory A, 35, 100-105, (1983) · Zbl 0529.68020
[6] Dean, T.; Boddy, M., An analysis of time-dependent planning, (), 49-54
[7] Denes, J.; Keedwell, A., Latin squares and their applications, (1974), Akademiai Kiado Budapest/English Universities Press, London · Zbl 0283.05014
[8] Ertel, W.; Luby, M., Optimal parallelization of Las Vegas algorithms, (), 463-475
[9] Fujita, M.; Slaney, J.; Bennett, F., Automatic generation of some results in finite algebra, (), 52-57
[10] Gomes, C.P.; Selman, B., Algorithm portfolio design: theory vs. practice, (), 190-197
[11] Gomes, C.P.; Selman, B., Problem structure in the presence of perturbations, (), 221-227
[12] Gomes, C.P.; Selman, B.; Crato, N., Heavy-tailed distributions in combinatorial search, (), 121-135
[13] Gomes, C.P.; Selman, B.; Kautz, H., Boosting combinatorial search through randomization, (), 431-438
[14] Gomes, C.P.; Selman, B.; Crato, N.; Kautz, H., Heavy-tailed phenomena in satisfiability and constraint satisfaction problems, J. automat. reason., 24, 1-2, 67-100, (2000) · Zbl 0967.68145
[15] ()
[16] Huberman, B.; Lukose, R.; Hogg, T., An economics approach to hard computational problems, Science, 275, 51-54, (1997)
[17] Kautz, H.; Selman, B., Unifying SAT-based and graph-based planning, (), 318-325
[18] Kautz, H.; Walser, J., State-space planning by integer optimization, (), 526-533
[19] Lam, C.; Thiel, L.; Swiercz, S., The non-existence of finite projective planes of order 10, Can. J. math., XLI, 6, 1117-1123, (1994) · Zbl 0691.51003
[20] Luby, M.; Sinclair, A.; Zuckerman, D., Optimal speedup of Las Vegas algorithms, Inform. process. lett., 47, 173-180, (1993) · Zbl 0797.68139
[21] Motwani, R.; Raghavan, P., Randomized algorithms, (1995), Cambridge University Press Cambridge, England · Zbl 0849.68039
[22] Puget, J.F.; Leconte, M., Beyond the black box: constraints as objects, (), 513-527
[23] Russell, S.; Norvig, P., Artificial intelligence: A modern approach, (1995), Prentice Hall Englewood Cliffs, NJ · Zbl 0835.68093
[24] Salman, F.S.; Kalagnanam, J.R.; Davenport, A., Cooperative strategies for solving the bicriteria sparse multiple knapsack problem, (), 53-60
[25] Selman, B.; Kirkpatrick, S., Finite-size scaling of the computational cost of systematic search, Artificial intelligence, 81, 1-2, 273-295, (1996)
[26] ()
[27] Vossen, T.; Ball, M.; Lotem, A.; Nau, D., Integer programming models in AI planning, technical report, workshop on planning as combinatorial search (held in conjunction with AIPS-98), Pittsburgh, PA, (1999)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.