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

    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.
    OriginalsprogEngelsk
    TitelProceedings from the International Conference on Economic, Technical and Organisational aspects of Product Configuration Systems
    Antal sider8
    ForlagTechnical University of Denmark
    Publikationsdato2004
    Sider133-140
    ISBN (Trykt)8791035139
    StatusUdgivet - 2004

    Emneord

    • Interactive product configuration
    • Binary Decision Diagrams (BDDs)
    • Symbolic representation
    • Offline and online processing
    • Formal verification

    Fingeraftryk

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

    Citationsformater