Improving the Computational Efficiency in Symmetrical Numeric Constraint Satisfaction Problems

Improving the Computational Efficiency in Symmetrical Numeric Constraint Satisfaction Problems R.M.Gasca,C.DelValle,V.Cejudo,andI.Barba Departmento de Lenguajes y Sistemas Inform´aticos. Universidad de Sevilla. (Spain) {gasca, carmelo, cejudo, irene}@lsi.us.es Abstract. Models are used in science and engineering for experimentation, analysis, diagnosis or design. In some cases, they can be considered as numeric constraint satisfaction problems (NCSP). Many models are symmetrical NCSP. The consideration of symmetries ensures that NCSP-solver will find solutions if they exist on a smaller search space. Our work proposes a strategy to perform it. We transform the symmetrical NCSP intoanewNCSP by means of addition of symmetry-breaking constraints before the search begins. The specification of a library of possible symmetries for numeric constraints allows an easy choice of these new constraints. The summarized results of the studied cases show the suitability of the symmetry-breaking constraints to improve the solving process of certain types of symmetrical NCSP. Their possible speedup facilitates the application of modelling and solving larger and more realistic problems. 1 Introduction Symmetries are common in science and engineering applications. It is due to the inherent symmetry of the physical world. Some examples are: electron spin in atoms, inertial changes in mechanics, electromagnetism, some organic chemical compounds, etc... Many problems in these applications exhibit a high degree of symmetry that can be exploited successfully for solving them. Backtracking and consistency techniques are conventional methods to solve constraint satisfaction problems (CSPs). Reducing complexity is the major issue in solving CSPs, specially when there is a large number of constraints and/or wide domains of the variables. In first works, the symmetries have been considered in problems where variables have discrete domains and to remove symmetrical solutions by changing the CSP solved [14]. Also, the symmetries are used in the detection and exploitation in planning problems [6], reasoning and optimization [4], the generation of balanced incomplete block designs [13] and applications to low autocorrelation binary sequences [8]. Other approaches consider the design of a new search method that avoids testing of possible symmetrical subsolutions [1] and the addition of constraints during the search [15]. Numeric Constraint satisfaction problems (NCSP) are more and more often used to solve engineering problems arisen in different areas of Artificial Intelligence (qualitative reasoning, diagnosis, planning, scheduling, configuration, distributed artificial intelligence, etc...). These problems are formed by a set of constraints among variables whose domains are real interval values. Constraintsolving systems have as a goal to find all solutions, only one solution, or if the model that represents the problem is or not consistent. The symmetrical NCSP (SNCSP) has a set of symmetrical properties or symmetrical constraints. These problems that contain symmetries may be solved most efficiently. The search effort can be reduced specially on hard and large problems. In Numerica [16] the symmetry property of NCSP has been considered by means of soft constraints. These constraints are equivalent to other ones except that they are ignored when the existence of solutions is proved. Reasoning about the ranges of values of variables is a type of reasoning often used when there are inaccurate data or partially defined parameters. It can be also generalized as a NCSP. A natural way of reasoning on the ranges of values is to propagate the domains of the variables through the constraints. It involves assigning values to variables in order to satisfy constraints among subsets of those variables. These problems can be solved efficiently by combining local consistency methods, such as approximations of arc-consistency, together with a backtracking-based search. Different problem solving techniques have been proposed in the bibliography [9] [11] [2] [16] [10]. The search space in numeric constraint problems is usually too wide and a lot of these techniques have a major drawback since they introduce choice points and they are exponential. The efficiency of some previous algorithms was analyzed in a previous work [3]. Another work [16] for improving the accuracy and efficiency in solving NCSP has been proposed by reducing dependencies and variable elimination. Our proposal considers that the symmetry property of NCSP can speed-up significantly its solving process. Although NCSP modeling is the necessary step preceding CSP solving, little work has been done to help modelers. In this line, our method provides a library of symmetries that allows modelers to remove some symmetries in SNCSP.The modeler selects and adds symmetry-breaking constraints of this library, reducing the search space. These additions are performed by hand and require a previous analysis of the modeler. It must not affect the soundness and completeness of the solutions. Nevertheless, the modeler must also consider the increase of the computational cost after adding these new constraints in the original NCSP.This paper is interested in reformulating concise models that support more efficient solutions. The rest of the article is organized as follows. In Section 2, we start presenting some examples of SNCSPs to introduce the problem domain. Section 3 presents some definitions and preliminaries. Section 4 exposes a simple library of symmetries to be taken into account in symmetrical NCSPs and proposes the selection of modelling schemas and their solving process. The experimental results are presented in Section 5. Finally, in the last section we present our conclusions and future work. 2 Illustrative Examples In order to clarify the aim of this work, the following geometrical problem is very illustrative: Model ≡ ⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ X={x, y} D={x, y ∈(−∞,+∞), C={x2+y2=4,x∗y=1} G=AllSolutions(X) For this problem, the search space is IR2, but if we consider the symmetries, this space is reduced four times. In fact, this reduction improves significantly the computational complexity of the search process. Also we have selected two examples from different Artificial Intelligence areas, the first problem is commonly used in order of magnitude reasoning and the second one is an example of a configuration task. Both examples are specified by means of a four-tuple: –X, the set of variables of the model, –D, the set of domains of the variables, –C, the set of relations of the variables of the model, and –Gthe goal of the model analysis. This representation allows an easy mapping from this specification to a NCSP. 2.1 A Countercurrent Heat-Exchanger This problem is studied in order of magnitude reasoning [12] and [5]. A schema of a countercurrent heat-exchanger is shown in Figure 1. The important variables in the analysis of the device are the molar-heat KH and the molar-flowrate FH of the hot stream, and the molar-heat KC and the molar-flowrate FC of the cold stream. Also, the temperature differences have been named DTH =Th1− Th2,DTC=Tc1−Tc2,DT 1=Th1−Tc1,DT 2=Th2−Tc2. The temperature drop of the hot stream is DTH, the temperature rise of the cold stream is DTC and the driving force at the left and right ends of the device are DT1and DT2 hot cold DTH DTC DT 1DT 2 Th2 Th 1 Tc 1Tc 2 Fig. 1. A countercurrent heat-exchanger respectively. The numeric constraints of the problem are the energy balance of the exchanger and the result from the definition of the temperature differences: DTH ∗KH ∗FH =DTC ∗KC ∗FC and DTH −DT1−DTC +DT2=0. In a particular case, the following order of magnitude relations may be known: DT2is moderately smaller than DT1and DT1is much smaller than DTH.A possible analysis of the model could consists in obtaining the qualitative relation between FC and FH. Model ≡ ⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ X={DTH,KH,FH, DTC,KC,FC, DT1,DT 2} D={DTH,KH,FH, DTC,KC,FC, DT1,DT 2∈(−∞,+∞), r1∈[0.1,0.9] r2∈[0,0.1] r3∈[0,+∞)} C={−DTC ∗FC ∗KC +DTH ∗FH ∗KH =0, −DTC +DTH −DT1+DT2=0,DT 2−DT1r1=0, DT1−DTH r2=0,FC−FH r3=0} G=Solution(r3) where r1,r 2are the corresponding intervals for the order of magnitude relations and r3is the interval for the unknown order of magnitude relation. Due to the symmetrical properties of this model it may be considered as a SNCSP. In the last section, the modeler specifies that he would like to know one solution of the unknown order of magnitude relation. 2.2 Structural Configuration of Resistors This example presents a given configuration of resistors as shows Figure 2. The modeler has the aim of selecting from two types of resistors whose values may be [9.8,10.1]Ωor [99.6,100.4]Ωin order to obtain an equivalent total resistor whose value is [149.5,150.5] Ωaccording to the previous configuration. This problem can be modelled by means of the four-tuple below. The goal of the modeler is to search for only one possible solution. This problem can be solved using the previous mentioned NCSP techniques, but the computational effort is exponential. We propose to exploit the symmetries of this problem in order to achieve better computational costs. Model ≡ ⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ X={R1,R 2,R 3,R 4,R 5,R 6,R 7,R 8,R 9,R 10,R} D={R1,R 2,R 3,R 4,R 5,R 6,R 7,R 8,R 9, R10 ∈[9.8,10.1],[99.6,100.4],R∈[149.5,150.5]} C={(R1∗R2)/(R1+R2)+ (R3+R4)∗R5∗R6/(R3+R4+R5+R6)+ (R7+R8)∗(R9+R10)/(R7+R8+R9+R10)=R G=OneSolution(X) R1 R2 R3 R5 R4 R6 R7 R9 R8 R10 Fig. 2. Configuration problem with resistors 3 Definitions and Notation We have presented informally SNCSP in terms of examples. This section presents a number of definitions for the formalization of symmetrical NCSP. The variable domains in these problems are real intervals. Definition 1 (Interval). Let IF denote a finite subset of IR augmented with the symbols {−∞,∞}.Ifa, b ∈IF then an interval [a, b] represents the set of real numbers {r∈IR |a≤r≤b}. Definition 2 (Numeric Variable). A variable of the model whose domain is a real interval. The set of numeric variables of the problem is denoted by X. Definition 3 (Numeric Constraint). It is a relation (equations) involving a finite subset of numeric variables. Definition 4 (Goal). A predicate that denotes the users’ preferences to search for only one solution, all solutions or the consistent domain of certain variables. Definition 5 (Numeric Satisfaction Problem). A four-tuple P=(X,D,C,G) where X={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 Gare the goals. Definition 6 (Symmetrical NCSP). ANCSP that has symmetry constraints. Definition 7 (Solution). An instantiation of the numeric variables such that all constraints are satisfied. They correspond to n-dimensional cubes, that are named hypercubes. We use Ψto denote a SNCSP(X,D,C, G). Ψhas a set of transformations TΨ= {T1, ...Tm}. Every transformation Ti∈TΨhas associated a finite set of expressions over the variables of the problem αi={α1 i(X),α 2 i(X), ..., αk i(X)}and a set of real regions associated to the previous expressions Ωi={Ω1 i(X),Ω2 i(X), ..., Ωk i(X)}. For example in the following SNCSP: Model ≡ ⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ X={x, y} D={x, y ∈(−∞,+∞), C={x2+y2=4,x∗y=1} G=AllSolutions(X) some transformations are shown in Table 1. Table 1. Symmetrical transformations of a previous example Transformations α Ω T1≡Permutations(x, y)α1 1(x, y)≡x=y∧y=x Ω1 1(x, y)≡y≤x Ω2 1(x, y)≡y≥x T2≡Symmetry(x,y)α1 2(x, y)≡x=−x∧y=−y Ω1 2(x, y)≡x+y≥0 Ω2 2(x, y)≡x+y≤0 Every symmetrical transformation belonging to the set TΨmust be invariant. Let Ti∈TΨbe a transformation that has associated an expression X=αi(X). A transformation is invariant if Ti(Ψ)≡Ψwhere ≡denotes symbolic equality. The transformation of Ψis obtained by means of the symbolic substitution of the variables Xby expressions αi(X), Ti(Ψ)=Ψ[αi(X)/X]i∈{1, ..., m} Let Ωi(X) be a finite set of associated regions for a transformation Ti(Ψ), where Ωi(X)={Ω1 i(X),Ω2 i(X), ..., Ωk i(X)} The elements of this set must satisfy the following properties: –Minimum overlapping of regions ∀s, t :s, t ∈1..k ∧s=t|Ωs i(X)∩Ωt i(X) may be a hyperplane of a lower dimension with respect to the dimension of the search space. –To fill in the search space jΩj i(X)=IRnwhere nis the cardinality of the set Xand j∈{1,2, ..., k}. –Obtaining the next regions ∀s∈1..k −1|Ti(Ωs i(X)) = Ωs+1 i(X) and if kis finite, then Ti(Ωk i(X)) = Ω1 i(X) 4 Symmetry Analysis in Symmetrical NCSP The aim of symmetry analysis is the identification of symmetries and the generation of the corresponding symmetry-breaking constraints. The search for symmetries in the initial SNCSP are performed by hand and requires a previous symmetry analysis. This analysis always must ensure the soundness and completeness of the search. The symmetry analysis has the following steps: 1. Identification of possible symmetries of a SNCSP. These problems may have an infinite number of symmetries and also some symmetries are hard to calculate. It determines that in this work we only identify the simplest symmetries. There are several approaches to identify these symmetries: –the symmetry-breaking constraints are derived from the model. –the symmetry-breaking constraints are derived from a visual representation of the model –Some tools calculate the symmetry-breaking constraints. The first item of the above list may be adequate to carry out the identification of the symmetries in symmetrical NCSP. 2. Reduction of the domain variables or generation of symmetry-breaking constraints, that are related to the different regions of the transformations. 3. Determination of the expressions to calculate symmetrical solutions and transformation of the variables’ domains in order to ensure the completeness of the search. It depends on the users’ goals. For example, if the goal is to obtain all the solutions of a SNCSP then we determine these expressions. 4.1 Numeric Symmetries Library The consideration of symmetries in symmetrical NCSP can be a hard process. There is no known polynomial algorithm to detect all the possible symmetries. This work only considers a partial analysis of the symmetries which covers the most elemental numeric symmetries. It is named Numeric Symmetry Library (NSL) and includes the following symmetries: •Permutations 1. Transformation: Given a set X⊆Xwhose elements are X= {x1, ..., xm}, the number of permutations in this set is k=m!. 2. The regions of the transformation Permutation are Ω1(X)≡x1≤x2≤... ≤xm Ω2(X)≡x2≤x1≤... ≤xm .............................................. Ωk(X)≡xm≤... ≤x2≤x1 One of these regions can be added to break symmetries. 3. The symmetric solutions are obtained as the permutations of the previous solutions. According to the notation used before, if s1is a solution of Ψthen: s2=P2(s1),s 3=P3(s2), ..., sk=Pk(s(k−1)) •Symmetries with respect to a hyperplane with all variables of the SNCSP 1. One possible transformation Ticould be Ti≡αi(X)=−X 2. The regions could be Ω1 i≡x1+... +xn≥0 Ω2 i≡x1+... +xn≤0 3. The symmetric solutions have the same absolute values than solutions obtained in solving the SNCSP but the sign of these values must be changed. •Symmetries with respect to a hyperplane with a subset of variables of the SNCSP Given a subset X⊂Xwhose variables are {x1, ..., xm} 1. The transformation in this case could be Ti≡αi(X)=−X 2. The regions could be Ω1 i≡x1+x2+... +xm≥0andΩ2 i≡x1+x2+ ... +xm≤0. 3. The symmetric solutions of the SNCSP are obtained changing the sign of the following variables {x1, .., xm}in the solutions of the SNCSP. The modeler must check if the hyperplane x1+x2+... +xm=0inIRmis a symmetry hyperplane for all the surfaces that represent the SNCSP. •Translations These transformations are convenient in SNCSPs with trigonometric or periodic functions. 1. The transformation in this case is Ti≡αi(x)=x+τwhere τis a real number. 2. The regions are Ω1 i≡0≤x≤τ,Ω2 i≡k≤x≤2∗τ, ... The number of regions is determined by the domain of the variable x. 3. The symmetric solutions are obtained from the original SNCSP such that if s1is a solution then s2=s1+τ,s3=s2+τ, ... Therefore, the symmetrical analysis must determine from the previous NSL which type of symmetries are most convenient in a particular SNCSP. Modeler must also analyze the pruning of the search space resulted from the addition of symmetry-breaking constraints and the complexity of the treatment of these symmetry-breaking constraints. The efficiency of the numeric constraint solver must be improved in any case. The modelling of symmetrical NCSPs is oriented to a search process of solutions. A broad variety of approaches have been focused to solve NCSPs, essentially, exhaustive or/and local search techniques. Our work considers exclusively the exhaustive approach. Modeler must determine a modelling schema of SNCSPs that considers the symmetries before the search begins. The key idea is to obtain from a SNCSP an equivalent NCSP by the addition of symmetry-breaking constraints and/or the update domains. This idea can be represented as SNCSP(X,D,C,G)SymmetryAnalysis −→ NCSP(X,D,C,G,T) The initial Symmetrical NCSP, denoted as Ψ, is transformed by means of a previous symmetry analysis into a new NCSP where C⊂Cand Tare the set of transformations identified in the symmetry analysis. The conversion is shown in the following expression: Ψ≡{X,D,C ∧Ω1 T1∧Ω1 T2... ∧Ω1 Tk,G} This modeling methodology proposes that the modeler must perform the symmetry analysis according to the particular syntax of a symmetrical NCSP and NSL. It allows the identification of the symmetry-breaking constraints that participate in the modelling schema of this problem. The transformations T,which allows the subsequent calculation of the symmetrical solutions are obtained from NSL. The specification of a SNCSP must consider the symmetries belonging to the NSL. Illustrative examples, that we presented in the section 2 of this article, have some symmetries. Table 2 shows the symmetries that we propose in the different example models. Table 2. Symmetry-breaking constraints of the example models Problem Symmetry-breaking constraints Geometrical x≤y,x +y≤0 Heat-exchanger DTH +KH +FH +DTC +KC +FC +DT1+DT2≥0 Resistors R1≥R2,R 5≥R6,R 7+R8≥R9+R10,R 7≥R8,R 9≥R10 These previous schemas must be solved by means of the adequate algorithm. If the goal is to search for all solutions, then we will apply the corresponding transformations to obtain the symmetric solutions. 5 Experimental Results We have used the previous examples in the experimentation with some extensions. The heat-exchanger example considers one and two heat exchangers in series. The resistors example considers two configurations with ten and thirteen resistors respectively. The results are a mean value considering different variable domains and goals. All the experiments have been performed on the same machine. The program with schema modelling has been run five times on each problem instance, and the results displayed are an average of these five runs. The application to the different proposed problems is shown in Table 3. These results show solutions calculation without considering the CPU computing time of obtaining symmetry-breaking constraints and symmetrical solutions. In the underconstrained problem (heat-exchanger), the computational time is the same in both cases. It indicates that the reduction of the search space is not compensated with a reduction of the computational time. In the other problems, the