Multiple Constraint Acquisition

Robin Arcangioli, Christian Bessiere, Nadjib LazaarIJCAI 2016

Abstract: Constraint acquisition systems like QUACQ automate the modeling process by learning from user-classified examples. However, high query counts often lead to user fatigue. This paper introduces MULTIACQ, an algorithm that maximizes information gain from negative examples by identifying all minimal scopes of failure. Experimental results across various benchmarks demonstrate a significant reduction in total queries and improved learning efficiency.

Introduction

Constraint programming is a robust framework for solving complex combinatorial problems, ranging from flight scheduling to Sudoku. However, modeling these problems typically requires expert knowledge. To democratize this process, researchers developed interactive Constraint Acquisition systems like QUACQ. These systems act as learners, asking a human user to classify examples as "positive" or "negative" to infer the underlying constraints.

While effective, QUACQ is notoriously "chatty." For a standard Sudoku puzzle, it may require over 8,000 queries, leading to significant user fatigue. This paper introduces MULTIACQ, a significant advancement that extracts more information from every negative response, drastically reducing the interaction burden.

The Challenge: Query Fatigue

In interactive constraint acquisition, the system proposes a configuration and asks the user for a classification. If the user rejects an example, the system knows at least one constraint was violated. The state-of-the-art QUACQ algorithm focuses on finding exactly one violated constraint per negative answer. This is inefficient; if a user rejects an example because multiple rules were broken, QUACQ ignores the additional information, necessitating more queries later. MULTIACQ aims to learn as much as possible from every single interaction.

Methodology: MULTIACQ and MACQ-CO

The core of the proposed approach is the findAllScopes algorithm, which identifies all "minimal scopes" of failure within a single negative example.

  1. Minimal Scopes: Inspired by Minimal Unsatisfiable Subsets (MUS) in SAT solving, the system identifies the smallest sets of variables causing a violation.
  2. Recursive Search: findAllScopes recursively explores variable subsets, using "partial queries"—questions about a small subset of variables—to pinpoint specific rule violations.
  3. Heuristics for Real-Time Interaction (MACQ-CO): Finding all violations can be computationally expensive. To maintain system responsiveness, the authors introduced MACQ-CO (MULTIACQ with Cut-Offs). If the search for a violation exceeds five seconds, the algorithm shuffles variables and moves to a new example, balancing computational time with query reduction.

Experimental Evaluation

The researchers evaluated MULTIACQ on a diverse set of benchmarks, including logic puzzles (Sudoku, Murder Mystery), combinatorial problems (Golomb Rulers, Langford’s Numbers), and real-world applications like the Radio Link Frequency Assignment Problem (RLFAP).

Performance comparison of QUACQ and MULTIACQ across logic puzzle benchmarks.

As shown in the table above, MULTIACQ significantly outperforms QUACQ. On Sudoku, total queries dropped by approximately 73% (from 10,110 to 3,821). Furthermore, the average query size—the number of variables a user must evaluate simultaneously—was reduced by up to 90%.

Comparative results for QUACQ, MULTIACQ, and the heuristic-based MACQ-CO on complex combinatorial problems.

For more complex problems like Graceful Graphs (GGraphs), the basic MULTIACQ algorithm encountered computational bottlenecks. However, the MACQ-CO variant successfully mitigated this, achieving a balance between query reduction and processing time.

Key Insights

  • Information Maximization: Negative examples are high-value data points. By identifying all minimal sets of variables causing a "No," the learner can eliminate large portions of the search space (the "bias") simultaneously.
  • Partial Queries: Asking a user to classify a small subset of variables is cognitively easier than classifying a complete configuration. MULTIACQ leverages this to improve user experience.
  • The Interaction Trade-off: While MULTIACQ increases CPU time, the massive reduction in human effort makes the system far more practical for real-world use.

Limitations and Future Directions

Despite its success, MULTIACQ assumes an "oracle" user who never makes mistakes. Future research should focus on making these algorithms robust to noisy or incorrect user feedback. Additionally, while the system handles standard benchmarks well, scaling to massive industrial-scale configuration problems remains an ongoing challenge.

Summary updated

BibTeX
@inproceedings{arcangioli2016multiple,
  author = {Robin Arcangioli and Christian Bessiere and Nadjib Lazaar},
  title = {{Multiple Constraint Acquisition}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2016},
}
Figure