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

Tarik Hadzic, Henrik Reif Andersen

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 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 configuration constraints into a tractable representation such as Binary Decision Diagrams (BDD) 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 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.

Subjects: 15.2 Constraint Satisfaction; 1.7 Expert Systems

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.