A probabilistic architecture for algorithm portfolios

Heuristic algorithms for logical reasoning are increasingly successful on computationally difficult problems such as satisfiability, and these solvers enable applications from circuit verification to software synthesis. Whether a problem instance can be solved, however, often depends in practice on whether the correct solver was selected and its parameters appropriately set. Algorithm portfolios leverage past performance data to automatically select solvers likely to perform well on a given instance. Existing portfolio methods typically select only a single solver for each instance. This dissertation develops and evaluates a more general portfolio method, one that computes complete solver execution schedules, including repeated runs of nondeterministic algorithms, by explicitly incorporating probabilistic reasoning into its operation. This modular architecture for probabilistic portfolios (MAPP) includes novel solutions to three issues central to portfolio operation: first, it estimates solver performance distributions from limited data by constructing a generative model; second, it integrates domain-specific information by predicting instances on which solvers exhibit similar performance; and, third, it computes execution schedules using an efficient and effective dynamic programming approximation. In a series of empirical comparisons designed to replicate past solver competitions, MAPP outperforms the most prominent alternative portfolio methods. Its success validates a principled approach to portfolio operation, offers a tool for tackling difficult problems, and opens a path forward in algorithm portfolio design.

Name thesis:degree_name

Doctor of Philosophy

Level thesis:degree_level

Doctoral

Discipline thesis:degree_discipline

Computer Science

Grantor

The University of Texas at Austin

Year dc:date.issued

2012

Author dc:creator

• Silverthorn, Bryan Connor

Advisor dc:contributor.advisor

• Miikkulainen, Risto

Committee members dc:contributor.committeemember

• Selman, Bart
• Stone, Peter
• Klivans, Adam
• Ravikumar, Pradeep

• Artificial intelligence
• Machine learning
• Propositional logic
• Algorithm selection
• Algorithm portfolios
• Satisfiability

Language dc:language.iso

en_US

Handle dc:identifier.uri

http://hdl.handle.net/2152/19828

OAI identifier oai:identifier

oai:repositories.lib.utexas.edu:2152/19828