A BDD-Based Polytime Algorithm for Cost-Bounded Interactive Configuration

Interactive configurators are decision support systems assisting users in selecting values for parameters that respect given constraints. The underlying knowledge can be conveniently formulated as a Constraint Satisfaction Problem where the constraints are propositional formulas. The problem of interactive configuration was originally inspired by the product configuration problem with the emergence of the masscustomization paradigm in product manufacturing, but has also been applied to other tasks requiring user interaction, such as specifying services or setting up complex equipment. The user-friendly requirements of complete, backtrack-free and real-time interaction makes the problem computationally challenging. Therefore, it is beneficial to compile the configuration constraints into a tractable representation such as Binary Decision Diagrams (BDD) (Bryant 1986) to support efficient user interaction. The compilation deals with the NPhardness such that the online interaction is in polynomial time in the size of the BDD. In this paper we address the problem of extending configurators so that a user can interactively limit configuration choices based on a maximum cost (such as price or weight of a product) of any valid configuration, in a complete, backtrack-free and real-time manner. The current BDD compilation approach is not adequate for this purpose, since adding the total cost information to the constraints description can dramatically increase the size of the compiled BDD. We show how to extend this compilation approach to solve the problem while keeping the polynomial time guarantees.

Authors

• Tarik Hadzic Henrik Reif Andersen

Keywords

No keywords are indexed for this paper.