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

Research output: Conference Article in Proceeding or Book/Report chapterArticle in proceedingsResearchpeer-review

Abstract

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.
Original languageEnglish
Title of host publicationProceedings from the International Conference on Economic, Technical and Organisational aspects of Product Configuration Systems
Number of pages8
PublisherTechnical University of Denmark
Publication date2004
Pages133-140
ISBN (Print)8791035139
Publication statusPublished - 2004

Fingerprint

Dive into the research topics of 'Fast Backtrack-Free Product Configuration using a Precompiled Solution Space Representation'. Together they form a unique fingerprint.

Cite this