INFORMEDQX: Informed Conflict Detection for Over-Constrained Problems

Viet-Man Le, Alexander Felfernig, Thi Ngoc Trang Tran, Mathias UtaAAAI 2024 · DOI

TL;DR

This paper introduces INFORMEDQX, an algorithm that significantly speeds up conflict detection in complex configuration systems by intelligently reusing previously identified conflicts. By leveraging past knowledge, INFORMEDQX prunes the search space, leading to substantial performance improvements over existing methods like QUICKXPLAIN, especially in large-scale applications.

What Problem Does This Paper Address?

In many interactive systems, such as product configurators or diagnostic tools, inconsistencies can arise when a set of constraints cannot be satisfied simultaneously. Conflict detection aims to identify minimal sets of these conflicting constraints, which are crucial for explaining the inconsistency to users and guiding them towards a resolution. A common challenge, especially in large and complex systems, is that repeatedly detecting the same conflicts is computationally expensive. Existing algorithms like QUICKXPLAIN, while effective, can become slow as the problem size grows. This paper addresses the need for more efficient conflict detection by proposing a method that reuses knowledge of previously found conflicts to avoid redundant computations.

Methods

The core contribution is the INFORMEDQX algorithm, which is presented as an enhancement to the existing QUICKXPLAIN algorithm. QUICKXPLAIN uses a divide-and-conquer approach to find preferred minimal conflict sets. INFORMEDQX builds upon this by introducing a "reuse-aware" strategy.

The key idea is to maintain a set of previously identified minimal conflicts, denoted as $N$. When a new conflict detection task arises, INFORMEDQX first checks if a "preferred conflict" ($N_{cp}$) can be identified from $N$ that directly addresses the current user requirements ($CR$).

  • Scenario 1: If no relevant conflicts are found in $N$, or if $N$ is empty, the algorithm falls back to the standard QUICKXPLAIN.
  • Scenario 2: If a preferred conflict ($N_{cp}$) is found in $N$, INFORMEDQX attempts to prune the current set of user requirements ($CR$) to a smaller set ($C_p$). This pruning is based on the idea that constraints not part of the identified preferred conflict, and which are lexicographically less preferred, can be omitted from the search. The algorithm then activates QUICKXPLAIN on this pruned set ($C_p$), significantly reducing the search space.
  • Conflict Reuse: The algorithm also includes mechanisms to check if further, more preferred conflicts exist within the pruned set, potentially leading to further optimizations before invoking QUICKXPLAIN.

The paper also discusses the construction of the set $N$ using Binary Decision Diagrams (BDDs) for efficient querying of previously identified conflicts.

Datasets

The paper evaluates INFORMEDQX using the Linux-2.6.3.33 configuration knowledge base. This is a real-world benchmark dataset for configuration tasks, characterized by its large scale: 6,467 features, 6,322 relationships, and 7,650 cross-tree constraints. The authors synthesized 136 minimal conflict sets from this dataset, with cardinalities ranging from 2 to 8, for their experiments.

Key Insights and Ideas

  • Knowledge Reuse is Key: The most significant insight is that explicitly leveraging past conflict detection results can dramatically improve performance in complex, over-constrained systems. This moves beyond simply solving the current problem to learning from previous solutions.
  • Pruning the Search Space: INFORMEDQX's ability to prune the set of user requirements ($CR$) based on pre-identified preferred conflicts is a crucial optimization. This targeted reduction makes subsequent conflict detection much faster.
  • Beyond Complete Knowledge: The approach is particularly valuable in scenarios where not all possible conflicts are known beforehand, allowing for intelligent exploitation of partial knowledge.
  • BDDs for Efficient Querying: Using BDDs to represent and query the set of known conflicts ($N$) provides an efficient mechanism for identifying relevant past solutions.

Key Results

The experimental evaluation on the Linux-2.6.3.33 configuration knowledge base demonstrated significant performance improvements for INFORMEDQX compared to QUICKXPLAIN.

  • Runtime Improvements: In scenarios where conflicts were reused (i.e., $N_{cp} \neq 0$ and $N_{cp} \neq CS$), INFORMEDQX achieved notably shorter average runtimes. For instance, with 8 conflicts, INFORMEDQX took 12.60 seconds on average, while QUICKXPLAIN took 18.91 seconds.
  • Reduced Consistency Checks: INFORMEDQX significantly reduced the number of consistency checks required. For example, with 8 conflicts, INFORMEDQX performed 18 checks, whereas QUICKXPLAIN performed 22.
  • BDD Query Efficiency: The paper notes that BDD queries themselves are very fast, contributing minimally to the overall runtime of INFORMEDQX.

Limitations and Future Work

  • Limitations:
    • The performance gains are most pronounced when there are known conflicts in $N$ that are relevant to the current $CR$. In cases where no relevant conflicts are found in $N$, INFORMEDQX's performance can be slightly inferior to QUICKXPLAIN.
  • The effectiveness of INFORMEDQX relies on the quality and completeness of the pre-identified conflict set $N$.
  • Future Work:
    • Conducting more extensive evaluations on other industrial configuration knowledge bases.
  • Applying the "informed" mechanisms to diagnostic scenarios, potentially integrating them with existing diagnostic algorithms like FASTDIAGP.

Summary updated

BibTeX
@inproceedings{le2024informedqx,
  author = {Viet-Man Le and Alexander Felfernig and Thi Ngoc Trang Tran and Mathias Uta},
  title = {{INFORMEDQX: Informed Conflict Detection for Over-Constrained Problems}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2024},
  doi = {10.1609/aaai.v38i9.28932},
}
Figure