Treffer: 1
Autor Lindauer, T. Marius
Titel Algorithm selection, scheduling and configuration of Boolean constraint solvers
Dokumenttyp Hochschulschrift / Englisch
Dissertation an der Universität Potsdam, Institut für Informatik, Wissensverarbeitung und Informationssysteme, 2014
DDC-Notation 020; 004
Deskriptoren Wissensorganisation; Wissensmanagement; Programmierung; Algorithmus; Planung; Scheduling; Benchmarking; Wissensrepräsentation; Informationssystem
Abstract Boolean constraint solving technology has made tremendous progress over the last decade, leading to industrial-strength solvers, for example, in the areas of answer set programming (ASP), the constraint satisfaction problem (CSP), propositional satisfiability (SAT) and satisfiability of quantified Boolean formulas (QBF). However, in all these areas, there exist multiple solving strategies that work well on different applications; no strategy dominates all other strategies. Therefore, no individual solver shows robust state-of-the-art performance in all kinds of applications. Additionally, the question arises how to choose a well-performing solving strategy for a given application; this is a challenging question even for solver and domain experts. One way to address this issue is the use of portfolio solvers, that is, a set of different solvers or solver configurations. We present three new automatic portfolio methods: (i) automatic construction of parallel portfolio solvers (ACPP) via algorithm configuration,(ii) solving the $NP$-hard problem of finding effective algorithm schedules with Answer Set Programming (aspeed), and (iii) a flexible algorithm selection framework (claspfolio2) allowing for fair comparison of different selection approaches. All three methods show improved performance and robustness in comparison to individual solvers on heterogeneous instance sets from many different applications. Since parallel solvers are important to effectively solve hard problems on parallel computation systems (e.g., multi-core processors), we extend all three approaches to be effectively applicable in parallel settings. We conducted extensive experimental studies different instance sets from ASP, CSP, MAXSAT, Operation Research (OR), SAT and QBF that indicate an improvement in the state-of-the-art solving heterogeneous instance sets. Last but not least, from our experimental studies, we deduce practical advice regarding the question when to apply which of our methods. (Autor)
URN nbn:de:kobv:517-opus4-71260
Link 1 publish.UP
[142 S. / 4587 KB]
erstellt: 2015 | veröff.: 21.4.2015
Copyright © Uni Potsdam
Volltextlizenz Creative Commons - Namensnennung, Nicht kommerziell, Weitergabe zu gleichen Bedingungen 4.0 International

© Informationszentrum für Informationswissenschaft und -praxis