Learning Constraint Networks over Unknown Constraint Languages

Christian Bessiere, Clément Carbonnel, Areski HimeurIJCAI 2023 · DOI

TL;DR

This paper introduces a novel method for "constraint acquisition" that automatically learns both the constraints and the underlying constraint language for a given problem, eliminating the need for prior knowledge of the language. This significantly broadens the applicability of constraint programming by making it accessible to non-experts.

What Problem Does This Paper Address?

Constraint programming (CP) is a powerful technique for solving complex combinatorial problems. However, a major hurdle is the process of expressing these problems using constraints. This typically requires users to have advanced knowledge of both CP and the specific problem domain to define the correct constraint language and select appropriate constraints. Existing constraint acquisition systems often assume the constraint language is known beforehand, limiting their usefulness. This paper tackles the challenge of learning constraint networks without any prior knowledge of the target constraint language, aiming to automate the entire process of problem modeling.

Methods

The core contribution is a method that learns a constraint network and its associated constraint language simultaneously from examples of solutions and non-solutions. The problem is framed as finding a constraint network that is consistent with the provided examples, while also minimizing the complexity of the learned constraint language (defined by the number of relations and their arity).

The authors first formalize the "LANGUAGE-FREE ACQ" problem and prove it's NP-complete, even for simple cases. To solve this, they propose a method that iteratively searches for the simplest constraint language and network. For a fixed language complexity (defined by maximum arity $k$ and number of relations $r$), they model the problem as a Weighted Partial Max-SAT instance. This involves defining Boolean variables representing relations, constraints, and their relationships, and then constructing hard and soft clauses to enforce consistency with examples and optimize for language simplicity. The search for the optimal $(k, r)$ is done in a bottom-up fashion, starting with the simplest languages and increasing complexity until a consistent network is found.

Datasets

The paper evaluates its method on several standard benchmark problems:

  • Sudoku: A classic logic puzzle.
  • Jigsaw Sudoku: A variant of Sudoku with irregular shapes.
  • Schur's Lemma: A problem involving partitioning numbers into boxes.
  • Subgraph Isomorphism: Determining if one graph contains a subgraph isomorphic to another.
  • N-Queens: Placing N queens on a chessboard without attacking each other.
  • Golomb Ruler: Finding a set of marks on a ruler with unique differences.

For each benchmark, training sets of varying sizes were generated. Positive examples were created by solving the target constraint network using a solver and randomized strategies, while negative examples were generated by altering solutions.

Key Insights and Ideas

  • Language Agnosticism is Key: The most significant insight is that by not requiring prior knowledge of the constraint language, the method becomes vastly more applicable to real-world problems where users might not be CP experts.
  • Simplicity as a Guiding Principle: The paper formalizes "simplicity" of a constraint language by minimizing its arity and the number of relations. This heuristic is crucial for guiding the search and avoiding trivial, overly complex languages.
  • Max-SAT as a Powerful Tool: Framing the problem as a Weighted Partial Max-SAT instance allows for a flexible and efficient way to encode the learning objective, balancing consistency with examples and language complexity.
  • Trade-off Between Examples and Complexity: The experiments reveal a clear trade-off: more complex target languages require significantly more examples to be learned accurately.

Key Results

  • The method achieves high accuracy (often >99%) on several benchmarks, including Sudoku, Jigsaw Sudoku, and Schur's Lemma, with a sufficient number of examples.
  • For Sudoku, the target constraint network was learned consistently with around 200 examples.
  • The method can learn the target language for Schur's Lemma with as few as 50 examples, demonstrating its ability to rule out simpler languages effectively.
  • For more complex languages (e.g., Subgraph Isomorphism, 8-Queens, Golomb Ruler), the method often learns equivalent networks rather than the exact target network, but still achieves high accuracy.
  • The runtime is heavily influenced by the complexity of the target language and the number of examples. For very complex languages or insufficient examples, the solver can time out.
  • The ratio of positive to negative examples impacts learning efficiency; a higher proportion of positive examples generally leads to faster learning, up to a point.

Limitations and Future Work

  • Number of Examples: The method can require a substantial number of examples, especially for complex constraint languages.
  • Language Complexity: Dealing with very large constraint languages remains challenging.
  • "Simplicity" Heuristic: The current definition of simplicity (minimizing $k$ and $r$) is a rough approximation. Future work could explore more sophisticated notions of simplicity.
  • Topological Information: Automatically detecting or inferring topological information about the target network (e.g., matrix structures) could significantly improve learning efficiency.
  • Learning with Only Positive Examples: The current method struggles to learn the target network when only positive examples are provided, often defaulting to a degenerate network.

Summary updated

BibTeX
@inproceedings{bessiere2023learning,
  author = {Christian Bessiere and Clément Carbonnel and Areski Himeur},
  title = {{Learning Constraint Networks over Unknown Constraint Languages}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.24963/ijcai.2023/208},
}
Figure