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

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 -