Fast Backtrack-Free Product Configuration using a Precompiled Solution Space Representation

Tarik Hadzic, Sathiamoorthy Subbarayan, Rune Møller Jensen, Henrik Reif Andersen, Jesper Møller, Henrik Hulgaard

Publikation: Konference artikel i Proceeding eller bog/rapport kapitelKonferencebidrag i proceedingsForskningpeer review


In this paper we describe a two-phase approach to interactive product configuration. In the first phase, a compressed symbolic representation of the set of valid configurations (the solution space) is compiled offline. In the second phase, this representation is embedded in an online configurator and utilized for fast, complete, and backtrack-free interactive product configuration. The main advantage of our approach compared to online search based approaches is that we avoid searching for valid solutions in each iteration of the interactive configuration process. The computationally hard part of the problem is fully solved in the offline phase given that the produced symbolic representation is small. The employed symbolic representation is Binary Decision Diagrams (BDDs). More than a decade of research in formal verification has shown that BDDs often compactly encode formal models of systems encountered in practice. To our experience this is also the case for product models. Often the compiled BDD is small enough to be embedded directly in hardware. Our research has led to the establishment of a spin-off company called Configit Software A/S. Configit has developed software for writing product models in a strongly typed language and has patented a particularly efficient symbolic representation called Virtual Tables.
TitelProceedings from the International Conference on Economic, Technical and Organisational aspects of Product Configuration Systems
Antal sider8
ForlagTechnical University of Denmark
ISBN (Trykt)8791035139
StatusUdgivet - 2004


Dyk ned i forskningsemnerne om 'Fast Backtrack-Free Product Configuration using a Precompiled Solution Space Representation'. Sammen danner de et unikt fingeraftryk.