Introduction
Interactive configurators are the "wizards" used to customize complex products like laptops, cars, or insurance policies. To provide a high-quality user experience, these systems must be complete (all valid combinations reachable), backtrack-free (no dead ends), and real-time (instant updates). Binary Decision Diagrams (BDDs) are typically used to represent the set of valid configurations. However, a significant challenge arises when users want to impose a "hard ceiling" on cost—for example, "Show me only configurations under $2,000."
Traditionally, adding cost as a logical variable in a BDD causes its size to explode exponentially. This paper addresses this "cost variable trap" by proposing a polynomial-time algorithm that enforces cost bounds while maintaining the efficiency of the underlying BDD structure.
The Method: Augmented Labelled Graphs
The authors avoid the brute-force approach of adding cost variables. Instead, they treat the BDD as a graph and augment it with shortest-path metadata. Each node $u$ in the BDD is annotated with two critical values:
- $U[u]$: The minimum cost to reach this node from the root.
- $D[u]$: The minimum cost to reach a successful completion (terminal node) from this node.
By keeping the cost logic separate from the BDD's structural logic, the system can perform online filtering that remains polynomial in the size of the original BDD. This allows the configurator to instantly prune choices that would inevitably exceed the budget, even in the best-case scenario.
Efficient Filtering and Traversal
During an interactive session, when a user sets a maximum cost ($C_{max}$), the system uses the pre-calculated labels to update the valid domains of the remaining variables. The core of this process is the Traverse algorithm, which navigates the augmented graph to identify valid assignments.
The algorithm ensures that the user is never presented with an option that leads to a violation of the cost constraint. This "heavy lifting" of graph augmentation is performed once, ensuring that subsequent user interactions are extremely fast and responsive.
Theoretical Insights and Results
The paper establishes a clear theoretical boundary for cost-bounded configuration. The authors prove that while enforcing a maximum cost (or a minimum cost) is efficient and can be done in polynomial time, enforcing both simultaneously (a price range) is NP-hard. They demonstrate this by reducing the classic "Subset Sum" problem to the min-max configuration problem.
Key results include:
- Polytime Guarantee: A successful algorithm for calculating valid domains under a single-sided cost constraint.
- Complexity Boundary: Formal proof (Theorem 1) that adding cost as a logical variable is doomed to fail due to exponential growth.
- Practical Applicability: The method is designed for real-world configuration models, such as those found in the CLib benchmark library.
Conclusion and Future Work
This research provides a robust solution for integrating budget constraints into interactive configurators without sacrificing performance. Future work will explore scaling this approach to multiple independent dimensions, such as simultaneously managing price, weight, and environmental impact, and validating the performance on massive industrial datasets.
Summary updated