Abstract
Constraint Programming (CP) is a powerful paradigm for solving combinatorial problems, yet its adoption is hindered by the "modeling gap"—the difficulty of translating real-world requirements into formal constraint networks. This paper introduces CONACQ, an automated constraint acquisition algorithm. CONACQ represents the version space of consistent constraint networks as a Boolean satisfiability (SAT) problem. By leveraging SAT solvers and techniques like backbone detection, the algorithm can efficiently learn the underlying rules of a problem from positive and negative examples. Our evaluation shows that incorporating backbone detection allows the learner to converge to the correct network with significantly fewer examples.
Introduction
The effectiveness of Constraint Programming (CP) in industrial scheduling, routing, and configuration is well-established. However, defining the appropriate constraints typically requires a human expert. For non-experts, this modeling step is a significant barrier. The goal of constraint acquisition is to automate this process: given a set of "solutions" (allowed configurations) and "non-solutions" (forbidden configurations), can a system induce the target constraint network?
Methodology: The CONACQ Framework
The authors propose CONACQ (CONstraint ACQuisition), which integrates version space learning with SAT encoding.
Version Space and SAT Encoding
In version space learning, the system maintains a set of all hypotheses (constraint networks) consistent with the observed data. CONACQ represents this version space as a SAT formula. Each potential constraint from a predefined library is treated as a Boolean literal. When a user provides an example, it is converted into logical clauses that restrict the possible combinations of these literals.
Operational Complexity
The efficiency of managing the version space is critical for interactive learning. The table below summarizes the time complexity for various queries and operations within the CONACQ framework, where $b$ is the number of possible constraints and $m$ is the number of examples.
Handling Redundancy and Backbone Detection
A primary challenge in learning is redundancy (e.g., $A > B \land B > C \implies A > C$). Without addressing this, the version space remains large, necessitating more training data. CONACQ employs two strategies:
- Redundancy Rules: Manually encoded domain knowledge using Horn clauses.
- Backbone Detection: A SAT-based technique that identifies "backbone" literals—constraints that must be true in every valid model of the current SAT formula. This allows the system to "lock in" constraints before they are explicitly proven by a single example.
Experimental Evaluation
The researchers evaluated CONACQ using synthetic benchmarks involving 12 variables, each with a domain of 12 values. The constraint library consisted of 18 binary relations (e.g., $\le, =, \ge$). Training sets were composed of 10% positive and 90% negative examples. The experiments specifically tested "patterns"—chains of constraints—to assess how the algorithm handles varying degrees of redundancy.
Results and Discussion
The experimental results highlight the impact of backbone detection on learning efficiency.
Convergence and Efficiency
As shown in the results table, basic CONACQ is extremely fast (~0.11s per example) but often fails to narrow down the network, leaving many undecided constraints ($U(V_B)$). Adding redundancy rules improves this, but the combination of rules and backbone detection is the most effective. In almost all test cases, $U(V_B)$ dropped to zero, indicating perfect convergence to the target network. While backbone detection increases the time per example to approximately 2.5 seconds, it drastically reduces the total number of examples (#Exs) required.
Key Insights
- SAT as a Meta-Learner: Using SAT solvers to find the description of a problem allows the system to benefit from advanced solver technology.
- Logical Leaps: Backbone detection enables the learner to make global logical inferences, realizing mandatory constraints based on the overall structure of the provided examples.
Conclusion and Future Work
CONACQ demonstrates that SAT-based version space learning is a viable path toward automated constraint acquisition. However, some limitations remain. The current model assumes a fixed vocabulary of variables and domains and is sensitive to noise; a single mislabeled example can cause the version space to collapse. Future research will focus on handling noisy data and extending the framework to higher-order constraints beyond binary relations.
Summary updated