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

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.