Nadjib Lazaar
email: lazaar@lirmm.fr

Parallel Constraint Acquisition

Constraint acquisition systems assist the non-expert user in modelling her problem as a constraint network. QUACQ is a sequential constraint acquisition algorithm that generates queries as (partial) examples to be classified as positive or negative. The drawbacks are that the user may need to answer a great number of such examples, within a significant waiting time between two examples, to learn all the constraints. In this paper, we propose PACQ, a portfolio-based parallel constraint acquisition system. The design of PACQ benefits from having several users sharing the same target problem. Moreover, each user is involved in a particular acquisition session, opened in parallel to improve the overall performance of the whole system. We prove the correctness of PACQ and we give an experimental evaluation that shows that our approach improves on QUACQ.

Introduction

Constraint programming (CP) has made considerable progress over the last forty years, becoming a powerful paradigm for modelling and solving combinatorial problems. Several parallel algorithms have been proposed to solve a problem as a constraint network and they are grouped under categories: distributed CSPs; parallel propagation; parallel search; portfolio algorithms; problem decomposition [START_REF] Régin | Parallel Constraint Programming[END_REF]. However, modelling a problem as a constraint network still remains a challenging task that requires some expertise in the field. Several constraint acquisition systems have been introduced to support the uptake of constraint technology by non-experts. Freuder and Wallace proposed the matchmaker agent [START_REF] Freuder | Suggestion Strategies for Constraint-Based Matchmaker Agents[END_REF]. This agent interacts with the user while solving her problem. The user explains why she considers a proposed solution as a wrong one. Lallouet et al. proposed a system based on inductive logic programming with the use of the structure of the problem as a background knowledge [START_REF] Lallouet | On Learning Constraint Problems[END_REF]). Beldiceanu and Simonis proposed MODELSEEKER, a system devoted to problems with regular structures and based on the global constraint catalog [START_REF] Beldiceanu | A Model Seeker: Extracting Global Constraint Models from Positive Examples[END_REF]. Bessiere et al. proposed CONACQ, which generates membership queries (i.e., complete examples) to be classified by the user [START_REF] Bessiere | Constraint acquisition[END_REF]). Shchekotykhin and Friedrich extended CONACQ to allow the user to provide arguments as constraints to speedup the convergence [START_REF] Shchekotykhin | Argumentation Based Constraint Acquisition[END_REF]. Bessiere et al. proposed QUACQ (for Quick Acquisition), an active learning system that is able to ask the user to classify partial queries [START_REF] Bessiere | Partial Queries for Constraint Acquisition[END_REF][START_REF] Bessiere | Constraint Acquisition via Partial Queries[END_REF]. QUACQ iteratively computes membership queries. If the user says yes, QUACQ reduces the search space by discarding all constraints violated by the positive example. When the answer is no, QUACQ finds the scope of one of the violated constraints of the target network in a number of queries logarithmic in the size of the example. This key component of QUACQ allows it to always converge on the target set of constraints in a polynomial number of queries. However, even that good theoretical bound can be hard to put in practice. Generating a complete example is NP-hard and the total number of examples to classify can be large. For instance, QUACQ can take more than 20 minutes to generate a complete example during the acquisition process of the Sudoku constraint network and it requires the user to classify more than 9K examples.

In this paper, we introduce a first ever approach to combine CP modelling through constraint acquisition with parallelism. We present PACQ, a portfolio-based parallel constraint acquisition system. PACQ learns constraint network by exchanging with several users in different acquisition sessions. Users have in mind the same target problem without knowing how to model it as a constraint network. PACQ benefits from the main limitations of the sequential QUACQ system: (i) large number of examples to classify by the user; and (ii) significant waiting time between two queries. We experimentally evaluate the benefit of using parallelism in constraint acquisition on several problems. The results show that the number of queries increases under an upper-bound using PACQ and that PACQ dramatically improves the sequential version of QUACQ in terms of queries asked per user and in terms of CPU time needed to generate queries.

Background

The constraint acquisition process can be seen as an interplay between the user and the learner. In our context, we have N users (U 1 to U N ) involved in N different acquisition sessions (A 1 to A N ) with one user per session and under a memory-shared model. The learner and the users need to share some common knowledge to communicate.

We suppose this common knowledge, called the vocabulary, is a tuple of n variables X = (x 1 , . . . , x n ) and a domain D = {D(x 1 ), . . . , D(x n )}, where D(x i ) ⊂ Z is the finite set of values for x i . A constraint c S is defined by the sequence of variables S, a sub-sequence of X (i.e. S X), called the constraint scope, and the relation c over Z specifying which sequences of |S| values are allowed for the variables S. A constraint network is a set C of constraints on the vocabulary (X, D). An assignment e Y ∈ D Y , where In addition to the vocabulary, the learner owns a language Γ of bounded arity relations from which it can build constraints on specified sets of variables. Adapting terms from machine learning, the constraint basis, denoted by B, is a set of constraints built from the language Γ on the vocabulary (X, D) from which the learner builds a constraint network.

D Y = Π xi∈Y D(x i ),
Given a prefixed vocabulary (X, D), a concept is a Boolean function f over D X , that is, a map that assigns to each assignement e a value in {0, 1}. A representation of a concept f is a constraint network C for which f -1 (1) = sol(C). A target concept is a concept f T that returns 1 for e if and only if e is a solution of the problem that the N users share and have in mind. The target network is a network T such that T ⊆ B and T is a representation of f T . Then we say that the target concept f T is representable by B. A membership query ASK Ui (e) takes as input a complete assignment e in D X and asks the user U i to classify it. The answer to ASK Ui (e) is yes if and only if e ∈ sol(T ). A partial query ASK Ui (e Y ), with Y ⊆ X, takes as input a partial assignment e Y in D Y and asks the user U i to classify it. The answer to ASK Ui (e Y ) is yes if and only if e Y does not violate any constraint in T . It is important to observe that "ASK Ui (e Y )=yes " does not mean that e Y extends to a solution of T , which would put an NP-complete problem on the shoulders of the user. For any assignment e Y on Y , κ B (e Y ) denotes the set of all constraints in B rejecting e Y . A classified assignment e Y is called positive or negative example depending on whether ASK Ui (e Y ) is yes or no. Knowing that (i) any extension of a negative example is a negative example and any shortening of a positive example is a positive example; and (ii) under a memoryshared model: the ASK function checks first if the query is not a redundant one w.r.t. another acquisition session where the classification can be deduced.

We now define convergence, which is the constraint acquisition problem we are interested in. Given a set E of (partial) examples labelled by the user yes or no, we say that a network C agrees with E if C accepts all examples labelled yes in E and does not accept those labelled no. The learning process has converged on the network L ⊆ B if (i) L agrees with E and (ii) for every other network L ⊆ B agreeing with E, we have sol(L ) = sol(L). We are thus guaranteed that sol(L) = sol(T ). We say that the learning process reached a premature convergence if only (i) is guaranteed.

PACQ: Portfolio-Based Parallel Constraint Acquisition

We propose PACQ, a portfolio-based parallel constraint acquisition system. PACQ takes as input a basis B on a vocabulary (X, D) shared with N users. It asks (partial) queries of the N users until it has converged on a constraint network L equivalent to the target network T . The rationale behind PACQ is to learn a constraint network using N parallel acquisition sessions. That is, we have a portfolio of acquisition sessions aiming to acquire simultaneously different parts of the problem using a shared-memory model.

Description of PACQ

PACQ (see Algorithm 1) shares between acquisition sessions the basis B and the network L (line 2). PACQ initializes the network L it will learn to empty set (line 3). At line 4, PACQ makes a set-partition of the basis B into N subsets (B 1 . . . B N ) using split function (i.e., B i = ∅, B i ∩ B j = ∅, ∀i, j and N i=1 B i = B). We will see later that there are multiple ways to design the split function. Then, PACQ opens in parallel N Acq session (line 6) and it converges on L once all sessions closed (line 7).

Acq session starts by calling GenerateExample function that generates an example e on X satisfying the constraints of L, but violating at least one constraint from B i (line 2). Bear in mind that, from a session to another, generating an example on a different B i allows us to have sessions with different and complementary viewpoints on the acquisition process as a whole. If there does not exist any example e accepted by L and rejected by B i , then all constraints in B i are implied by L and we can safely remove them from B (line 3). Then, the current session is closed (line 3). If an example e is returned by GenerateExample, e is classified as positive or negative by the user U i (line 4). If the answer is yes, we can remove from B the set κ B (e) (line 5). If the answer is no, we are sure that e violates at least one constraint of the target network T . We then call the function FindScope to discover the scope scp of these violated constraints (line 7), and the procedure FindC will learn (that is, put in L) at least one constraint of T whose scope is in scp (line 9). Function FindScope and procedure FindC ask queries to the corresponding user U i and they are used exactly as they appear in, respectively, [START_REF] Bessiere | Constraint Acquisition via Partial Queries[END_REF] and [START_REF] Bessiere | Partial Queries for Constraint Acquisition[END_REF]. The unique portion of the algorithm that cannot be parallelized is the call of FindC within connected scopes. Here, the procedure FindC has a unique permit access. For instance, if two Acq session A i and A j return simultaneously at line 7 the scopes scp 1 and scp 2 , such that scp 1 ∩ scp 2 = ∅ (i.e., connected scopes), only one session acquires an access to FindC on scp 1 or scp 2 (line 8) and the second one must wait for its release at line 10. In case we have two sessions looking simultaneously for constraints on scp, only one session will have access to FindC

whereafter κ B (e[scp]) = ∅. Algorithm 1: PACQ In : A basis B, Number of Users N Out : A learned network L 1 begin 2 shared B; L; 3 L ← ∅; 4 split (B, N ); // split B into N parts 5 foreach i ∈ 1..N do in parallel 6 Acq session (U i ); 7 return "convergence on L"

Theoretical Analysis

We first show that a parallel acquisition using PACQ (algorithm 1) is a correct algorithm to learn a constraint network representing the target problem over B. We prove that PACQ is sound, complete, and it terminates.

Proposition 1 (Soundness) Given a basis B, a target network T ⊆ B and N users, the network L returned by PACQ is such that sol(T ) ⊆ sol(L).

Proof. Suppose there exists e ∈ sol(T ) \ sol(L). Hence, there exists at least a constraint c Y ∈ L rejecting e and learned by PACQ within a Acq session A i of user U i . The only place where we can add c Y to L is (algo:2-line:9) with FindC on Y scope that is returned by FindScope at (algo:2line:7). FindC represents the portion of PACQ that is not parallelized and the access is conditioned by the fact that no previous call occurred on Y (i.e., κ B (e[Y ]) = ∅). We know from [START_REF] Bessiere | Constraint Acquisition via Partial Queries[END_REF][START_REF] Bessiere | Partial Queries for Constraint Acquisition[END_REF] that FindScope and FindC functions are sound. The learned constraint c Y is one of the target network T . Therefore, adding a constraint to L cannot reject a tuple accepted by T .

Proposition 2 (Completeness) Given a basis B, a target network T ⊆ B and N users, the network L returned by PACQ is such that sol(L) ⊆ sol(T ).

Proof. Suppose there exists e ∈ sol(L) \ sol(T ) when PACQ terminates. Hence, there exists a constraint c Y from B that rejects e. Knowing that at (algo:1-line:4) we have Algorithm 2: Acq session (U i ) a set-partition of B, it exists a Acq session A i where c Y ∈ B i . The only way for PACQ to terminate is to have all Acq session closed. This means that within A i session and at (algo:2-line:2), GenerateExample was not able to generate an example e accepted by L and rejected by B i . c Y was in B i before starting PACQ (c Y ∈ T ) and it is not in B i when PACQ terminates. Constraints can be removed in FindC/FindScope functions and at (algo:2-line:3 and 5). We know from [START_REF] Bessiere | Constraint Acquisition via Partial Queries[END_REF][START_REF] Bessiere | Partial Queries for Constraint Acquisition[END_REF] that FindC/FindScope cannot remove a constraint that rejects an example accepted by L. A constraint c removed from (algo:2-line:3 and 5) cannot be c Y because e violtates c Y and is accepted by L. Therefore, c Y cannot reject an example accepted by L, which proves that sol(L) ⊆ sol(T ).

1 while true do 2 e ←GenerateExample (L, B i ); 3 if e = nil then B ← B \ B i ; break ; 4 if ASK Ui (e) = yes then 5 B ← B \ κ B (e);
Proposition 3 (Termination) Given a basis B, a target network T ⊆ B and N users, PACQ terminates.

Proof. The termination of PACQ immediately follows the closure of the N Acq session. Let us consider a given A i session. An example is generated such that it satisfies L and violates B i . If no such example exists, B i is reduced to empty and A i session is closed. Otherwise, Generate-Example at (algo:2-line:2) returns an example e to submit to the user U i . B decreases in size by removing κ B (e) when user U i says yes (algo:2-line:5). If the user U i says no, B also decreases in size by learning at least one constraint from B (algo:2-line:9). Let us suppose now that the user U i says no on e because of a unique constraint to learn c Y that is rejected by e. Suppose that the same example is generated at the same time in k -1 sessions. Then Y scope is returned by the FindScope calls in the k Acq session. We know that for connected scopes, FindC has a single permit access. Thus, we have only one user U j calling FindC Uj , adding c Y to L and removing c Y from B. Afterwards, the other k -1 sessions will not have access to FindC on Y as κ B (e[Y ]) is reduced to empty after the first call. Therefore, at each execution of the loop, we have at least one B i that strictly decreases in size. As B i represent finite-size subsets coming from a set-partition of B, we have termination.

Theorem 1 (Correctness) Given a basis B, a target network T ⊆ B and N users, PACQ returns a network L such that sol(L) = sol(T ).

Proof. Correctness immediately follows from Propositions 1, 2, and 3.

Strategies and Settings

PACQ can be improved by making the use of Generate-Example and split functions less brute-force, and by adapting it to a particular context (e.g., distributed CSPs).

GenerateExample. We can speed up the example generation by using well-known variable heuristic selectors (e.g., minDom, domOverWdeg, impact,...), or by using a dedicated one like bdeg heuristic [START_REF] Tsouros | Efficient multiple constraint acquisition[END_REF]. bdeg selects the variable involved in a maximum number of constraints present in B i \ L. Knowing that each session is reasoning on a particular B i and based on preliminary comparisons, bdeg heuristic provides a good diversification.

split. In our study, we have investigated five setpartitions of B based on different background knowledge:

• Scope: put in the same B i all constraints of a given scope;

• Negation: put in B i a constraint and its negation;

• Language: put in B i constraints of the same relation;

• Graph: B i 's are connected components;

• Rule: put in B i constraints satisfying a set of rules.

The preliminary tests show that a B partition using background knowledge boosts the acquisition process and that the same findings are observed with the five set-partitions. We focus our analysis on the Rule based set-partition.

The split function based on Rule groups in the same B i 's constraints satisfying a set of rules adapted to constraint acquisition. For instance, if we know that c 1 ∧ c 2 → c 3 , then putting the three constraints c 1 , c 2 , c 3 in the same B i can speed up the generation of examples. Building a complete set of rules is often too expensive, both in time and space as it requires generating a set of rules potentially exponential in space (all combinations of constraints that imply another one). However, it is possible to compute approximations by bounding the number of constraints in the body of a rule. Here, we only considered the rule that contain two constraints in the body rule : c i ∧ c j → c k . That is, split performs a random partition of triplets (c i , c j , c k ) ∈ B 3 where (c i , c j , c k ) satisfies rule. The rationale behind Rule partition is to group in the same session a certain percentage of redundancies that B contains. " Doing so, (i) we facilitate the task of GenerateExample to find an assignment satisfying L and rejecting at least one constraint in B, and (ii) avoiding parallel sessions to learn redundancies.

PACQ for Distributed CSPs. In some cases, parallel acquisition can be subject to privacy and/or security requirements with information that should not be shared between sessions. PACQ can easily be adapted to act in a distributed context by (i) taking into account the visibility of each agent (i.e., set of variables) in the split function (algo:1-line:4); and (ii) for a given session, generating examples on its own learned network L i (algo:2-line:2).

PACQ versions.

With the different strategies and settings in hand, we evaluate the four following versions of PACQ: • PACQ.0 using a random variable ordering and a random set-partition of B into N subsets.

• PACQ.1 using bdeg heuristic; • PACQ.2 using bdeg heuristic and Rule based split; • PACQ.3 a revised version of PACQ.2 for distributed CSPs.

Experimental Evaluation

In this section, we experimentally evaluate our portfoliobased parallel constraint acquisition system. As finding an assignment satisfying the constraints of L and violating at least one constraint from B is an NP-complete problem, we use a time limit, denoted by TL, once reached, the acquisition process returns a premature convergence on L. The only parameter we will keep fixed in all our experiments is TL, that we set to 5 seconds as it corresponds to an acceptable waiting time for a human user [START_REF] Lallemand | Enhancing User eXperience During Waiting Time in HCI: Contributions of Cognitive Psychology[END_REF]. The implementation of PACQ were carried out in Java using Choco solver 4.10.2.1 The code is publicly available at (gite.lirmm.fr/constraint-acquisition-team). All tests were conducted on an HPC node of 28 CPU cores and 128Gb of RAM. Each core is an Intel(R) Xeon(R) CPU E5-2640 v4 @2.40GHz. Our evaluation aims to answer the following five research questions:

• RQ1: How effective is an acquisition in a parallel configuration?

• RQ2: How to make PACQ more effective?

• RQ3: Is PACQ achieving a good level of load balancing between sessions?

• RQ4: How does PACQ scale with the number of sessions?

• RQ5: How effective is PACQ on distributed CSPs?

Benchmark Problems

Random. We generated binary random target networks with 50 variables, domains of size 10, and 122 binary arithmetic constraints, denoted by rand 122. PACQ is initialized with the basis B containing the complete graph of 12, 250 binary arithmetic constraints.

Purdey. The problem has a single solution. Four families have stopped by Purdey's general store, each to buy a different item and paying differently. The problem is how can we match each family with the item they bought and how they paid for it. The target network has 12 variables with domains of size 4 and 27 binary arithmetic constraints.

We initialized PACQ with a basis of 950 binary constraints.

Zebra. Lewis Carroll's zebra problem has a single solution.

The target network is formulated using 25 variables of 5 values with 5 cliques of = constraints and 14 additional constraints given in the description of the problem. PACQ is initialized with a basis B of 4, 950 unary and binary (arithmetic and distance) constraints.

Queens. (prob054 in CSPLib

2 ) The problem is to place n queens on an n × n chessboard such that the placement of no queen constitutes an attack on any other. The target network is formulated using n variables of n values and 3n * (n -1)/2 binary constraints with 3 constraints between each pair of variables ( =, out diag1 and out diag2). We take the instance of 30 queens. PACQ is initialized with a basis B of 4, 350 binary constraints.

Sudoku. The Sudoku logic puzzle is a 9 × 9 grid. It must be filled in such a way that all the rows, all the columns and the 9 non overlapping 3 × 3 squares contain the numbers 1 to 9. We run experiments also on a variant of Sudoku problem, the Jigsaw Sudoku (jsudoku) displayed in figure 1. Instead of having 3 × 3 squares, we have irregular shapes. The two target networks of sudoku and jsudoku have 81 variables of 9 values and, respectively, 810 and 811 binary = constraints on rows, columns and shapes. PACQ is initialized with B of 19, 440 binary arithmetic constraints.

Figure 1: Jigsaw Sudoku logic puzzle instance.

Latin Square. The Latin square problem consists of an n × n table in which each element occurs once in every row and column. For this problem, we use 100 variables with domains of size 10 and 900 binary = constraints on rows and columns. PACQ is initialized with |B| = 29, 700 constraints.

Meeting Scheduling. (prob046 in CSPLib 3 ) The Meeting Scheduling problem (msp) consists of n meetings and m attendees. Each meeting is of a given duration and location, and has a set of attendees. Thus, each attendee has a set of meetings that must attend. We take the instances of 40 meetings, presented in the CSPLib (msp 19 to msp 27).

The target networks contain from 75 to 125 constraints (attendee and time-arrival constraints). PACQ is initialized with |B| = 4, 680 constraints.

Results

Table 1 reports the performance of PACQ.0 averaged over ten runs on each instance. We report the number of users #U; the size of the learned network |L|; the total number of asked queries #Q in all sessions; the averaged, min and max number of queries asked per session (#q, min, max); We report results with 1, n/10 and n users, where n corresponds to the number of variables of the given instance. We denote by PACQ.x [n] the call of PACQ with n users. Note that PACQ.0 [1] is equivalent to a sequential acquisition under QUACQ.

[ RQ1]: PACQ.0 effectiveness. From table 1, we observe that parallel acquisition under PACQ reduces the number of asked queries per user #q and increases the total number of queries #Q. The number of queries per user #q is reduced by a factor ranging between 2 and 60. However, the total 3 www.csplib.org/Problems/prob046/ number of queries #Q is increased by a factor ranging between 2 and 4, which is far below the theoretical bound represented by the factor #U (Amdahl's Law [START_REF] Amdahl | Validity of the single processor approach to achieving large scale computing capabilities[END_REF]).

For instance, on latin QUACQ asks more than 11K queries to a unique user, where PACQ.0 [100] asks 192 queries per user (reduction factor of 60) with a total number of queries of 19K (growth factor of 2). Two reasons explain the growth of #Q. The first reason is related to the cost of learning a constraint (i.e., learning-ratio) that increases in a parallel configuration. For instance, we need 5 queries on average to learn a constraint of queens using QUACQ, where we need 12 queries under PACQ.0 [30] . The increase of the learningratio is due to the fact that several sessions can visit simultaneously the same part of the search space looking for the same constraint to learn where only one session succeeds at the end. The second reason that explains the growth of #Q is learning implied constraints. If c 1 ∧ c 2 ⇒ c 3 , parallel sessions can learn c 1 , c 2 and the implied constraint c 3 , where in a sequential configuration, c 3 can be removed. For instance, QUACQ converges on zebra with a constraint network of size 50. Within 25 parallel sessions, we learn a constraint network of size 70 including 20 implied constraints.

The second observation that we can draw is that a parallel acquisition speeds up the convergence. For instance, QUACQ is not able to learn the whole constraint network of the queens instance and it returns a premature convergence state. Here, generating e ∈ sol(L ∧ ¬B) is hard enough that it requires more than a TL of 5s. Whereas, PACQ.0 [3] converges in 6.15s with B split between 3 sessions, which makes example generation much easier. Let us take another example with sudoku instance. QUACQ asks more than 8K queries to learn 76% of the target network. Than it reaches a state where finding an example in sol(L ∧ ¬B) is too hard to be returned in less than 5s. Within 8 sessions, PACQ.0 asks 1, 378 queries per user to reach an acquisition rate of 94% (min, max sessions of, resp., 1, 123 and 2, 043 queries). Whereas, PACQ.0 [81] asks less than 200 queries per user to learn the whole target network and reaches a convergence rate of 99% ([min, max] = [107,346]).

[ RQ2]: Strategies and Settings. Table 2 reports the performance of PACQ.0, 1 and 2 averaged on ten runs on each instance. As table 1, we report the size of the learned network |L|; total number of queries #Q; queries per user, min and max (#q, min, max); acquisition time T A ; convergence time T C ; acquisition rate %A; convergence rate %C. We report results of 10n users, where n is the number of variables of the given instance. In terms of queries, we observe a slight difference between the three versions. However, PACQ.1 and 2 outperform the basic setting of PACQ in terms of time and convergence with the use of a dedicated heuristic bdeg and the Rule split. For instance, we need 11 seconds to acquire the jsudoku instance, where PACQ.1 and 2 acquire it in one second. On the same instance, PACQ.0 reaches (%C = 98%), where PACQ.1 and PACQ.2 slightly improve it by both reaching 99%.

[ RQ3]: Workload Balancing. From table 1 and2 In order to strengthen our previous observations, we run PACQ.0, 1 and 2 on queens with 10 sessions A 1 to A 10 . For each session, we report in figure 2 the number of queries (#q), the number of redundant queries (#RQ), the number of connected scopes (#CS) and time in seconds of each session A i . Note that RQ and CS allow us to estimate the degree of diversification between the different sessions.

The instance of queens has a target network of 1, 305 binary constraints. For the three versions, the averaged number of constraints acquired by each session is 130 with a standard deviation of 15 constraints for PACQ.0 and less than 8 constraints for PACQ.1 and 2. That is, PACQ provides a wellbalanced workload of sessions. It follows that the same observation can be made on #Q, #RQ and #CS. Comparing the three versions, we observe that PACQ.1 (using bdeg heuristic) outperforms PACQ.0 by reducing the number of redundant queries to 50% and the number of connected scopes to 90%. We also observe that using Rule based split in PACQ.2 further improves the performance. In terms of CPU time, we observe an overload for A 4 session under PACQ.0 and PACQ.1. That is, the acquisition process terminates after the close of session A 4 (7s for PACQ.0 and 7s for PACQ.1). Whereas, PACQ.2 is ensuring an excellent level of load balancing with sessions of ≈ 1s.

[ RQ4]: Scalability. From table 1, we selected the three instances where QUACQ needs to ask more than 7K queries to acquire the corresponding target network (i.e., sudoku, jsudoku and latin). We run PACQ.2 on the three instances by varying the number of users up to 1K. Figure 3 reports the total number of queries (#Q), the number of queries asked per user (#q), the learning-ratio R (i.e., the number of queries needed to learn a constraint R = #Q/|T|), the number of redundant queries (#RQ) and the number of connected scopes (#CS). Figure 3 shows that when the number of users grows, #Q follows an (a -bx -c ) scale with a = 25K, b = 18K and c = 0.74, which means that when we get more and more users, the total number of queries gets closer and closer to the bound a = 25K, which is far below the Amdahl's Law theoretical bound [START_REF] Amdahl | Validity of the single processor approach to achieving large scale computing capabilities[END_REF] represented by number of queries asked by QUACQ (> 8K) multiplied by #U. The second observation is that when the number of users grows, the number of queries asked per user #q follows a negative power function scale (a x -b ) with a = 11K and b = 0.85, which means that when we get more and more users, number of queries asked per user gets closer and closer to 0 (horizontal asymptotes of negative power functions). This is very good news as it means that learning problems in parallel will scale well. For instance, QUACQ asks more than 8K to one user to learn sudoku instance. PACQ with, respectively, 2, 10, 100 and 1000 parallel sessions, asks to the same user, respectively, 3K, 1K, 163 and 13. Also, the learning-ratio R scales well when the number of users grows. The number of queries asked to learn one constraint follows a logarithmic scale bounded above by 35 queries per constraint (c log(x) + d with c = 3 and d = 8). Following the conclusions drawn in RQ3 and thanks to bdeg heuristic and Rule based split, we observe that #RQ and #CS per user decreases when the number of users grows. That is, PACQ.2 ensures an excellent level of workload balancing between sessions up to 1K.

[ RQ5]: PACQ for distributed CSP. For our last experiment, we illustrate the use of PACQ on distributed CSP with msp problem. In msp, each attendee comes with her own constraints and shares meetings (i.e., variables) with the other attendees. This means that the problem can be acquired in a fully-distributed scheme by having a session per attendee. Figure 4 reports %A and %C rates performed by QUACQ, PACQ.2 [v] and PACQ.3 [v] (where v ∈ {9, 13, 14, 17} is the number of attendees) on the 9 msp instances. Darker color indicates higher convergence rate. The number in each cell indicates the acquisition rate. The sequential version using QUACQ is not able to learn and to converge on the 9 instances. PACQ.2 is not converging. However, PACQ.3 learns and converges on the 9 instances. For instance, on msp 21 QUACQ learns 58% of the target network and returns a premature convergence of 62% in 10 seconds. PACQ.2 learns the instance without converging (%C = 84%) in 8s. Then, the distributed version with PACQ.3 converges

Conclusion

In this paper we proposed a parallel constraint acquisition system PACQ, where numerous users answer in parallel queries in order to learn all the constraints. PACQ is a parallel extension of QUACQ and preserves the fundamentals of its active learning system and its soudness, correctness and completeness properties. Performed experiments showed that (i) PACQ ensures an excellent level of load balancing; (ii) the total number of queries increases under an upper-bound; (iii) when the number of users grows, the number of queries asked per user gets closer and closer to zero.

  is called a partial assignment when Y ≺ X and a complete assignment when Y = X. An assignment e Y on a set of variables Y X is rejected by a constraint c S (or e Y violates c S ) if S Y and the projection e Y [S] of e Y on the variables in S is not in c. If e Y does not violate c S , it satisfies it. An assignment e Y on Y is accepted by C if and only if it satisfies all constraint in C. An assignment on X that is accepted by C is a solution of C. We write sol(C) for the set of solutions of C, and C[Y ] for the set of constraints from C whose scope is included in Y .

  Ui (e, ∅, X); 8 acquire(scp); 9 if κ B (e[scp]) = ∅ then FindC Ui (e, scp, L); 10 release(scp);

  time T A needed to learn L; time of the learning process until convergence T C ; the acquisition rate %A = |T | -|L |/|T |, where L are the constraints that have to be added to L to make it equivalent to T ; and the convergence rate %C = (B init -B final )/B init , where B init and B final are, respectively, the initial and the final size of the the basis B. T A and T C are CPU times of the last closed session. That is, we report the maximum (T A , T C ) times needed for a given session.

Figure 2 :

 2 Figure 2: PACQ acting on 30-queens with 10 users

Figure 3 :

 3 Figure 3: Scalability of PACQ.2 up to 1K users

Figure 4 :

 4 Figure 4: %A and %C comparison (QUACQ, PACQ.2 and 3)

Table 1 :

 1 , we observe that PACQ.2 provides well-balanced sessions in terms of queries with values close to the mean comparing PACQ.0 results

	#U	|L| #Q	(#q, min, max) (TA, TC) %A %C
	rand 122:
	1	116 1K	1K	(4, 9)	100 100
	5	116 4K	(898, 781, 973)	(4, 5)	100 100
	50	117 4K	(90, 18, 475)	(0, 2)	100 100
	purdey:
	1	17 159	159	(0, 0)	100 100
	2	15 154	(77, 70, 84)	(0, 0)	100 100
	12	30 372	(31, 20, 44)	(0, 0)	100 100
	zebra:
	1	50 601	601	(1, 1)	100 100
	3	61 852	(284,276 , 340)	(0, 0)	100 100
	25	70 1K	(53, 41, 108)	(0, 0)	100 100
	queens:
	1 1295 6K	6K	(-, -)	99 99
	3 1305 8K	(2K, 2K, 2K)	(4, 6)	100 100
	30 1305 16K (534, 470, 577)	(2, 5)	100 100
	sudoku:
	1	621 8K	8K	(-, -)	76 96
	8	769 11K	(1K, 1K, 2K)	(-, -)	94 99
	81	801 15K (195,100 , 346)	(2, -)	100 99
	jsudoku:
	1	586 7K	7K	(-, -)	72 95
	8	746 9K	(1K, 1K, 1K)	(-, -)	92 98
	81	791 12K (155, 107 , 188)	(10, -)	100 99
	latin:
	1	818 11K	11K	(-, -)	90 98
	10	879 13K	(1K, 820, 1K)	(-, -)	99
	100	898 19K	(192, 65, 1K)	(10, -)	100 99
	msp 27:
	1	92 1K	1K	(-, -)	36 63
	4	134 1K	(390, 202, 410 )	(-, -)	53 77
	40	223 2K	(71, 20, 79)	(-, -)	89 89
	#q

Table 2 :

 2

PACQ (P.) 0, 1 and 2 results with 10n users. 200 queries. However, PACQ.2 asks queries per user in a tight interval of [7, 66] with a standard deviation of 13.

The Thirty-Fifth AAAI Conference on Artificial Intelligence (AAAI-21)

github.com/chocoteam/choco-solver

www.csplib.org/Problems/prob054/

Acknowledgments

This work has received funding from the European Union's Horizon 2020 research and innovation programme under grant agreement No 952215. This work also received support from University of Montpellier and I-Site MUSE under CAR-UM2020/2021 project. We thank Nassim Belmecheri and Yahia Lebbah who provided insight and expertise that greatly assisted the work. We would also like to show our gratitude to the "anonymous" reviewers for their insightful suggestions and careful reading.