# Efficient Multiple Constraint Acquisition

arXiv: https://arxiv.org/abs/2109.05920 · HTML: https://mlsanity.com/paper/2109.05920/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 2 of its 42 references that are in the map.
- First posted on arXiv 13 Sep 2021.

## Builds on (most cited first, 2 of 2)

- [Boosting Combinatorial Problem Modeling with Machine Learning](https://mlsanity.com/paper/1807.05517/) (2018)
- [Exact Learning from an Honest Teacher That Answers Membership Queries](https://mlsanity.com/paper/1706.03935/) (2017)

## Built on by (most cited first, 7 of 7)

- [Guided Bottom-Up Interactive Constraint Acquisition](https://mlsanity.com/paper/2307.06126/) (2023)
- [Learning to Learn in Interactive Constraint Acquisition](https://mlsanity.com/paper/2312.10795/) (2023)
- [Easy, adaptable and high-quality Modelling with domain-specific Constraint Patterns](https://mlsanity.com/paper/2206.02479/) (2022)
- [Deep Neural Network for Constraint Acquisition through Tailored Loss Function](https://mlsanity.com/paper/2403.02042/) (2024)
- [MPMMine: Better Benchmarks for Constraint Acquisition](https://mlsanity.com/paper/2605.26279/) (2026)
- [Learning Symbolic Constraint Representations from Examples: A Neuro-Symbolic Approach](https://mlsanity.com/paper/2609.12267/) (2026)
- [Learning Size Independent Constraint Models from Input Data and Positive and Negative Example Solutions](https://mlsanity.com/paper/2610.13640/) (2026)

## Abstract (arXiv)

Constraint acquisition systems such as QuAcq and MultiAcq can assist non-expert users to model their problems as constraint networks by classifying (partial) examples as positive or negative. For each negative example, the former focuses on one constraint of the target network, while the latter can learn a maximum number of constraints. Two bottlenecks of the acquisition process where both these algorithms encounter problems are the large number of queries required to reach convergence, and the high cpu times needed to generate queries, especially near convergence. In this paper we propose algorithmic and heuristic methods to deal with both these issues. We first describe an algorithm, called MQuAcq, that blends the main idea of MultiAcq into QuAcq resulting in a method that learns as many constraints as MultiAcq does after a negative example, but with a lower complexity. A detailed theoretical analysis of the proposed algorithm is also presented. %We also present a technique that boosts the performance of constraint acquisition by reducing the number of queries significantly. Then we turn our attention to query generation which is a significant but rather overlooked part of the acquisition process. We describe %in detail how query generation in a typical constraint acquisition system operates, and we propose heuristics for improving its efficiency. Experiments from various domains demonstrate that our resulting algorithm that integrates all the new techniques does not only generate considerably fewer queries than QuAcq and MultiAcq, but it is also by far faster than both of them, in average query generation time as well as in total run time, and also largely alleviates the premature convergence problem.