1 Search Results for "Ullmann, Nils Merlin"

Document
DOI: 10.4230/LIPIcs.CP.2021.55
Parallelizing a SAT-Based Product Configurator

Authors: Nils Merlin Ullmann, Tomáš Balyo, and Michael Klein

Published in: LIPIcs, Volume 210, 27th International Conference on Principles and Practice of Constraint Programming (CP 2021)

Abstract
This paper presents how state-of-the-art parallel algorithms designed to solve the Satisfiability (SAT) problem can be applied in the domain of product configuration. During an interactive configuration process, a user selects features step-by-step to find a suitable configuration that fulfills his desires and the set of product 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. Another additional constraint is deterministic computation, which is not trivial to achieve in well performing parallel SAT solvers. In the paper we propose five new deterministic parallel algorithms and experimentally compare them. Experiments show that reasonable speedups are achieved by using multiple threads over the sequential counterpart.
Cite as

Nils Merlin Ullmann, Tomáš Balyo, and Michael Klein. Parallelizing a SAT-Based Product Configurator. In 27th International Conference on Principles and Practice of Constraint Programming (CP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 210, pp. 55:1-55:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{ullmann_et_al:LIPIcs.CP.2021.55,
  author =	{Ullmann, Nils Merlin and Balyo, Tom\'{a}\v{s} and Klein, Michael},
  title =	{{Parallelizing a SAT-Based Product Configurator}},
  booktitle =	{27th International Conference on Principles and Practice of Constraint Programming (CP 2021)},
  pages =	{55:1--55:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-211-2},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{210},
  editor =	{Michel, Laurent D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2021.55},
  URN =		{urn:nbn:de:0030-drops-153464},
  doi =		{10.4230/LIPIcs.CP.2021.55},
  annote =	{Keywords: Configuration, Satisfiability, Parallel}
}
  • Refine by Author
  • 1 Balyo, Tomáš
  • 1 Klein, Michael
  • 1 Ullmann, Nils Merlin

  • Refine by Classification
  • 1 Applied computing → E-commerce infrastructure

  • Refine by Keyword
  • 1 Configuration
  • 1 Parallel
  • 1 Satisfiability

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2021

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact