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 7 displays the process for the computational semantic example.

  
Figure 7: 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 7, 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:

1. Full downward propagation is impossible. Downward propagation in SS-FREUDER relies on having information about allowable combinations of sub-solutions. However, SS-TSANG only determines allowable combinations of adjacent nodes; therefore, propagation can only proceed from these nodes. A limited amount of propagation between adjacent nodes is possible. This drawback is related to the next problem.
2. Ambiguity is carried forward needlessly if two constrained variables are far apart in list. Consider what would happen in the computational semantic example if the ordering of variables was changed to (T I A J F). The following order-2 solutions would be obtained:

     = {(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 (1993) states 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 section 2.4. Specifically, he suggests using a Minimal Bandwidth Ordering (MBO). This idea is adopted and expanded upon in our work.