  Constraint Acquisition (CA) systems can be used to assist in the modeling of
constraint satisfaction problems. In (inter)active CA, the system is given a
set of candidate constraints and posts queries to the user with the goal of
finding the right constraints among the candidates. Current interactive CA
algorithms suffer from at least two major bottlenecks. First, in order to
converge, they require a large number of queries to be asked to the user.
Second, they cannot handle large sets of candidate constraints, since these
lead to large waiting times for the user. For this reason, the user must have
fairly precise knowledge about what constraints the system should consider. In
this paper, we alleviate these bottlenecks by presenting two novel methods that
improve the efficiency of CA. First, we introduce a bottom-up approach named
GrowAcq that reduces the maximum waiting time for the user and allows the
system to handle much larger sets of candidate constraints. It also reduces the
total number of queries for problems in which the target constraint network is
not sparse. Second, we propose a probability-based method to guide query
generation and show that it can significantly reduce the number of queries
required to converge. We also propose a new technique that allows the use of
openly accessible CP solvers in query generation, removing the dependency of
existing methods on less well-maintained custom solvers that are not publicly
available. Experimental results show that our proposed methods outperform
state-of-the-art CA methods, reducing the number of queries by up to 60%. Our
methods work well even in cases where the set of candidate constraints is 50
times larger than the ones commonly used in the literature.
