In many AI domains such as product configuration, a user should interactively specify a solution that must satisfy a set of constraints. In such scenarios, offline compilation of feasible solutions into a tractable representation is an important approach to delivering efficient backtrack-free user interaction online. In particular,binary decision diagrams (BDDs) have been successfully used as a compilation target for product and service configuration. In this paper we discuss how to extend BDD-based configuration to scenarios involving cost functions which express user preferences. We first show that an efficient, robust and easy to implement extension is possible if the cost function is additive, and feasible solutions are represented using multi-valued decision diagrams (MDDs). We also discuss the effect on MDD size if the cost function is non-additive or if it is encoded explicitly into MDD. We then discuss interactive configuration in the presence of multiple cost functions. We prove that even in its simplest form, multiple-cost configuration is NP-hard in the input MDD. However, for solving two-cost configuration we develop a pseudo-polynomial scheme and a fully polynomial approximation scheme. The applicability of our approach is demonstrated through experiments over real-world configuration models and product-catalogue datasets. Response times are generally within a fraction of a second even for very large instances.

In many AI domains such as product configuration, a user should interactively specify a solution that must satisfy a set of constraints. In such scenarios, offline compilation of feasible solutions into a tractable representation is an important approach to delivering efficient backtrack-free user interaction online. In particular,binary decision diagrams (BDDs) have been successfully used as a compilation target for product and service configuration. In this paper we discuss how to extend BDD-based configuration to scenarios involving cost functions which express user preferences. We first show that an efficient, robust and easy to implement extension is possible if the cost function is additive, and feasible solutions are represented using multi-valued decision diagrams (MDDs). We also discuss the effect on MDD size if the cost function is non-additive or if it is encoded explicitly into MDD. We then discuss interactive configuration in the presence of multiple cost functions. We prove that even in its simplest form, multiple-cost configuration is NP-hard in the input MDD. However, for solving two-cost configuration we develop a pseudo-polynomial scheme and a fully polynomial approximation scheme. The applicability of our approach is demonstrated through experiments over real-world configuration models and product-catalogue datasets. Response times are generally within a fraction of a second even for very large instances.

A product configurator which is complete, backtrack free and able to compute the valid domains at any state of the configuration can be constructed by building a Binary Decision Diagram (BDD). Despite the fact that the size of the BDD is exponential in the number of variables in the worst case, BDDs have proved to work very well in practice. Current BDD-based techniques can only handle interactive configuration with small finite domains. In this paper we extend the approach to handle string variables constrained by regular expressions. The user is allowed to change the strings by adding letters at the end of the string. We show how to make a data structure that can perform fast valid domain computations given some assignment on the set of string variables. We first show how to do this by using one large DFA. Since this approach is too space consuming to be of practical use, we construct a data structure that simulates the large DFA and in most practical cases are much more space efficient. As an example a configuration problem on $n$ string variables with only one solution in which each string variable is assigned to a value of length of $k$ the former structure will use $Ω(k^n)$ space whereas the latter only need $O(kn)$. We also show how this framework easily can be combined with the recent BDD techniques to allow both boolean, integer and string variables in the configuration problem.

Constraint Programming (CP)[21] is a powerful technique for spec ifying Constraint Satisfaction Problems (CSPs) based on allowing a constraintprogrammer to model problems in terms of high-level constraints. Using such global constraints allows easier specification of problems but also allows for faster solve rs that take advantage of the structure in the problem. The classica l approach to CSP solving is to explore the search tree of all possible assignment s to the variables in a depth-first search backtracking manner, guided by v arious heuristics, until a solution is found or proven not to exist. One of the most basic techniques for reducing the number of search tree nodes explore d is to perform domain propagation at each node. In order to get as much domain propagation as possible we wish for each constraint to remove from the variable d omains all values that cannot participate in a solution to that constraint.

Constraint Programming (CP)[1] has been successfully appl ied to both constraint satisfaction and constraint optimization prob lems. A wide variety of specialized global constraints provide critical assistan ce in achieving a good model that can take advantage of the structure of the problem in the search for a solution. However, a key outstanding issue is the representation of'a d-hoc' constraints that do not have an inherent combinatorial nature, and hence are n ot modelled well using narrowly specialized global constraints. We attempt to address this issue by considering a hybrid of search and compilation. Specificall y we suggest the use of Reduced Ordered Multi-V alued Decision Diagrams (ROMDDs) as the supporting data structure for a generic global constraint. We g ive an algorithm for maintaining generalized arc consistency (GAC) on this cons traint that amortizes the cost of the GAC computation over a root-to-leaf path in th e search tree without requiring asymptotically more space than used for the MD D. Furthermore we present an approach for incrementally maintaining the redu ced property of the MDD during the search, and show how this can be used for provid ing domain entailment detection. Finally we discuss how to apply our ap proach to other similar data structures such as AOMDDs and Case DAGs. The techni que used can be seen as an extension of the GAC algorithm for the regular la nguage constraint on finite length input [2].

In these notes we formally describe the functionality of Calculating Valid Domains from the BDD representing the solution space of valid configurations. The formalization is largely based on the CLab configuration framework.