On the Modelling of Constraints with Tractable Logical Operators

Ruiwei Wang, Roland H. C. YapAAAI 2025 · DOI

TL;DR

This paper introduces a novel framework called "constraint representation pairs" to enable tractable negation for constraint satisfaction problems (CSPs). By focusing on specific subforms of existing representations like Binary Constraint Trees (BCTs) and Ordered Multi-valued Decision Diagrams (OMDDs), the authors demonstrate how to achieve expressive logical combinations of constraints without sacrificing computational efficiency. This work is crucial for building more flexible and powerful models for complex combinatorial problems.

What Problem Does This Paper Address?

Constraint Satisfaction Problems (CSPs) are fundamental to many areas of computer science, from scheduling to planning. Solving a CSP typically involves modeling the problem using a set of constraints. While basic constraints are useful, real-world problems often require more complex, "ad-hoc" constraints that can be built by combining simpler ones using logical operators like AND ($\land$), OR ($\lor$), and NOT ($\neg$).

The challenge arises because while AND and OR are generally well-supported, the negation operator ($\neg$) is often computationally intractable for many common constraint representations. This creates a dilemma: modelers want the expressiveness that negation provides, but using it can lead to models that are too slow to solve in practice. The paper addresses this gap by investigating how to achieve tractable negation for constraint representations, focusing on maintaining both expressiveness and computational efficiency.

Methods

The core contribution of this paper is the introduction of the constraint representation pair framework. This framework models a constraint $c$ and its negation $\neg c$ as a pair of representations, $(A, B)$, where $A$ represents $c$ and $B$ represents $\neg c$. If both $A$ and $B$ adhere to the same structural properties (like variable ordering), it's called an ordered constraint representation pair (op-R).

The authors then apply this framework to specific constraint representations:

  • Ordered Multi-valued Decision Diagrams (OMDDs): They identify subforms of OMDDs, specifically op-OMVD (ordered multi-valued variable diagram), which are strictly more succinct than standard OMDDs but retain tractable logical operations.
  • Binary Constraint Trees (BCTs): They introduce op-BCT (ordered BCT), which also offers improved succinctness and tractable logical operations.

The framework leverages the idea that if the conjunction and disjunction operations are tractable for a representation $R$, they are also tractable for its corresponding constraint representation pair $(p-R)$ and ordered pair $(op-R)$. Tractable negation is achieved by simply swapping the primal and dual representations within the pair.

Datasets

The paper does not introduce new datasets. Instead, it uses a set of six constraint families (F1-F6), defined in Table 1, as benchmarks. These families are specifically designed to test the tractability and succinctness of various constraint representations and their logical combinations, particularly focusing on scenarios where disjunction and conjunction might be intractable. They also use instances from the CSP competition 2009 for constraint reification benchmarks and product configuration instances (Bessiere, Fargier, and Lecoutre 2016) for evaluating model size.

Key Insights and Ideas

  • Tractable Negation is Achievable: The central insight is that by framing constraint modeling as pairs of primal and dual representations (e.g., $(c, \neg c)$), tractable negation becomes possible for certain representations, even if negation is intractable for the representation in isolation.
  • Op-BCT and Op-OMVD Offer Superior Succinctness: The paper demonstrates that the newly defined op-BCT and op-OMVD representations can be strictly more compact (succinct) than standard OMDDs for certain problems, while still supporting tractable logical operations. This is a significant improvement for modeling complex problems.
  • Constraint Representation Pairs as a Unifying Framework: The proposed framework provides a systematic way to study and compare the expressiveness and tractability of different constraint representations, particularly concerning logical operations.
  • Bridging Theory and Practice: The paper not only presents theoretical results on tractability and succinctness but also shows practical applications in modeling reified constraints and product configuration problems, demonstrating tangible benefits.

Key Results

  • Improved Tractability: The paper establishes that op-BCT and op-OMVD support tractable conjunction, disjunction, and negation operations, especially when following the same structure.
  • Enhanced Succinctness: op-BCT and op-OMVD are shown to be strictly more succinct than OMDD for certain constraint families. For example, family F3 can be modeled as a polysize op-OMVD but not as a polysize OMDD.
  • Practical Performance Gains: Experiments on constraint reification benchmarks show that using op-BCT propagators can be significantly faster (up to 124 times) than using MDDC propagators (which rely on OMDDs).
  • Compact Models: For product configuration benchmarks, op-BCT models were found to be considerably more compact than OMDD models.

Limitations and Future Work

  • Scope of Tractability: While the paper demonstrates tractable logical operators for op-BCT and op-OMVD under the same structure, it notes that conjunction and disjunction can be intractable for sets of op-BCT or op-OMVD constraints.
  • Representation Specificity: The framework is applied to BCT and OMVD/OMDD. Future work could explore its application to other constraint representations.
  • Experimental Scope: The experimental evaluation, while promising, could be expanded to a wider range of benchmarks and problem types to further validate the practical benefits of the proposed approach.
  • New Directions: The authors suggest that this work opens a new direction for exploring existing and new representations that can offer both modeling expressiveness and computational tractability, encouraging further research into such representations.

Summary updated

BibTeX
@inproceedings{wang2025modelling,
  author = {Ruiwei Wang and Roland H. C. Yap},
  title = {{On the Modelling of Constraints with Tractable Logical Operators}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.1609/aaai.v39i11.33238},
}
Figure