TY - GEN
T1 - Fast Backtrack-Free Product Configuration using a Precompiled Solution Space Representation
AU - Hadzic, Tarik
AU - Subbarayan, Sathiamoorthy
AU - Jensen, Rune Møller
AU - Andersen, Henrik Reif
AU - Møller, Jesper
AU - Hulgaard, Henrik
PY - 2004
Y1 - 2004
N2 - 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.
AB - 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.
KW - Interactive product configuration
KW - Binary Decision Diagrams (BDDs)
KW - Symbolic representation
KW - Offline and online processing
KW - Formal verification
KW - Interactive product configuration
KW - Binary Decision Diagrams (BDDs)
KW - Symbolic representation
KW - Offline and online processing
KW - Formal verification
UR - https://backend.orbit.dtu.dk/ws/portalfiles/portal/5285291/PETO+2004+Proceedings.pdf
M3 - Article in proceedings
SN - 8791035139
SP - 133
EP - 140
BT - Proceedings from the International Conference on Economic, Technical and Organisational aspects of Product Configuration Systems
PB - Technical University of Denmark
ER -