About The Solution Of Combinatorical Problems With Problem Solving Methods

Introduction

In the field of problem solving informa­ tion has been gathered about efficient search techniques and about kinds of re­ presentation of problems (1). We have only found few cases of application of these problem solving methods in com­ puter-aided design (2,3,4). Fields of application of these results are mainly the organization of search processes for robots and for question answering systems.

This paper deals with the rationali­ zation of design processes by means of problem solving methods. We formulate general features of the class of combi­ natorical problems, which we found in various phases of design processes. One example of this class is placing the components of an electronic circuit onto printed circuit boards or substrates so as to minimize the number of connections between boards. For the solution of these problems we applicate methods of artificial intelligence. The algorithms, which we got as a result of our investi­ gations, are described. Initial trials of application of these algorithms indi­ cate that they have significant power for effectively solving the described problems.

Problem Formulation

In a paper (5) we have shown that com­ binatorical problems arise in electrical and mechanical engineering. The effec­ tive solution of these problems is one way in rationalizing the design process. The main properties of these problems

Academy of Sciences of the GDR Central Institute of Cybernetics and Information Processing, Berlin, �O~

are the following:

1. The elements x of the set X of poten­ tial solution objects are composed of elements a,b, ·· of sets A,B, ··· An element x could be a subset of A, a subset of A~B, a partition of A, and so on.
2. The elements x of the set X of admis­ sible solution objects are zcharac­ terized by a set p· of predicate Pq(x). With Pq(x) we describe the properties determining the admissibility of elements x.
3. The elements x of the set Xe of optimal solution objects are described by means of a set P of predicats with P · P · u ( P e ( x )) · P e ( x ) is formula ted

on the basis of the cost g(x)a

In particular tasks specifications of these points are given. Choosing the state-space approach of problem solving the set of states of the state-space is the set X of possible solution objects and the set of goal states X is charac­ terized by P- or P. For chan~ging state x into state x' we must define operators o. The problem is to generate states xEXg from states XEX'Xg by means of the operators o of a set o. To illustra­ te these ideas we give some examples for such combinatorical problems.

Decompos~tion problems

Decomposition problems arise in the field of electrical circuit design, in the field of organization of work, and in system analysis. The solution object x of a decomposition problem is a parti­ tion of a set A in n subsets A 1 · We set for decomposition problems x · {A 1 , ··· , A ). A relation F over A is defined tRrough these sublets A 1 · Relation Fx holds between the elements a 1 and aj of set A if these elements are in the same

subset A 1 ·

For the layouts of electrical circuit design the following decomposition pro­ blem with restrictions must be solved:

Given: A= (a 1 , ·· ,ak) a set of elements of the electrical circuit which is to be decomposed ; c(i,j) a coefficient equal to thb number of C'Jfl ·la-:.tions bet­ ween the elements ai and aj with c(i,i) = o; K · (n,k 1 , ·· ,kn) a set of natural numbers characterizing a partition x through the number n of the subsets A 1 in x and the size k ot the subset A 1 for eAch l;

• g(x) the cost for a partition is the sum of the number of connections c(i,j) of all pairs (ai,aj) with ai and aj in different sub­ sets.

Find: a partition x of A in n subsets A 1 with size of A 1 equal to k 1 for each 1, so that the cost g(x) is minimal.

So the set X for this problem is the set of all possible partitions of A, the set Xz is the set of all partitions with the size of A 1 equal to k 1 for each 1. x 8 is the subset of partitions x e X with minimal cost g(x). z

We investigated solution processes based on three sets Oi (i·1,2,3) of operators. An operator o(i,l;j,m) of the set 0 interchanges the element ai of the 1 sub­ set A 1 and the element a 3 of the subset Am (see figure 1). For a partition x the number of operators in the set o 1 is

An operator o(i,n;m) of the set o 2 joins together an element ai of the subset An and the subset Am (see figure 1). For a partition x the number of operators in set o 2 is equal to kn multiplied by (n-1). An operator o(N,n;m) of the set 0 3 joins together a subset N of An and subset Am (see figure 1). An operator of o 2 is an operator o 1: 0 3 with size of N equal to 1. For a partition x the num­ ber of operators in set o 3 is equal to the number of possible subsets N in An multiplied by (n-1).

~unction of ai~ with Am

Junction of N sA with A

Fig. 1: Examples for the operator sets

A decomposition problem without restric­ tions is of importance for finding the constituents of systems or for a decom­ position of task graphs. In reference to the first problem we give only the dif­ ferences: The coefficient c(i,j) charac­ terizes the binding strength between the elements a . and a · The set K is not gi­ ven. We mu~t findla partition x so th~t elements from the sar.le subset A have a great binding strength, but ele~ments of different subsets have a low binding strength. On the basis of these goal we defined the cost g(x) for a partition x ( 9) :

Ii(A 1 ) is the mean value of the binding strengths c(i,j) between the element aie A 1 and all other elements aj€ A 1 , Ei(A 1 ,Am) this one between the element ai E A 1 and all elements aj E Am. v'le have spacial definitions for cases with size of subset Am equal to 0 and with size of subset A equal to 1. We must find a partitio~ with maximal g(x). To solve this problem we investigated solution processes on the basis of sets o 4 and o 5 of operators. An operator o(i,l;m) of set 0 4 units the element ai of the subset A 1 and the subset Am. This is analogous to operator o E 0 2 · For a partition x there are k(n-1) operators of this set. An ope­ rator o(l,m) of the set 0 5 joins together the subsets A 1 and Am· For a partition x we have o,5(n-l)n operators of this set.

tielection Problems

For generating optimal variants reali­ zing a desired technics~ function the following selection problem must be solved:

Given: (A 1 , ·· An) a partition of a set A

of constructional ele­ ments ai:

a set B of functional elements, whereby each ai of the subset A 1 is the realization of the functional element b 1 :

• S ~ B · B a relation between ele­ ments of the set B. s holds between the ele­ ments b 1 and bm if these elements must be coupled in order to the accomplishment of the system function;
• Q ~A" A a relation between ele­ ments of the set A. The relation Q holds between the elements ai and aj if they could be coupled;
• g(~) the cost for an object x is the sum of the costs of each element ai in x.
• Finda an object x · (ai , ·· ,ai ) with 1 n ai E Aland Pe(x) · 'True·, where1 by relation Q must hold between a . and ai if relation s holds l.l m

between the elements b 1 and bm. So we have X · A 1 x ····· xAn for this selection problem. Possibilities for the effective solution of this selection problem are described in (5).

Algorithms

The power of algorithms for the solution of such problems is determined by the time for generating objects x and by the cost g(x). In the field of artificial intelligence search techniques are deve­ loped for generating goai states in the state-space approach of problem solving. We auapted and developed these techni­ ques to get efficient a!gorithms. The algorithms do not generate optimal solu­ tion objects with probability 1. The ob­ jects x are the states in the problem space, the operators of the sets 0 (i:a1, ·· ,5) realize the t ransitionsibet­ ween states. We are going to describe briefly the genera l solution algorithm for the decomposition problems. The efficien~y of the search process is determined by the following steps (6):

• -Choice of a start object x 0 ·
• Selection of a ~et of operators.
• Selection of a subset of applicable operators from the chosen set.
• Selection of an operator from this subset. The application of this ope­ rator produces the next object. We repeat these steps until a brea~-off point is raacheci.
• Determination of a brea k-off point.

The selection process is based on heuri­ stic rules for operators ozx-.x·. A rule is defined by means of the weight ~ for an operator o. We got these weights as a result of the analysis of the costs g(x) and g(x'). So these weights are depen­ dent from the object x and/or from the object x·. Through the kind of computa­ tion of these weights we are sure that they are only computed for applicable operators.

For the decomposition problem with re­ strictions we determined the following weights a

1. Weight L1 1 (i,n :m) for the selection of an operator o(i,n~m) is the sum of the numbers c(i,j} of connections from element aie An to all elements ajeAm·

1. Weight!J 2 (i,n;m) for the selection of an operator o(i,n;m) is the difference between the sum of the numbers c(i,j} of connections from element aiE Anto all elements ajEAm and the sum of the numbers c(i,j} of connections from the element a 1 EAn to all other ele­ ments alAn:

1. Weight..:1 3 (i,l;j,m} for the selection of an operator o(i,l;j,m} is the sum of weightsL1 2 (i,l;m) andLI 2 (j,m;l) subtracted by 2c(i,j}l

1. Weight L1 4 (N,n:m) for the selection of an operator o(N,n;m) is the difference between the sum of the coefficients c(i,j) of all pairs (ai,aj) in the subset Am UN and the sum of coeffi­ cients c(i,j) of all pairs (ai,aj) in the subset Am:

In all ca~es the best operator of the set of applicable operators is this one with the maximal weight. Distinct vari­ ants of search algorithms based on these operators ~nd weights ure implemented. On the basis of the efficiency of the various algorithms a variant with the following characteristics is firstly choosed:

• -~elect the first element a. of the sub­ set A from An = A. There ~are several possibilities for this selection which here we do not discuss.
• Compose the set A 1 with operators from the set o 2 · The first o,5k 1 elements of A 1 we select from An on the basis of opera tors choosed oy weights Lf 1 {i,n:m). The other o,5k 1 elements of A 1 we select on the basis of operators choosed by weights.1 2 (i,n:m). So with k 1 steps we have generated the subset A1.
• After this the subsets ~, ·· ,An-l are generated element by element in an analogous way. So after (k-kn) steps an admissible object x e X is generated. z
• The object x generated by the appli­ cation of operators from the set 0 2 is the start object for the next phase: We interchange pairs of elements by means of operators from the set o 1 · We select the operators on the basis of weights ~ 3 (i,l;j,m). The process stops if after the application of an opera­ tor from the set o 1 onto object x the generated object x' has cost g(x') not less than the cost g(x) of object x. We found this last .phase also in (7).

With the kind of computation of the weights it is provided that only appli­ cable operators are selected. With the help of this algorithm we found out that the cost g{x) is hardly to increase by the application of operators from the set o 1 after the generation of the first aduissible object by means of o e o 2 ·

A better solution object at the expense of the search time is attainable through the application of operators o(N,n;m) instead of operators o(i,n:m). With these operators we select subsets N~ An with a predetermined number V' of elemen~ts ond join together N and A . In our al­ gorithm we consider not a!l possible V' -subsets N of An. Instead we compute subsets N element by element by means of operators from the set o 2 :

We generate all possible sequences of length v with weights ..1 1 (i,n ;m) and ~ 2 (1,n;m) as elements. On the basis of each of these sequences we determine a sequence of operators o(i,n;m). The application of each operator sequence results in a single -.r-1>ubset N. Each of these subsets generated by on operator sequence is a subset N of an operator o(N,n;m). The weights J 4 (N,n;m) are then determined and the operator with the maximal weight is selected.

In an analogous wey the algorithm for the solution of the decomposition problem without restrictions is generated on the basis of operatoro of the sets 0 4 and 0 5 · For the selection of an operator from the set 0 4 we choose a;:; weightJ 5 (i,l;m) the component hi(A 1 ) of the cost g(x). We select the operator with the minimal weight. After reaching the subgoal hi{A 1 )~ 0 for i·1(1)k we applicate operators of the set o 5 · The selection pro­ cess of these operators is controlled by the weight ~ 6 (m,l) 1

A 1 is determined by the element ai in this computation. The operator with the maximal weight is applicated. The search process stops after reaching a threshold value forJ 6 (m,l).

Applications

The presented algorithms are based heavily on experimental evidence, al­ though there are quite plausible reasons for performing the particular operations (5,7). In the following we characterize some applications.

We examined the behaviour of the al­ gorithm for the decomposition problem without restrictions if the matrix of coefficients c(i,j) is a matrix with known clusters. So the a~gorithm always finds in a set A the partition x~ with the following properties if this parti­

tion in A exists: c(i,j) = c 1 for

(ai,a)~ Fxotand c(i,j) = c 2 for (a 1 ,aj)<: E Fx,.with c 1 ~ o,5c 0 > c 2 whereby c 0 is the maximal possible coefficient in the matrix of coefficients. ~ith the start object x =(A 1 =(a 1 ), ··· ,An=(an)) the algorithm stops aiter reaching the parti­ tion xw. This algorithm is applicated for the clustering of experimental data, which a··e the results of an experiment for the identification of inner struc­ tures in human problem solving. Based on such groupings we could give statements about properties of inner structures by means of scaling methods (8). This al­ gorithm helps also the projectants of systems in the analysis of the system structure and their decomposition. An example show this: For decomposing the organizational structure of a production department the flow of information bet­ ween units was determined by experts. This flow is set equal to the binding strength c(i,j). The algorithm generated a partition x with cost g(x) · 1,3. The maximal possible value for g(x) was 5. The analysis of these results show that the coats hi(A 1 ) for each element ai are greater than o. This means, that the flow of information between each ele­ ment ai E A 1 to the subset A 1 is greater than tho flow of information between the element ai E A 1 to each other subset Am. The algorithm for the decomposition pro­ blem without restrictions is also a part of a program for the realization of the structure of a technical system. With this algorithm we determine the con­ stituents of the system structure (5).

We tested the algorithm for the decompo­ sition problem with restrictions on a variety of practical problems. To illu­ strate the power of the algorithm we give some statistical results:

1. Three different sets A of size 72 were partitioned. For each set A we computed with the algorithm four dif­ ferent partitions x characterized by the following sets K: (3,24,24,24), (3,30,24,18), (3,30,30,12) and (3,36,18,18). For ench set K we also generated 10 random partitions over A. The main result is the following: In the mean with our algorithm we gene­ rate partitions with cost g(x) 10 % less than the cost of random parti­ tions. The variability coefficient of the distribution of the random partitions is 3,5 ~.
2. A practical example with set A of size 24 is also computed. We 9enerate partitions with K · (3,10,8,6) and K · (3,9,9,6). For this problem we also generate analogous to point 1 u set of 10 random partitions. In the mean our algorithm 9enerates parti­ tions with cost g(x) 18 % less than the cost of random partitions. The variability coefficient of the di­ stribution of random partitions is 3 x.

Further results of this kind must be computed. ·

This algorithm is also a part of a pro­ gram for the placement of logical ele­ ments on double sided printed circuit boards. On figure 2 the structure of this progra~ is given:

On the basis of placements which we com­ puted with this program the routing of all connections between positions on the board is possible with a routing progra· with 96 - 98 5~.

Conclusions

The results show that the application of problem solving methods is one way in rationalization of design processes. The practical applications are encouraging. In the future we are interested to find estimates of the probability for reach­ ing extremal values of the cost g(x) for such problems. In the past we restricted our investigations on problems with only structural relationships between ele­ ments aE A such as the number of connec­ tions, the flow of information and so on. From the point of view of electrical and mechanical engineering the functional features of the elements a E A can not be neglected in the future. So we hope to go one step in the direction of automa­ tically solving synthesis problems as parts of design processes by ~eans of problem solving methods.

Acknowledgements

The computation of routings w~s carried out by P. Bennewitz by means of the ·pro­ gram constructed by K. Schiller under the leadership of J. Saedler, 'Institut fur Nachrichtentechnik Derlin'.