Improving the Performance of Interactive Configuration with Regular String Constraints

Esben Rune Hansen, Peter Tiedemann

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

    Abstrakt

    A generalization of the problem of interactive configuration has previously been presented in [1]. This generalization
    utilized decomposition to extend the standard finite domain interactive configuration framework to deal with unbounded string variables and provided features such as prefix auto-completion.

    In this paper we present several significant improvements to the core data structures and algorithms in [1] as well as the first implementation of an interactive configurator on string variables.

    The primary improvement is obtained by replacing the binary decomposition model with a finite domain model. We then describe an optimization for this model which allows us to replace the use of costly conjunctions with simple restrict operations during synchronization between decomposed constraints. In addition we describe how to improve the performance of the auto-complete operation, by using projection on relevant variables to significantly reduce the size of the data structures involved.

    We empirically verify the critical significance of these improvements using our own implementation of a string variable based configurator on real-world example data.

    OriginalsprogEngelsk
    TitelInternational Conference on Tools with Artificial Intelligence : 20th IEEE International Conference on Tools with Artificial Intelligence (ICTAI 2008)
    ForlagIEEE Press
    Publikationsdato2008
    Sider3-10
    ISBN (Trykt)978-0-7695-3440-4
    DOI
    StatusUdgivet - 2008
    Begivenhed20th IEEE International Conference on Tools with Artificial Intelligence, 2008. ICTAI '08. - Dayton, Ohio, USA
    Varighed: 3 nov. 20085 nov. 2008
    Konferencens nummer: 20

    Konference

    Konference20th IEEE International Conference on Tools with Artificial Intelligence, 2008. ICTAI '08.
    Nummer20
    Land/OmrådeUSA
    ByDayton, Ohio
    Periode03/11/200805/11/2008

    Citationsformater