KIT | KIT-Bibliothek | Impressum | Datenschutz

Fast approximate calculation of valid domains in a satisfiability-based product configurator

Werner, J.; Balyo, T.; Iser, M.; Klein, M.


Calculating valid domains is an important feature of an interactive product configurator. Since it is an NP hard problem, it is necessary (for large real-world instances) to calculate valid domains only approximately in order to keep the response time low. In this paper, we present a new fast and accurate approximation algorithm to calculate the valid domains in a satisfiability based interactive product configurator. The algorithm is based on building a full implication graph during unit propagation and performing a search in that implication graph in order to approximate whether a domain value is valid. We experimentally compared our new algorithm to the algorithm used by the commercial SAT-based configurator CAS Merlin and measured speedups of up to 18-fold while maintaining the same accuracy.

Verlagsausgabe §
DOI: 10.5445/IR/1000138397
Veröffentlicht am 04.10.2021
Cover der Publikation
Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Proceedingsbeitrag
Publikationsjahr 2021
Sprache Englisch
Identifikator ISSN: 1613-0073
KITopen-ID: 1000138397
Erschienen in Proceedings of the 23rd International Configuration Workshop (CWS/ConfWS 2021): Vienna, Austria, 16-17 September, 2021. Ed.: M. Aldanondo
Veranstaltung 23rd International Configuration Workshop (ConfWS 2021), Wien, Österreich, 16.09.2021 – 17.09.2021
Verlag RWTH Aachen
Seiten 24-32
Serie CEUR Workshop Proceedings (CEUR-WS) ; 2945
Nachgewiesen in Scopus
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page