Parallel Constraint Acquisition

Nadjib LazaarAAAI 2021 · DOI

Introduction

Constraint Programming (CP) is a robust paradigm for solving complex combinatorial problems, such as scheduling, layout design, and resource allocation. However, the utility of CP is often limited by the "modeling bottleneck"—the requirement for an expert to translate a real-world problem into a formal set of mathematical constraints.

To democratize CP, researchers developed Constraint Acquisition (CA) systems. These systems learn a model by interacting with a non-expert user, who classifies examples as either valid (positive) or invalid (negative). While sequential algorithms like QUACQ have proven effective, they suffer from two critical issues: extreme user fatigue (often requiring thousands of queries) and high computational complexity, where generating the next question becomes an NP-hard task that can stall the system for minutes.

The PACQ Framework

This paper introduces PACQ (Portfolio-based Parallel Constraint Acquisition), a framework that transforms the sequential learning process into a parallel task. By distributing the workload across multiple concurrent sessions, PACQ addresses both the human and computational bottlenecks of traditional CA.

Key Technical Components

  • Basis Partitioning: The "basis" (the set of all potential constraints) is divided into $N$ subsets. Each parallel session focuses on a specific portion of the problem space.
  • Shared Memory Model: Sessions operate concurrently but contribute to a unified "learned network" ($L$). When one session identifies a constraint, it is immediately shared with all other sessions, preventing redundant queries.
  • Rule-Based Splitting: Rather than random distribution, PACQ uses logical rules to group related constraints. This helps the system more efficiently identify implied or redundant constraints.
  • Heuristic Optimization: The framework utilizes the bdeg heuristic to prioritize variables involved in the highest number of unknown constraints, significantly accelerating the generation of new examples.

Experimental Evaluation

The researchers evaluated PACQ against a variety of benchmarks, including logic puzzles (Zebra, Sudoku), combinatorial problems (30-Queens, Latin Squares), and real-world meeting scheduling tasks.

Table 1: Impact of increasing the number of users (#U) on the number of queries per user (#q) across various benchmarks.

As shown in Table 1, increasing the number of parallel sessions (#U) leads to a dramatic reduction in the burden placed on any individual user. For instance, in the Latin Square problem, the number of queries per user (#q) dropped from 11,000 in a single-user setup to just 192 when distributed across 100 sessions.

Key Results and Scalability

PACQ demonstrates a significant "parallel relief" effect. While the total number of queries across all sessions increases slightly due to parallel overhead, the queries per user decrease by factors ranging from 2x to 60x.

Furthermore, PACQ overcomes the timeout barriers that plague sequential systems. In the 30-Queens problem, sequential QUACQ failed to converge within the time limit because generating a complete example became too computationally expensive. PACQ, by narrowing the search space for each session, achieved convergence in just 5 seconds.

Figure 1: Scalability analysis showing total queries (#Q), queries per user (#q), and learning ratio (R) as the number of users increases to 1000.

The system scales remarkably well to large-scale environments. As illustrated in Figure 1, PACQ can handle up to 1,000 parallel sessions. While the total query volume (#Q) grows, the individual user burden (#q) follows a steep downward curve, and the learning ratio (R)—the number of queries needed to learn a single constraint—remains within a manageable logarithmic bound.

Conclusion

PACQ represents a major step forward in making constraint acquisition practical for real-world use. By leveraging parallelism, the framework not only reduces user fatigue but also makes it possible to model complex problems that were previously computationally out of reach. Future work will focus on optimizing communication overhead in fully decentralized networks and improving robustness against noisy user feedback.

Summary updated

BibTeX
@inproceedings{lazaar2021parallel,
  author = {Nadjib Lazaar},
  title = {{Parallel Constraint Acquisition}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.1609/aaai.v35i5.16504},
}
Figure