Solution synthesis is a method used to generate all solutions to a
CSP. That is, all assignments of values to variables that satisfy the
problem's constraints are produced by a solution synthesis algorithm.
Often, this set of solutions can be further judged according to some
separate criteria to obtain the optimal answer. For instance, in a
modified traveling salesperson problem in which all cities must be
visited, but in an order subject to certain constraints,
solution synthesis can generate the list of all possible
answers that meet the constraints, from which the most optimal answer
(presumably the one with the least total mileage) could be picked.
[Freuder, 1978] introduced solution synthesis and [Tsang and
Foster, 1990] refined it. Both of their research will be described
below. We extend the work of Tsang and Foster and combine it with
branch-and-bound techniques, all of which will be described in the
``Hunters and Gatherers in Computational Semantics'' section.
Solution synthesis constructs the set of all possible solutions by
iteratively combining smaller solutions while propagating constraints.
A simplified algorithm which implements
solution synthesis follows:
GENERAL ALGORITHM
1 PROCEDURE SS-1;; initialize SOLUTION SET to set of order-1 solutions
2 SOLUTION-SET <-- nil
3 FOR each variable, V
4 FOR each value, X in the domain of V that meets unary constraint
5 SOLUTION-SET = SOLUTION-SET + (<V,X>)
6 FOR I = 2 to n, where n = number of variables
;;Create all partial solutions of length I
;;At this point, SOLUTION-SET contains all solutions of
;; length I-1
7 SOLUTION-SET <-- SYNTHESIZE(SOLUTION-SET,I)
8 PROCEDURE SYNTHESIZE(SOLUTION-SET,I)
9 SOLUTION-SET-TEMP <-- nil
10 FOR each SOLUTION-A in SOLUTION-SET
11 FOR each SOLUTION-B in SOLUTION-SET
12 IF SOLUTION-A and SOLUTION-B have I distinct variables
b AND all like-variable assignments are the same THEN
13 POSSIBLE-SOLUTION <-- UNION(SOLUTION-A,SOLUTION-B)
14 IF POSSIBLE-SOLUTION meets all I-ARY CONSTRAINTS
b AND NOT-MEMBER(POSSIBLE-SOLUTION,SOLUTION-SET-TEMP)
c AND SYNTHESIZED?(POSSIBLE-SOLUTION,SOLUTION-SET,I) THEN
15 SOLUTION-SET-TEMP <-- SOLUTION-SET-TEMP + POSSIBLE-SOLUTION
16 RETURN SOLUTION-SET-TEMP
17 PROCEDURE SYNTHESIZED?(POSSIBLE-SOLUTION,SOLUTION-SET,I)
;; Make sure all sub-solutions of length I-1 of the new solution
;; are in SOLUTION-SET (which contains all valid solutions of order I-1.)
18 OK <-- true
19 FOR all COMBOs of I-1 <V,X> pairs in POSSIBLE-SOLUTION
20 IF NOT-MEMBER(COMBO,SOLUTION-SET) THEN
21 OK <-- false
22 RETURN OK
Before giving an example, a walkthrough of the algorithm would be
instructive. At the most abstract level, SS-1 creates partial
solution sets of order k by combining solution sets of order
k-1. The initial solution set of order 1 is created in lines 3-5; a
solution is added for each value of each variable. From there,
solution sets of higher order are created using SYNTHESIZE (lines
8-16).
In SYNTHESIZE, solution sets of order I are created. The input
SOLUTION-SET contains all solutions of order I-1. POSSIBLE-SOLUTIONs
are created by combining compatible solutions of order I-1 that differ
only in one variable. For example, a solution of variables (A,B,C)
combined with a solution of variables (A,B,D) would combine to create
a solution of variables (A,B,C,D). ``Compatible'' combinations are
those which have like-variables assigned similarly. For example,
(<A,1>,<B,2>) can combine with (<A,1>,<C,3>) to create a
POSSIBLE-SOLUTION (<A,1>,<B,2>,<C,3>), but
(<A,1>,<B,2>) cannot combine with (<A,4>,<C,3>) because the
assignments <A,1> and <A,4> are not compatible.
Each POSSIBLE-SOLUTION must meet three tests (lines 14a-c). First,
all I-ary constraints must be met. For instance, for an
order 2 POSSIBLE-SOLUTION involving variables A and B, the constraints
and 
must be met. Order 3 possible solutions must
meet 3-ary constraints, and so on. In computational semantics, there are only binary
constraints, so order 3 solutions and above will always pass this
test. Second, line 14b simply ensures that duplicate solutions are not added.
For instance, when adding variable C onto a partial solution (A,B),
solutions for (A,B,C) are obtained. Later, when adding on variable B
to (A,C), the same solutions would be obtained. Line 14b prevents
this. Line 14c ensures that solutions of length I meet the constraints
already calculated for solutions of length I-1. This is the
synthesizing step. A simple example will illustrate. In order to
allow a POSSIBLE-SOLUTION = (<A,0>,<B,1>,<C,2>), a solution of order
3, the following order-2 solutions must exist:
{
}
In other words, an order-N solution cannot have any sub-solutions of
order N-1 that were not already identified. Because of the way order
I-1 solutions are combined, most of these sub-solutions will be
present. For instance, in the
example above a solution of variables (A,B) was combined with a
solution of variables (B,C) to create a solution of variables (A,B,C).
Thus, we do not need to check the (A,B) or (B,C) sub-solutions.
However, the sub-solution involving variables (A,C) was synthesized
and must be checked. If, for this example, an order I-1 solution
(<A,0>,<C,2>) does not exist, then this combination of values is
unacceptable. The SYNTHESIZED? procedure in lines 17-22 performs this
check. Again, this step ensures that any new order-I solution only
contains order-(I-1) sub-solutions that had already been deemed
legitimate.
In order to start moving this discussion towards natural language semantics, the solution synthesis algorithms will be exemplified using a simple computational semantic problem. Consider the following sentence:
(1) IBM acquired Jacob-Smith for ten-million-dollars.
For simplicity, assume that Jacob-Smith and ten-million-dollars are
phrasal entries in the lexicon. Also assume that we have an
ontology, or model of the world, that maps each of these
words into the concepts as shown in Figure 7.
IBM (referred to below as I) maps into a single concept, ORG.
acquired (referred to as A) maps into two possible concepts.
The first, TAKE-OVER, constrains IBM to be an ORG
and Jacob-Smith to be an ORG. Refer to Figure
7 for the rest of the possible assignments and
constraints.
Figure 7: Concept assignments for SS example.
The SS-1 algorithm would proceed as follows. First, it would
initialize SOLUTION-SET to the set of all order-1 nodes in lines 2-5.
For convenience, we will present SOLUTION-SET as a group of subsets
arranged according to the variables involved:
= {
}
= {
}
= {
}
= {
}
= {
}
For example, 
has two possible solutions, the first of which
assigns the concept TAKE-OVER (T-O) to A ( aquired).
If necessary, unary constraints would be applied in line 3. In computational semantics, unary constraints correspond to selecting the appropriate word-senses from the lexicon based on the word used and the surrounding syntax. In this case, those constraints were applied before beginning the algorithm.
Before line 6 is executed, then:
SOLUTION-SET = APPEND(
)
Next, all higher order nodes, including the final solution, are created in steps 6 and 7. First, order-2 nodes are constructed. When SYNTHESIZE is called with I=2, SOLUTION-SET contains all the solutions of order-1. In SYNTHESIZE, these order-1 solutions are combined into order-2 solutions. For instance, if, in lines 10 and 11:
SOLUTION-A = 
SOLUTION-B = 
Then, together, A and B have two distinct variables (I and A), checked in line 12, there are no like-variables, so line 12 is true, so in line 13:
POSSIBLE-SOLUTION = 
Line 14a is important only when I=2, as in this case, because computational semantic
problems only have binary constraints. Two binary constraints must be
examined, 
and 
. As shown in Figure 7, I does not
constraint A for any value of A, but <A,T-O> constrains I to be of
type ORG. Since <I,ORG> obviously meets this constraint, line 14a is
true. No other solutions have been added for order-2 solutions, so
line 14b is also true. Finally, since the only two sub-solutions of
POSSIBLE-SOLUTION of order 1, 
and 
, came
directly from SOLUTION-SET, SYNTHESIZED? will obviously return true.
In fact, SYNTHESIZED? will always be true for POSSIBLE-SOLUTIONS of
order-2. It only becomes relevant for order-3 and higher nodes, when
previously non-existent lower order sub-solutions are possible.
An example of when the binary constraint in line 14a rejects a POSSIBLE-SOLUTION occurs for
SOLUTION-A = 
SOLUTION-B = 
which yields
POSSIBLE-SOLUTION = 
The binary constraint, 
, specifies that for the assignment
<A,T-O>, J must be an ORG. However, the assignment <J,HUM> does
not meet this constraint, so this POSSIBLE-SOLUTION is rejected.
A complete listing of order-2 solutions for this example is shown below, with solutions rejected by binary constraints identified:
= {(ORG,T-O),(ORG,OBT)}
= {(ORG,HUM),(ORG,ORG)}
= {(ORG,COST),(ORG,BEN),(ORG,PUR),(ORG,DUR)}
= {(ORG,MON)}
= {(T-O,ORG),(OBT,ORG)} ;; eliminate (T-O,HUM),(OBT,HUM)
= {¯(T-O,COST),(T-O,BEN),(T-O,PUR),(T-O,DUR),
(OBT,COST),(OBT,BEN),(OBT,PUR),(OBT,DUR)}
= {(T-O,MON),(OBT,MON)}
= {¯(HUM,COST),(HUM,BEN),(HUM,PUR),(HUM,DUR),
(ORG,COST),(ORG,BEN),(ORG,PUR),(ORG,DUR)}
= {(HUM,MON),(ORG,MON)}
= {(COST,MON)} ;; eliminate (BEN,MON),(PUR,MON),(DUR,MON)
Order-3 nodes are then synthesized by combining order-2 solutions. Note that from this point on, no reference needs to be made to constraints, because all the binary constraints information is implicit in the order-2 solution set. An example of synthesisizing an order-3 solution follows:
SOLUTION-A (from 
) = (ORG,T-O)
SOLUTION-B (from 
) = (T-O,ORG)
Together, A and B have three distinct variables (I, A and J), and the only like-variable, A, has the same value assignment in both, so:
POSSIBLE-SOLUTION = (<I,ORG>,<A,T-O>,<J,ORG>)
Because there are no n-ary constraints for n > 2, line 14a will be true from here on. It will also be assumed, starting now, that line 14b will prevent duplicate solutions from being added. Thus, the SYNTHESIZED? procedure called in line 14c is the only part left needing comment. In this case, the following sub-solutions of order-2 taken from POSSIBLE-SOLUTION are:
(<I,ORG>,<A,T-O>)
(<A,T-O>,<J,ORG>)
(<I,ORG>,<J,ORG>)
The first two come directly from SOLUTION-A and B. The third,
however, was a result of the synthesis; therefore, it must be checked
to see if it is a valid order-2 solution. A quick look at the list of
order-2 solutions shows that this solution is present in 
.
Therefore, POSSIBLE-SOLUTION is a valid synthesis.
An example of a POSSIBLE-SOLUTION that does not meet the SYNTHESIZED? criterion occurs for:
SOLUTION-A (from 
) = (HUM,BEN)
SOLUTION-B (from 
) = (HUM,MON)
This gives:
POSSIBLE-SOLUTION = (<J,HUM>,<F,BEN>,<T,MON>)
Three sub-solutions of order-2 can be extracted from POSSIBLE-SOLUTION:
(<J,HUM>,<F,BEN>)
(<J,HUM>,<T,MON>)
(<F,BEN>,<T,MON>)
Again, the first two come directly from SOLUTION-A and B. The third, however, was synthesized. This time, though, the synthesized sub-solution cannot be found in the list of order-2 solutions, thus it cannot be allowed.
A complete list of order-3 solutions follows:
= {(ORG,T-O,ORG),(ORG,OBT,ORG)}
= {¯(ORG,T-O,COST),(ORG,T-O,BEN),(ORG,T-O,PUR),(ORG,T-O,DUR),
(ORG,OBT,COST),(ORG,OBT,BEN),(ORG,OBT,PUR),(ORG,OBT,DUR)}
= {(ORG,T-O,MON),(ORG,OBT,MON)}
= {¯(ORG,HUM,COST),(ORG,HUM,BEN),(ORG,HUM,PUR),(ORG,HUM,DUR),
(ORG,ORG,COST),(ORG,ORG,BEN),(ORG,ORG,PUR),(ORG,ORG,DUR)}
= {(ORG,HUM,MON),(ORG,ORG,MON)}
= {(ORG,COST,MON)}
= {¯(T-O,ORG,COST),(T-O,ORG,BEN),(T-O,ORG,PUR),(T-O,ORG,DUR),
(OBT,ORG,COST),(OBT,ORG,BEN),(OBT,ORG,PUR),(OBT,ORG,DUR)}
= {(T-O,ORG,MON),(OBT,ORG,MON)}
= {(T-O,COST,MON),(OBT,COST,MON)}
= {(HUM,COST,MON),(ORG,COST,MON)}
It is interesting to note that the solution sets 
, 
and 
all carry along values for F that, with a little bit of
thought, could be eliminated. In 
, 
and 
,
inconsistent values for J are also kept. Freuder's algorithm, as well
as Tsang's and our own, eliminate this.
Order-4 solutions are formed similarly:
= {¯(ORG,T-O,ORG,COST),(ORG,T-O,ORG,BEN),(ORG,T-O,ORG,PUR),(ORG,T-O,ORG,DUR),
(ORG,OBT,ORG,COST),(ORG,OBT,ORG,BEN),(ORG,OBT,ORG,PUR),(ORG,OBT,ORG,DUR)}
= {(ORG,T-O,ORG,MON),(ORG,OBT,ORG,MON)}
= {(ORG,T-O,COST,MON),(ORG,OBT,COST,MON)}
= {(ORG,HUM,COST,MON),(ORG,ORG,COST,MON)}
= {(T-O,ORG,COST,MON),(OBT,ORG,COST,MON)}
Finally, the order-5 solutions are synthesized:
= {(ORG,T-O,ORG,COST,MON),(ORG,OBT,ORG,COST,MON)}
At each stage, higher order solutions are created by combining lower order solutions, while ensuring no unacceptable lower-order sub-solutions are introduced. The order-n solution set contains all of the valid answers for the problem.
Although various improvements to this algorithm will be
offered, all solution
synthesis algorithms will have the same worst-case time complexity.
Assume a CSP for which all combinations of values for every variable
meet all constraints. Furthermore, assume each variable has a
values in its domain. For such a CSP, there exist 
solutions. It is easy to see, therefore, that line 15 must be
executed 
times when the SYNTHESIZE procedure is called the
last, 
time. It is the nature of CSPs that worst-case
(algorithmic) time behavior is always exponential because the number
of possible solutions is always, theoretically, exponential.
However, ``worst-case'' can be redefined
non-algorithmically, and with respect to a certain class of problems,
to mean the ``typical'' worst class complexity as measured
experimentally. Such measurements will be described below.
FREUDER'S ALGORITHM
Freuder's algorithm [Freuder, 1978] eliminates some of the waste present in SS-1. Instead of only propagating constraints upward from lower-order nodes to higher order nodes, Freuder also propagates constraints downward, from higher order nodes to lower order nodes.
An example would clarify best. Suppose the following order-1 solutions were found for a simple CSP:
= {(1),(2)}
= {(3),(4)}
= {(5),(6)}
= {(7)}
Assume binary constraints were then used to acquire the following order-2 solutions:
= {(1,3),(2,3)}
= {(1,5),(1,6),(2,5)}
= {(1,7),(2,7)}
= {(3,5),(4,5),(4,6)}
= {(3,7),(4,7)}
= {(5,7),(6,7)}
At this point, it can be deduced that an assignment <B,4> will never be compatible with any assignment for A. SS-1, however, blindly constructs the order-3 solutions:
= {(1,3,5),(1,3,6),(2,3,5)}
= {(1,3,7),(2,3,7)}
= {(3,5,7),(4,5,7),(4,6,7)}
Clearly, (4,5,7) and (4,6,7) in 
are impossible. SS-1
eventually gets the correct answer because it cannot construct any
order-4 solutions with the assignment <B,4>, but it wastes much
effort in doing it.
Freuder suggests allowing downward propagation of constraints. For
instance, once it can be determined that a solution set of order I
contains no instances of a particular sub-solution of order I - 1,
that sub-solution can be eliminated from the order I - 1 solutions.
Above, since the sub-solution (<B,4>) does not occur in 
,
(<B,4>) can be removed from the order-1 solutions:
= {(3)} ;; removed (4)
Whenever a solution is removed, all higher order solutions involving that solution must also be removed (upward propagation). In addition, whenever a solution is removed, downward propagation can occur again. In the example above, solutions of order-2 involving <B,4> must be removed, giving:
= {(3,5)} ;; removed (4,5) and (4,6)
= {(3,7)} ;; removed (4,6)
Before creating new order-3 solutions, downward propagation can be
repeated, since the assignment <C,6> no longer is compatible with
any assignment of B. Therefore, removing (6) from 
yields:
= {(5)}
which can be re-propagated upward to form the level-2 solutions:
= {(1,5),(2,5)} ;; removed (1,6)
= {(5,7)} ;; removed (6,7)
The resulting complete list of order-2 solutions is:
= {(1,3),(2,3)}
= {(1,5),(2,5)}
= {(1,7),(2,7)}
= {(3,5)}
= {(3,7)}
= {(5,7)}
Creating order-3 solutions from this yields the smaller set:
= {(1,3,5),(2,3,5)}
= {(1,3,7),(2,3,7)}
= {(3,5,7)}
from which the order-4 solutions can be calculated easily:
= {(1,3,5,7),(2,3,5,7)}
SS-1 needs to be modified to include this downward propagation. One major change is that SOLUTION-SETs for all the previous levels need to be stored. Also, after a solution set is formed, it needs to be analyzed to see if it excludes any sub-solutions of the next lower order. If it does, these sub-solutions will need to be removed from the lower order SOLUTION-SET. Whenever a solution is removed from a SOLUTION-SET, higher order solutions utilizing it must also be removed, and the SOLUTION-SET it was removed from needs to be re-checked for downward propagation possibilities. SS-FREUDER implements these changes:
1 PROCEDURE SS-FREUDER2 INITIALIZE SOLUTION-SET, SOLUTION-VC and SOLUTION-VC-1 arrays
;; initialize SOLUTION SET[1] to set of order-1 solutions
3 FOR each variable, V
4 FOR each value, X in the domain of V that meets unary constraint
5 SOLUTION-SET[1] = SOLUTION-SET[1] + (<V,X>)
6 FOR I = 2 to n, where n = number of variables
;;Create all partial solutions of length I
;;At this point, SOLUTION-SET[I-1] contains all solutions of
;; length I-1
7 SOLUTION-SET[I] <-- SYNTHESIZE(SOLUTION-SET[I-1],I)
;; set up data arrays to be used in DOWNWARD-PROPAGATE
7b FOR each SOLUTION in SOLUTION-SET[I]
7c VAR-COMBO <-- the combination of variables used in SOLUTION
7d SOLUTION-VC[I,VAR-COMBO] <--
SOLUTION-VC[I,VAR-COMBO] + SOLUTION
7e FOR each combination, VAR-COMBO-I-1, of I-1 variables in VAR-COMBO
7f PARTIAL-SOLUTION <-- the sub-solution of SOLUTION
involving the variables in VAR-COMBO-I-1
7g SO LUTION-VC-1[I,VAR-COMBO-I-1] =
SOLUTION-VC-1[I,VAR-COMBO-I-1] + PARTIAL-SOLUTION
7h DOWNWARD-PROPAGATE(SOLUTION-SET,SOLUTION-VC,SOLUTION-VC-1,I)
8 PROCEDURE SYNTHESIZE(SOLUTION-SET-I-1,I)
9 SOLUTION-SET-TEMP <-- nil
10 FOR each SOLUTION-A in SOLUTION-SET-I-1
11 FOR each SOLUTION-B in SOLUTION-SET-I-1
12 IF SOLUTION-A and SOLUTION-B have I distinct variables
b AND all like-variable assignments are the same THEN
13 POSSIBLE-SOLUTION <-- UNION(SOLUTION-A,SOLUTION-B)
14 IF POSSIBLE-SOLUTION meets all I-ARY CONSTRAINTS
b AND NOT-MEMBER(POSSIBLE-SOLUTION,SOLUTION-SET-TEMP)
c AND SYNTHESIZED?(POSSIBLE-SOLUTION,SOLUTION-SET-I-1,I) THEN
15 SOLUTION-SET-TEMP <--
SOLUTION-SET-TEMP + POSSIBLE-SOLUTION
16 RETURN SOLUTION-SET-TEMP
17 PROCEDURE SYNTHESIZED?(POSSIBLE-SOLUTION,SOLUTION-SET-I-1,I)
;; Make sure all sub-solutions of length I-1 of the new solution
;; are in SOLUTION-SET-I-1 (which contains all valid solutions of order I-1.)
18 OK <-- true
19 FOR all COMBOs of I-1 <V,X> pairs in POSSIBLE-SOLUTION
20 IF NOT-MEMBER(COMBO,SOLUTION-SET-I-1) THEN
21 OK <-- false
22 RETURN OK
23 PROCEDURE DOWNWARD-PROPAGATE(SOLUTION-SET,SOLUTION-VC,
SOLUTION-VC-1,I)
;; SOLUTION-SET,SOLUTION-VC and SOLUTION-VC-1 are arrays, assume
;; we can change values in them
24 FOR each X entry in SOLUTION-VC-1[I,X]
;; for a specific combination of I-1 variables, X, first get
;; all of the sub-solutions of order-i solutions that use
;; that combination
25 SUBSOLUTIONS <-- SOLUTION-VC-1[I,X]
;; now get all of the order I-1 solutions that use that combination
26 VC-1-SOLUTIONS <-- SOLUTION-VC[I-1,X]
;; now remove any VC-1-SOLUTIONS
;; that are not used as subsolutions in order-I solutions.
27 FOR each VC-1-SOLUTION in VC-1-SOLUTIONS
28 IF NOT-MEMBER(VC-1-SOLUTION,SUBSOLUTIONS) THEN
29a REMOVE VC-1-SOLUTION from SOLUTION-SET[I-1]
29b REMOVE VC-1-SOLUTION from SOLUTION-VC[I-1,X]
29c REMOVE subsolutions of VC-1-SOLUTION from
SOLUTION-VC-1[I-1] if necessary
30 UPWARD-PROPAGATE(SOLUTION-SET,I,SOLUTION)
31 DOWNWARD-PROPAGATE(SOLUTION-SET,I-1)
32 PROCEDURE UPWARD-PROPAGATE(SOLUTION-SET,I,SOLUTION)
33 FOR each SOLUTION-I in SOLUTION-SET[I]
34 IF SOLUTION is a sub-solution of SOLUTION-I THEN
35a REMOVE SOLUTION-I from SOLUTION-SET[I]
35b VAR-COMBO <-- the combination of variables used in SOLUTION-I
35c REMOVE SOLUTION-I from SOLUTION-VC[I,VAR-COMBO]
35d REMOVE subsolutions of SOLUTION-I from SOLUTION-VC-1[I] if necessary
36 UPWARD-PROPAGATE(SOLUTION-SET,I+1,SOLUTION-I)
36 DOWNWARD-PROPAGATE(SOLUTION-SET,I)
SS-FREUDER makes use of two arrays to store solutions for combinations of variables at each level. Besides this storage, performed in lines 7b-7g, the only major change to the basic algorithm is the addition of line 7h, where DOWNWARD-PROPAGATE is called. DOWNWARD-PROPAGATE determines if any sub-solutions of order I-1 need to be excluded on the basis of the order I solutions. Whenever a solution is removed (lines 29 and 35), two things happen. First, UPWARD-PROPAGATE is called to remove higher-level solutions which are based on it. Second, DOWNWARD-PROPAGATE is called to start the downward propagation process again, because the removal of a solution at level I might enable downward propagation again.
SS-FREUDER is inefficient as written. When a SOLUTION is removed, only those solutions which depend on it need to be rechecked, similar to the work in AC-4. However, it is not the intent here to optimize SS-FREUDER. Freuder himself admits that the algorithm is intractable. SS-FREUDER is simply a step on the way to TSANG's algorithm, and, ultimately, to our own.
To conclude the description of SS-FREUDER, the computational semantic example presented above will be re-worked. The order-1 solutions would be calculated the same as before, and are repeated here for convenience:
= {
}
= {
}
= {
}
= {
}
= {
}
The order-2 nodes are then calculated:
= {(ORG,T-O),(ORG,OBT)}
= {(ORG,HUM),(ORG,ORG)}
= {(ORG,COST),(ORG,BEN),(ORG,PUR),(ORG,DUR)}
= {(ORG,MON)}
= {(T-O,ORG),(OBT,ORG)}
= {¯(T-O,COST),(T-O,BEN),(T-O,PUR),(T-O,DUR),
(OBT,COST),(OBT,BEN),(OBT,PUR),(OBT,DUR)}
= {(T-O,MON),(OBT,MON)}
= {¯(HUM,COST),(HUM,BEN),(HUM,PUR),(HUM,DUR),
(ORG,COST),(ORG,BEN),(ORG,PUR),(ORG,DUR)}
= {(HUM,MON),(ORG,MON)}
= {(COST,MON)}
In the DOWNWARD-PROPAGATE step, it will be determined that all assignments <F,BEN>,<F,PUR> and <F,DUR> can never be combined with any values for T, and that the assignment <J,HUM> is incompatible with any value of A. These facts will be propagated downward to the order-1 constraints:
= {
}
= {
}
= {
} ;; removed 
= {
} ;; removed 
= {
}
The removals can then be upward-propagated to order-2 nodes again:
= {(ORG,T-O),(ORG,OBT)}
= {(ORG,ORG)} ;; removed (ORG,HUM)
= {(ORG,COST)} ;; removed (ORG,BEN),(ORG,PUR),(ORG,DUR)
= {(ORG,MON)}
= {(T-O,ORG),(OBT,ORG)}
= {¯(T-O,COST),(OBT,COST)}
;; removed(T-O,BEN),(T-O,PUR),(T-O,DUR),(OBT,BEN),(OBT,PUR),(OBT,DUR)
= {(T-O,MON),(OBT,MON)}
= {(ORG,COST)} ;; removed (HUM,COST),(HUM,BEN),(HUM,PUR),(HUM,DUR),
(ORG,BEN),(ORG,PUR),(ORG,DUR)}
= {(ORG,MON)} ;; removed (HUM,MON)
= {(COST,MON)}
No further downward propagation is possible, so the order-3 solutions are synthesized:
= {(ORG,T-O,ORG),(ORG,OBT,ORG)}
= {(ORG,T-O,COST),(ORG,OBT,COST)}
= {(ORG,T-O,MON),(ORG,OBT,MON)}
= {(ORG,ORG,COST)}
= {(ORG,ORG,MON)}
= {(ORG,COST,MON)}
= {(T-O,ORG,COST),(OBT,ORG,COST}
= {(T-O,ORG,MON),(OBT,ORG,MON)}
= {(T-O,COST,MON),(OBT,COST,MON)}
= {(ORG,COST,MON)}
From here, order-4 and order-5 solutions are simple:
= {(ORG,T-O,ORG,COST),(ORG,OBT,ORG,COST)}
= {(ORG,T-O,ORG,MON),(ORG,OBT,ORG,MON)}
= {(ORG,T-O,COST,MON),(ORG,OBT,COST,MON)}
= {(ORG,ORG,COST,MON)}
= {(T-O,ORG,COST,MON),(OBT,ORG,COST,MON)}
= {(ORG,T-O,ORG,COST,MON),(ORG,OBT,ORG,COST,MON)}
TSANG'S ALGORITHM
Tsang's algorithms, defined in [Tsang and Foster, 1990], also known as the Essex algorithms, improve upon SS-FREUDER by limiting the number of second-order solutions (and thus limiting the number of higher order solutions as well). SS-TSANG sets up an arbitrarily ordered list of the variables, and then constructs second-order solutions only for variable pairs that are adjacent in that list. Third-order solutions are then synthesized from ``adjacent'' second-order solution sets, etc.. Figure 8 displays the process for the computational semantic example.
Figure 8: SS-TSANG Solution Set Construction.
SS-TSANG is exactly the same as SS-1, except that the number of
order-2 solutions is restricted. This restriction could be easily
added by constructing a list of the variables, then only allowing
order-2 solutions that involve adjacent variables in the list.
Synthesizing higher-order solutions will proceed exactly as in
SS-1.
Because they are so similar, with the changes fairly obvious, the
algorithm will not be presented here.
The computational semantic example solutions would be synthesized in the following manner. Order-1 nodes would be constructed first, exactly the same as before:
= {
}
= {
}
= {
}
= {
}
= {
}
Assuming a list of the variables as in Figure 8, the order-2 solution set is constructed the same as for
SS-1, except only solutions which utilize adjacent variables are
allowed:
= {(ORG,T-O),(ORG,OBT)}
= {(T-O,ORG),(OBT,ORG)} ;; eliminate (T-O,HUM),(OBT,HUM)
= {¯(HUM,COST),(HUM,BEN),(HUM,PUR),(HUM,DUR),
(ORG,COST),(ORG,BEN),(ORG,PUR),(ORG,DUR)}
= {(COST,MON)} ;; eliminate (BEN,MON),(PUR,MON),(DUR,MON)
Level 3 solutions are then synthesized from these:
= {(ORG,T-O,ORG),(ORG,OBT,ORG)}
= {¯(T-O,ORG,COST),(T-O,ORG,BEN),(T-O,ORG,PUR),(T-O,ORG,DUR),
(OBT,ORG,COST),(OBT,ORG,BEN),(OBT,ORG,PUR),(OBT,ORG,DUR)}
= {(HUM,COST,MON),(ORG,COST,MON)}
Level 4 solutions follow:
= {¯(ORG,T-O,ORG,COST),(ORG,T-O,ORG,BEN),(ORG,T-O,ORG,PUR),
(ORG,T-O,ORG,DUR),(ORG,OBT,ORG,COST),(ORG,OBT,ORG,BEN),
(ORG,OBT,ORG,PUR),(ORG,OBT,ORG,DUR)}
= {(T-O,ORG,COST,MON),(OBT,ORG,COST,MON)}
Finally, the correct solution set is generated:
= {(ORG,T-O,ORG,COST,MON),(ORG,OBT,ORG,COST,MON)}
Propagation, as in SS-FREUDER, can be added. For example, once the order-2 solutions are calculated above, it can be deduced that the assignment <J,HUM> is incompatible with all assignments to variable A, and the assignments <F,BEN>, <F,PUR> and <F,DUR> are incompatible with variable T. This information can be propagated downward to order-1 solutions to give:
= {
}
= {
}
= {
}
= {
}
= {
}
This can then be upward propagated to order-2 solutions to give:
= {(ORG,T-O),(ORG,OBT)}
= {(T-O,ORG),(OBT,ORG)}
= {(ORG,COST)}
= {(COST,MON)}
Higher order solutions follow:
= {(ORG,T-O,ORG),(ORG,OBT,ORG)}
= {(T-O,ORG,COST),(OBT,ORG,COST)}
= {(ORG,COST,MON)}
= {(ORG,T-O,ORG,COST),(ORG,OBT,ORG,COST)}
= {(T-O,ORG,COST,MON),(OBT,ORG,COST,MON)}
= {(ORG,T-O,ORG,COST,MON),(ORG,OBT,ORG,COST,MON)}
The major benefit of SS-TSANG is that the number of solution sets at each level is minimized. Also important is the fact that this algorithm is ideal for parallel implementations (see [Tsang and Foster, 1990]). There are two disadvantages:
= {(MON,ORG)}
= {(ORG,T-O),(ORG,OBT)}
= {(T-O,ORG),(OBT,ORG)} ;; eliminate (T-O,HUM),(OBT,HUM)
= {¯(HUM,COST),(HUM,BEN),(HUM,PUR),(HUM,DUR),
(ORG,COST),(ORG,BEN),(ORG,PUR),(ORG,DUR)}
Because the variable T is no longer adjacent to F, it will not be able to disambiguate it. Propagation will be of no help either, since it is dependent on discovering that certain values of F are not compatible with T. Thus, the ambiguity, under this ordering, will be carried all the way up until the final solution, the order-5 solutions, are synthesized.
Tsang states [Tsang, 1993] that the efficiency of his algorithm can be improved by giving the nodes a certain order. Preferred orderings, he suggests, can be obtained by applying some of the general variable ordering techniques discussed below in the ``Other Strategies for CSPs'' section. Specifically, he suggests using a Minimal Bandwidth Ordering (MBO). This idea is adopted and expanded upon in our work.