NMUS: Structural Analysis for Improving the Derivation of All MUSes in Overconstrained Numeric CSPs

NMUS: Structural Analysis for Improving the Derivation of All MUSes in Overconstrained Numeric CSPs R.M.Gasca,C.DelValle,M.T.G´omez-L´opez, and R. Ceballos Departmento de Lenguajes y Sistemas Inform´aticos. Escuela T´ecnica Superior de Ingenier´ıa Inform´atica. Universidad de Sevilla. (Spain) {gasca,carmelo,mayte,ceballos}@lsi.us.es Abstract. Models are used in science and engineering for experimentation, analysis, model-based diagnosis, design and planning/sheduling applications. Many of these models are overconstrained Numeric Constraint Satisfaction Problems (NCSP), where the numeric constraints could have linear or polynomial relations. In practical scenarios, it is very useful to know which parts of the overconstrained NCSP instances cause the unsolvability. Although there are algorithms to find all optimal solutions for this problem, they are computationally expensive, and hence may not be applicable to large and real-world problems. Our objective is to improve the performance of these algorithms for numeric domains using structural analysis. We provide experimental results showing that the use of the different strategies proposed leads to a substantially improved performance and it facilitates the application of solving larger and more realistic problems. 1 Introduction A lot of Artificial Intelligence problems can be cast in terms of Numeric Constraint Satisfaction Problems (NCSPs), and a large number of systems have been developed to compute efficiently solutions of these problems. NCSPs are more and more often used to solve engineering problems arisen in different areas such as qualitative reasoning, diagnosis, planning, scheduling, configuration, distributed artificial intelligence, etc... This work focuses on problems related to engineering field, what play a prominent role in industrial applications. Generally, these problems are formed by a set of constraints among variables whose domains are real interval values. Usually, the numeric constraints are linear or polynomial relations (equations or inequations). However, not every set of numeric constraints is satisfiable. Different researchers have proposed methods for the identification of Minimally Unsatisfiable Subsets of Constraints (MUSes) or Conflict Sets (CS)astheyarealso namedinoverconstrainedCSPs. Determining MUSes can be very valuable in many industrial applications, because it describes what is wrong in a NCSP instance. They represent the smallest explanations -in terms of the number of involved constraintsof infeasibility. Indeed, when we check the consistency of aNCSP, we prefer knowing which constraints are contradicting one another rather than only knowing that the whole NCSP is inconsistent. In the bibliography, different types of CSPs have been treated in order to obtain the MUSes. They are related to Satisfiability Problems [8] [2] [13] [7], Disjunctive Temporal Problem (DTP) [11] [9] [12] and model-based diagnosis and debugging problems [10] [5] [6] [1] [3]. Due to the high computational complexity of these problems, the goal of most of these approaches was to reduce the amount of satisfaction checking and subsets examined. However, some approaches were designed to derive only some MUSes and no all MUSes of these overconstrained CSPs. To derive MUSesin overconstrained NCSP, we are aware of very few technical works. In [4], Irreducible Infeasible Subsets (IIS) was studied for only linear and integer domains, but not all MUSes are obtained. These problems may contain multiple MUSes, and all of them must be resolved by constraint relaxation before the NCSP can be solved. Also, other authors of the model-based diagnosis community have treated the high complexity of these problems using constraint databases [6] and new concepts such as constraint clusters and nodes [3]. In this paper, a set of new derivation techniques are presented to obtain efficiently MUSes of a overconstrainted NCSP. These techniques improve the complete technique in several ways depending on the structure of the constraint network. It makes use of the powerful concept of the structural lattice of the constraints and neighborhood-based structural analysis to boost the efficiency of the exhaustive algorithms. As systematic methods for solving hard combinatorial problems are too expensive, structural analysis offers an alternative approach for quickly generating all MUSes. Accordingly, experimental studies of these new techniques outperform the best exhaustive ones. They avoid to solve a high number of NCSPs with exponential complexity, however they add some new procedures with polynomial complexity. The rest of the article is organized as follows. In Section 2, we start presenting some examples of overconstrained NCSPs to introduce the problem domain. Section 3 presents some definitions and notations. Section 4 exposes different neighborhood concepts based on the structural analysis of the constraint network. Afterwards, we propose different search algorithms for deriving numeric MUSes in a efficient way and their experimental results are argued in Section 5. Finally, in the last section we present our conclusions and future work. 2 Motivating Examples The parts of an overconstrained NCSP instance that could cause the unsolvability are the variables domains or constraints of the problem. Only this last cause will be treated in this article. In the following subsections, we specify some different NCSP instances to motivate this work. The specification of a NCSP instance is represented by Ψ, C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 C11 C12 10 10 10 10 X Y Fig. 1. Overconstrained NCSP with same real variables for all constraints the variables by XΨ, the domains by DΨ, the constraints by CΨand the goals by GΨ. In this last item, the modeler could also specify which constraints would be preferred for relaxing. 2.1 NCSP with the Same Real Variables for All Constraints An example is the following geometrical problem, where the overconstrained NCSP instance has linear equations and polynomial equations/inequations: Ψ≡ ⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ XΨ={x, y} DΨ={x, y ∈[−10,+10]}, CΨ={c1≡x2+y2<4,c 2≡(x−7/2)2+y2<4,c 3≡x∗y>1, c4≡x+y=0,c 5≡y+(x−1)2=5,c 6≡(x+4) 2+y2=1, c7≡y=6−(x+3) 2,c 8≡(x+8) 2+(y−4)2=1, c9≡(x−8)2+(y−4)2=1,c 10 ≡y=5+(x−4)2, c11 ≡y=6+2∗(x−4)2,c 12 ≡(x−8)2+(y−7)2=1} GΨ=Solutions(X)? Why? This problem has no solution, but the question is what cause it. In this case, Ψ exhibits the following MUSes, namely {c1,c 2,c 5},{c10,c 11},{c9,c 12}, etc... 2.2 NCSP with Some Different Variables for the Numeric Constraints The following example is extracted from a recent work in the model-based diagnosis community [3], where the miand aiconstraints corresponds to multipliers and adders respectively. This is a very illustrative example to show the utility of the structural analysis: M1 M2 M3 A2 A1 a b c d e x01 x02 x03 p q M4 M5 M6 A4 A3 f g h i j x04 x05 x06 r k m n o M7 M8 M9 A A 5 6 x07 x08 x09 x10 x12 x11 M1 M2 M3 A2 A1 a b c d e x01 x02 x03 p q M4 M5 M6 A4 A3 f g h i j x04 x05 x06 r k m n o M7 M8 M9 A A 5 6 x07 x08 x09 x10 x12 x11 Fig. 2. Overconstrained NCSP with different real variables for all constraints Ψ≡ ⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ XΨ={a, b, c, d, e, f, g, h, i, j, k, m, n, o, p, q, r, xi(i∈{1, ..., 12})} DΨ={xi∈(−∞,+∞), a, b, c, d, e, f, g ∈[2,4] k,m,n,o ∈[3,5] p, q, r ∈[15,18])} CΨ={m1≡a∗c=x01,a 1≡x01 +x02 =x08, etc...} GΨ=Solutions(X)? Why? 3 Definitions and Notations In the previous section, some overconstrained NCSPs in terms of examples have been shown. This section presents some necessary definitions to formalize and clarify the derivation of all MUSes in these problems. Definition 3.1 (Numeric Variable). A variable of the NCSP whose domain is a real interval value. The set of numeric variables of the problem is denoted by XΨand XΨ(ci) stands for the set of variables of a constraint ci. Definition 3.2 (Numeric Constraint). It is a linear or polynomial relation (equations or inequations) involving a finite subset of numeric variables. Definition 3.3 (Goal). A predicate that denotes the users’ preferences to search why the NCSP is overconstrained. Definition 3.4 (Numeric Constraint Satisfaction Problem). A four-tuple Ψ=(X,D,C,G)whereXΨ={x1, ..., xn}is a set of variables, whose continuous domains are respectively DΨ={d1, ..., dn}(n≥1), CΨ={c1, ..., cm}(m≥1) is a set of numeric constraints and GΨis the goal. Definition 3.5 (Overconstrained NCSP). It is a NCSP with no solution caused by some of the domains or constraints contradicting others. When a NCSP instance is unsatisfiable, it has at least one Numeric Minimally Unsatisfiable SubSet,inshortoneNMUS. It is a set of numeric constraints which is unsatisfiable, but becomes satisfiable as soon as we remove any of its constraints. Definition 3.6 (Numeric Minimally Unsatisfiable SubSet). Given an instance Ψof a NCSP,aMUSμis a set of numeric constraints s.t. μ⊂CΨ,μis unsatisfiable and ∀δ∈μ,μ\{δ}is satisfiable. The number of constraints in a MUS is its cardinality and it is represented by #μ. Generally, we can have more than one MUS in the same NCSP.Someof them can overlap, in the sense that they can share some constraints, but they cannot be fully contained one in another. This concept of MUS have similarities with that one of IIS in the case of systems of linear inequalities. 4 Neighborhood-Based Structural Analysis To construct a practical system developing a complete and efficient method for deriving numeric MUSes is a key issue in real-world and industrial applications. In this paper, the option for an important reduction of the search space is based on the structural analysis. For this reason, the concept of neighbors of a given assignment of the constraints of a NCSP is defined. Definition 4 (Assignment). It is the tuple of values {0,1}assigned to each constraint of a NCSP instance Ψ, meaning the truth value of each constraint. It is represented by A(CΨ). For example, in a NCSP with five numeric constraints an assignment could be (c1,c 2,c 3,c 4,c 5)≡(1,0,0,1,0). 4.1 General Neighborhood Definition 4.1 (Neighbor Assignment). GivenanassignmentA(CΨ), a neighbor assignment is defined by a new assignment A(CΨ)thatdiffersinexactly one truth value. For a given assignment A(CΨ), one option could be to consider all alternatives whose variable assignments differ in exactly one position; for example, the assignment (c1,c 2,c 3,c 4,c 5)≡(1,0,0,1,0) would be a neighbor of (c1,c 2,c 3,c 4,c 5) ≡(1,0,0,1,1), since they both differ only on the assignment to c5. However, as each civariable may take these different values, the cardinality of the set of possible neighbors could be very high. But, it could be reduced in a significant way, taking into account the structural aspects of the constraint network of the NCSP. In this article, two clear options of neighborhood are used: when the variables of all the constraints of NCSP are identical then we define the concept of domain-based neighborhood; in other cases we define the concept of variable-based neighborhood. 4.2 Variable-Based Neighborhood An important aspect in this concept is the notion of Non-Observable Numeric Variable of a NCSP instance. For these variables, there is not any information about their domains. Definition 4.2.1 (Non-Observable Numeric Variable). It is a numeric variable of a NCSP, whose initial domain in the problem specification is (−∞, +∞). For the example in the subsection 2.2, the neighborhood is based on the common non-observable numeric variables between constraints. Definition 4.2.2 (Variable-based Neighbor Assignment of Constraints). GivenanassignmentofA(CΨ), a neighbor is defined by a new assignment A(CΨ) that differs in exactly one truth value of a constraint with some common non-observable variable to the constraints with truth values equals 1. 4.3 Domain-Based Neighborhood Another neighborhood concept is when all numeric constraints of an overconstrained NCSP instance have the same variables. In this case we could use the projection operator of a variable xi∈XΨw.r.t. a constraint cj∈CΨis represented as Πxi(cj). In the same way, the projection operator of a variable xi∈XΨ w.r.tasetofconstraintCΓ⊂CΨthat is represented as Πxi(Cγ). Then, the new concept for deriving MUSes is the domain-based neighborhood. A constraint ci∈CΨcould be domain-based neighbor of another set of constraint Cγ⊂CΨ|ci∈ Cγwhen the intersection of the projections for all variables of set XΨis not empty: ∀xk∈XΨΠxk(ci)∩Πxk(Cγ)=∅ Definition 4.3 Domain-based Neighbor Assignment of the Constraints GivenanassignmentofA(CΨ), a neighbor is defined by a new assignment A(CΨ) that differs in exactly one truth value of a constraint and all projection operations of the variables w.r.t. a set of the numeric constraints with truth value equals 1 is not empty. With this definition we are sure of the domain-based neighborhood, but it could happen that the intersection of all the projections are not empty and the constraints are unsatisfiable. For this reason, it is necessary to solve a NCSP. 5 NMUS: Numeric MUSes Search Methods In this section, a set of methods NMUS is presented to efficiently derive all MUSes using the Neighborhood-based Structural Analysis on overconstrained NCSP. We describe different bottom-up derivation strategies taking into account the concept of neighborhood for the different types of problems. The search methods are different depending on the structural aspects of these problems. 5.1 NMUS for NCSPs with the Same Variables for All Constraints A basic algorithm would study all the 2n−1 combinations of constraints in order to determine all MUSes of an overconstrained NCSP instance Ψ,where nis the cardinality of the set CΨ. The proposed method is complete, but it is very inefficient and no practical. For this reason, this work proposes different strategies to improve this algorithm. Let MUS be a data structure List of Sets where the MUSes are stored and Qa data structure type Queue of Sets where the active constraints and its projections w.r.t the variables of the problem are stored. The function poll() retrieves and removes the head of a queue or null if the queue is empty. First Improvement (NMUS-1): Only Inclusion in queue of satisfiable subsets. This first improvement will include in the queue Qonly subset of constraints that are satisfiable. Given an overconstrained NCSP instance Ψ, the algorithm is shown in Algorithm 1. Alg. NMUS-1 (Ψ:NCSP) Let CΨ={c1,...,c n}be constraints of the overconstrained NCSP instance Q:= Queue with a set for each satisfiable numeric constraints belong to CΨ MUS := List with the set of unsatisfiable numeric constraints belong to CΨ while (Qis not Empty) {ci... c j}:=Q.poll() for (ck∈{cj+1 to cn}) if (NOT ∃SubSet1...n−1 {ci...cj}∪ck∈MUS)// n is cardinality of {ci...c j} if ({ci... c j}∪ckis satisfiable) // aNCSP must be solved Q.add({ci... c j}∪ck) else MUS.add({ci... c j}∪ck) endIf endIf endFor endWhile Algorithm 1. NMUS-1 (Ψ:NCSP) In this algorithm, the neighborhood concept is not taken into account and the satisfiability could be checked using NCSP solvers. Second Improvement (NMUS-2): Using Domain-based neighborhood In this algorithm, two concepts are used: domain-based neighborhood and overlapping projection. The initialization procedure is the same as the previous algorithm. The new algorithm is shown in Algorithm 2. The function Overlap Projection(Constraint c, Constraints List lc) returns true if it exists overlapping between the projection of the constraint cand the projection of lcw.r.t. every variable. If this function returns false, it means that it exists aMUS formed by cand some constraints of lc,therebyc∪lc is not a MUS. Alg. NMUS-2(Ψ:NCSP) ............... // Initialization while (Qno Empty) {ci... c j}:= Q.poll() // a list of satisfiable constraints are obtained for (ckin {cj+1 to cn})// it avoids to obtain redundant solutions if (Overlap Projection(ck,{ci... c j})AND NOT ∃SubSet1...n−1 {ci...cj}∪ck∈MUS if ({ci... c j}∪ckis satisfiable) // aNCSP is created Q.add({ci... c j}∪ck) else MUS.add({ci... c j}∪ck) endIf else if(#{ci... c j}=1) MUS.add({ci... c j}∪ck) endIf endIf endFor endWhile Algorithm 2. NMUS-2 (Ψ:NCSP) Third Improvement (NMUS-3): Sorting constraints according to the overlapped domain. The heuristic used in this algorithm is based on the quick search of MUSes. First of all, the algorithm sorts the constraints depending on the number of projections that intersect with the projections of other constraints. It is possible to check the satisfiability only analysing the minimum and maximum value of each variable in the different constraints, no being necessary to solve a NCSP. The previous algorithms add subsets of constraints in the queue Qwhen a subset of constraints is satisfiable. If we analyze first the less promising subsets, there will be less possibilites yo add these constraints to Q. 5.2 NMUS for NCSPs with Some Different Variables for the Numeric Constraints In this algorithm, we will apply a different neighborhood concept, the variablebased one. The initialization procedure is the same as in the previous algorithm, but the data structure Qcan be now a Queue, a Stack or another data structure depending on the different search strategy. This structure must have a new method add which includes a tuple Cγ,NOBV(Cγ),whereNOBV(Cγ)) represents the set of non-observable variables of Cγ. Depending on the type of structure Q, the search process will be depth-search or breadth-search, what will determine two different algorithms NMUS-4 and NMUS-5 respectively (Algorithm 3). Alg. NMUS-4-5(Ψ:NCSP) ............... // Initialization while(Qis not Empty) Cγ,NOBV(Cγ):= Q.poll() // chose a element belong to Q neighbors := expand (Cγ,NOBV(Cγ))// generate neighbours according variable-based neighborhood foreach (ck,NOBV(ck)∈neighbors) if(Cγ∪ckis satisfiable)// aNCSP is created Q.add(Cγ,NOBV(Cγ)∪ck,NOBV(ck)) else MUS.add(Cγ,NOBV(Cγ)∪ck,NOBV(ck)) endIf endFor endWhile Algorithm 3. NMUS-4-5(Ψ:NCSP) 6 Experimental Results NMUS is a prototype that includes all previous algorithms. This prototype is implemented in Java and runs on an AMD Athlon Dual Core 2.21 GHz with 1.78 GB Ram. The standard routine used for solving NCSP belongs to ILOGTMJSolver. The different algorithms of this prototype improve the performance of basic algorithms for numeric domains using the structural analysis. We provide experimental results showing that the use of the different strategies proposed leads to substantially improved performance and facilitates to solve larger and more realistic problems. The following table reports the experimental results for the different examples of the Section 2 when a domain-based or a variable-based neighborhood are used. NMUS-5 is more efficient than NMUS-4 since using a breadth search approach we can detect more easily the redundant sets of constraints that are generated. The examples show also a significant improvement w.r.t. the basic algorithms. Therefore these algorithms provide a realistic method for deriving all numeric MUSes of a given problem. Table 1. Experimental Results for examples in Section 2 Algorithms Example 2.1 Algorithms Example 2.2 #NCSPsTime(ms) Time (ms) Basic Alg. 212 −1 = 4095 40210 Basic Alg. 1017 NMUS-1 88 8692 NMUS-4 16,8 NMUS-2 58 7500 NMUS-5 2,0 NMUS-3 57 2340 7 Conclusions and Future Work The derivation of all MUSes for overconstrained NCSP is a computationally hard problem and arises in a lot of industrial problems. This problem has been formally defined in this paper and different methods for deriving all NMUSes