Decision Heuristics in a Constraint-based Product Configurator

This paper presents an evaluation of decision heuristics of solvers of the Boolean satisfiability problem (SAT) in the context of constraint-based product configuration. In product configuration, variable assignments are searched in real-time, based on interactively formulated user requirements. Operating on user’s successive input poses new requirements, such as low-latency interactivity as well as deterministic and minimal implicit product changes. This work presents a performance evaluation of several heuristics from the SAT literature along with new variants that address the special real-time requirements of incremental product configuration. Our results show that the execution time on an industrial benchmark can be significantly improved with our new heuristic.