Freuder (1978) introduced Solution Synthesis (SS) as a means to ``gather up'' all solutions for a CSP without resorting to traditional search methods. Freuder's algorithm (SS-FREUDER) created a set of two-variable nodes that contained combinations of every two variables. These two-variable nodes were then combined into three-variable nodes, and so on, until a node containing all the variables, i.e. the solution, was synthesized. At each step, constraints were propagated down and then back up the ``tree'' of synthesized nodes.
Tsang improved on this scheme with the Essex Algorithms (SS-ESSEX). These algorithms assumed that a list of the variables could be made, after which two-variable nodes were created only between adjacent variables in the list. Higher order nodes were then synthesized as usual, starting from the two-variable nodes. Tsang noted that some orderings of the original list would prove more efficient than others, most notably a ``Minimal Bandwidth Ordering'' (MBO), which seeks to minimize the distance between constrained variables.
The work described here extends and generalizes the concept of MBO. The basic idea of synthesizing solution sets one order higher than their immediate ancestors is discarded. Instead, solution synthesis operates with maximally interacting groupings (circles) of variables of any order and extends to the highest levels of synthesizing. Tsang only creates second order nodes from adjacent variables in a list, with the original list possibly ordered to maximize second order interactions. After that, third and higher order nodes are blindly created from combinations of second order nodes. We extend MBO to the higher levels. The circles of co-constrained variables described in the previous section guide the synthesis process from beginning to end.
The main improvement of this approach comes from a recognition that much of the
work in SS-FREUDER and SS-ESSEX was wasted on finding valid combinations of
variables which were not related. Even though relatively few words in a
sentence are connected through constraints, SS-FREUDER looks for valid
combinations of every word pair. Depending on the ordering used, many
irrelevant combinations can also be inspected by SS-ESSEX. Furthermore, the
ESSEX algorithm tends to carry along unneeded ambiguity. If two related
variables are not adjacent in the ESSEX algorithm, their disambiguating power
will not be applied until they happen to co-occur in a higher-order
synthesis.
The
current work combines the efficiency of the ESSEX algorithms with the
early disambiguation power of the Freuder method.
Our SS-GATHERER algorithm only expends energy on variables directly related by constraints. For instance, for the example in Figure 2, three ``base'' circles would be formed:
1. adquirir, grupo roche, dr andreu 2. adquirir, a traves de, compania 3. compania, en, espana
The last two are synthesized into a larger circle:
adq., a traves de, compania, en, espana, su
This is then synthesized with the first ``base'' circle above to give the answer to the complete problem.
The bulk of disambiguation occurs in the lower order circles which were chosen to maximize this phenomenon. The correct solution to the example problem was obtained by SS-GATHERER in only five steps. SS-Freuder uses hundreds of extra nodes for this example and SS-ESSEX, 31 extra nodes. Focusing the synthesizer on circles that yield maximum disambiguation power produces huge savings while still guaranteeing the correct solution.
One objection that could be raised to this process is that more work might be
needed to create higher-level nodes. For instance, if each variable had three
possible values, one needs to test 9 (
) combinations for each second-order
node, but 27 (
) combinations for third order nodes. If two
second-order nodes could be created that would form a third-order node, and
each second order node could be completely disambiguated to a single solution,
then the third order node could be created without any combinatorics, yielding
a total of 18 combinations (9 + 9) that were searched in the case of three
values for each variable. Directly creating the third-order node requires the
27 combinations to be searched. However, if the second order nodes do
not disambiguate, nothing is gained from them. For this reason,
base circles can be further sub-divided into groups of second-order
nodes, if those second-order nodes are connected in the constraint
graph.
The algorithm below accepts a list of Circles, ordered from smaller to larger. Each circle has the sub-circles from which it is made identified.
1 PROCEDURE SS-GATHERER(Circles)2 FOR each Circle in Circles
3 PROCESS-CIRCLE(Circle)
4 PROCEDURE PROCESS-CIRCLE(Circle)
;;Each Circle in form (Vars-in-Circle Sub-Circles)
5 Output-Plans <-- nil
6 Incoming-Non-Circles <-- REMOVE all
variables in Sub-Circles from Vars-In-Circle
7 Non-Circle-Combos <--
Get-Combos(Incoming-Non-Circles)
8 Circle-Combos <--
Combine-Circles(Sub-Circles)
9 FOR each Non-Circle-Combo in Non-Circle-Combos
10 FOR each Circle-Combo in Circle-Combos
;; each incoming circle has consistency
;; info stored in arrays:
11 AC¯-Info <-- access arc constraint
info from input circles
12 Plan <-- add Non-Circle-Combo
to Circle-Combo
;; Plan is a potential solution for this Circle
;; with a value assigned to each variable.
13 IF Arc-Consistent(Plan,AC-Info) THEN
14 Output-Plans <-- Output-Plans + Plan
15 ;; update AC-Info for this circle
16 RETURN Output-Plans
The Get-Combos procedure (line 7) simply produces all combinations of
value assignments for the input variables. This procedure has complexity
O(
), where x is the number of variables in the input
Incoming-Non-Circles, and a is the maximum number of values for a
variable. In the worst case, x will be n; this is the case when
the initial circle contains all the variables and no sub-circles. Of course,
this is simply an exhaustive search, not Solution Synthesis. In practice, the
circles usually contain no more than two variables not involved in input
sub-circles, the exceptions almost always pertaining to the
base circle, in which case the combine-circles procedure does not add
complexity.
The Combine-Circles procedure (line 8) combines all consistent plans already
calculated for each input Sub-Circle. In the worst case, where each
Sub-Circle contained a single variable, and Sub-Circles contained
every variable, then the time complexity would be
O(
), where a is the maximum size of a variable domain. This is
unavoidable, and is the nature of CSPs. However, if the number of circles in
Sub-Circles is limited to c, and each circle has at most p
possible Plans, then the complexity of this step is O(
). This step
dominates the time complexity of SS-GATHERER. The next section illustrates how this
number can be reduced to a ``near'' constant value.
The FOR loops in lines 9 and 10 simply combine the possible Plan-Combos from
the Incoming-Non-Circles with the Circle-Combos calculated for the
Sub-Circles. The worst-case time complexity is no worse than the
worst-case time complexity for either Combine-Circles or Get-Var-Combos. If
Get-Var-Combos produces 
combinations, then Combine-Circles will
produce none, and vice-versa. In practice, Combine-Circles produces
combinations while Plan-Combos produces a constant number of combinations. The total
complexity of PROCESS-CIRCLE is therefore O(
). Again, this number
can be reduced to a ``near'' constant, as shown below. The complexity of
SS-GATHERER, then, is O(
) times the number of circles, which is
proportional to the number of variables, n. If O(
) can be
shown to be a ``near'' constant, then SS-GATHERER has time complexity that is
``near'' linear with respect to the number of variables.
For each synthesis, arc consistency may be performed (line 13). As discussed above, however, un-modified CSP techniques such as arc-consistency are not usually helpful in problems with non binary-valued constraints. The next section presents a computational substitute that will produce similar efficiency for these kinds of problems.