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

Abstract

Interactive configurators are decision support systems assist-ing 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 in-teractive configuration was originally inspired by the prod-uct configuration problem with the emergence of the mass-customization 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 con-figuration constraints into a tractable representation such as Binary Decision Diagrams (BDD) (Bryant 1986) to support efficient user interaction. The compilation deals with the NP-hardness such that the online interaction is in polynomial time in the size of the BDD. In this paper we address the problem of extending con-figurators so that a user can interactively limit configura-tion choices based on a maximum cost (such as price or weight of a product) of any valid configuration, in a com-plete, 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 descrip-tion 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.