Parallel SAT-Solving for Product Configuration
| Main Author: | Nils Merlin Ullmann |
|---|---|
| Format: | info publication-thesis Journal |
| Bahasa: | eng |
| Terbitan: |
, 2021
|
| Subjects: | |
| Online Access: |
https://zenodo.org/record/5152114 |
Daftar Isi:
- This thesis presents parallel algorithms to solve SAT problems in the domain of product configuration. During an interactive configuration process, a user selects components step-by-step to find a suitable configuration that fulfills a set of constraints. A configuration system can be used to guide the user through the process by validating the selections and providing feedback. Each validation of a user selection is formulated as a SAT problem. Furthermore, an optimization problem is identified to find solutions with the minimum amount of changes compared to the previous configuration. The necessity of reproducible solutions, despite using parallel algorithms, is considered and concepts to provide deterministic results are presented. Different parallel algorithms are proposed and compared. Experiments show that reasonable speedups are achieved by using multiple threads over the sequential counterpart.