Thumbnail
Access Restriction
Subscribed

Author Hansen, E.R. ♦ Tiedemann, P.
Source IEEE Xplore Digital Library
Content type Text
Publisher Institute of Electrical and Electronics Engineers, Inc. (IEEE)
File Format PDF
Copyright Year ©2008
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Special computer methods
Subject Keyword Binary decision diagrams ♦ Data structures ♦ Artificial intelligence ♦ Constraint optimization ♦ NP-hard problem ♦ Constraint theory ♦ Boolean functions ♦ Polynomials ♦ Regular Languages ♦ Constraint Programming ♦ Decision Support
Abstract 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.
Description Author affiliation: IT Univ. of Copenhagen, Copenhagen (Hansen, E.R.; Tiedemann, P.)
ISBN 9780769534404
ISSN 10823409
Educational Role Student ♦ Teacher
Age Range above 22 year
Educational Use Research ♦ Reading
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2008-11-03
Publisher Place USA
Rights Holder Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Size (in Bytes) 339.08 kB
Page Count 8
Starting Page 3
Ending Page 10


Source: IEEE Xplore Digital Library