A probabilistic architecture for algorithm portfolios

dc.contributor.advisorMiikkulainen, Ristoen
dc.contributor.committeeMemberSelman, Barten
dc.contributor.committeeMemberStone, Peteren
dc.contributor.committeeMemberKlivans, Adamen
dc.contributor.committeeMemberRavikumar, Pradeepen
dc.creatorSilverthorn, Bryan Connoren
dc.date.accessioned2013-04-05T14:50:01Zen
dc.date.issued2012-05en
dc.date.submittedMay 2012en
dc.date.updated2013-04-05T14:50:01Zen
dc.descriptiontexten
dc.description.abstractHeuristic 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.en
dc.description.departmentComputer Science
dc.format.mimetypeapplication/pdfen
dc.identifier.urihttp://hdl.handle.net/2152/19828en
dc.language.isoen_USen
dc.subjectArtificial intelligenceen
dc.subjectMachine learningen
dc.subjectPropositional logicen
dc.subjectAlgorithm selectionen
dc.subjectAlgorithm portfoliosen
dc.subjectSatisfiabilityen
dc.titleA probabilistic architecture for algorithm portfoliosen
thesis.degree.departmentComputer Sciencesen
thesis.degree.disciplineComputer Scienceen
thesis.degree.grantorThe University of Texas at Austinen
thesis.degree.levelDoctoralen
thesis.degree.nameDoctor of Philosophyen

Access full-text files

Original bundle

Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
silverthorn_dissertation_2012212.pdf
Size:
2.03 MB
Format:
Adobe Portable Document Format

License bundle

Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
2.13 KB
Format:
Plain Text
Description: