Figure 11: Graph Coloring: maximize the number of reds.
The weakness of previous solution synthesis algorithms is that they do not directly decrease problem complexity. Constraint satisfaction methods used in combination with solution synthesis indirectly aid in decreasing complexity, and variable ordering techniques such as MBO try to direct this aid, but complexity is still driven by the number of exhaustive solutions available at each synthesis. In effect, solution synthesis has been used simply as a way to maximize the disambiguating power of constraint satisfaction for optimization problems.
Instead of concentrating on constraints, HG focuses on the optimization aspect and uses that to guide solution synthesis. The key technique used for optimization is branch-and-bound. Consider the subgraph of a coloring problem shown on the left side of Figure 11. Coloring problems are constraint satisfaction problems with the simple constraint that no two adjacent nodes can have the same value (adjacent nodes are connected by arcs in this graph format). For our purposes, we can turn this type of problem into an optimization problem by requiring the solution to contain as many reds as possible. In this subgraph, only vertex A has constraints outside the subgraph. What this tells us is that by examining only this subgraph, we cannot determine the correct value for vertex A, since there are constraints we are not taking into account. However, given a value for vertex A, we can optimize each of the other vertices with respect to that value. Hunter-Gatherer, then, will partition a graph into subgraphs (see below for details), process and optimize each subgraph independently, and then use solution synthesis techniques to combine the results from the subgraphs.
Figure 12: Three steps for subgraph optimization.
The optimization stage is done in three steps. First, exhaustively determine all of the combinations of values for the vertices in the subgraph. Next, use constraint satisfaction to eliminate impossible combinations. Finally, for each possible value of the vertex with constraints outside the subgraph, determine the optimal assignments for the other vertices. Figure 12 illustrates this process. Step one exhaustively combined all of the possible values for each node in the subgraph. Notice that many of these combinations, such as (r,r,r,r), are not legal sub-answers since adjacent nodes have the same value. Step two used constraint satisfaction techniques to remove these illegal combinations (and possibly others, via a dynamic application of AC-4). Step 3 then retained a combination for each possible value of vertex A, each optimized so that the maximum number of reds appear. Now, no matter what value node A is assigned in the end, we know the optimal values for nodes B, C and D that correspond to it. After step 3, we say that the subgraph has been reduced to its optimal set of partial answers.
Figure 13: Subgraph: maximize the number of reds.
Now consider what happens if, instead of having a single vertex constrained outside the subgraph, two vertices are constrained outside the subgraph, as in Figure 13. In this case, the assignment of correct values for both Vertices A and D must be deferred until later. In the branch-and-bound reduction phase, all possible combinations of values for vertices A and D must be retained, each of which can be optimized with respect to the other vertices. Phase three for this subgraph would yield 4*4=16 combinations (actually less, since 4 of the 16 combinations assign the same value to A and D, violating the coloring constraint).
Solution synthesis is used to combine results from subgraphs or to add individual vertices onto subgraphs (we postpone the discussion of graph decomposition to section 3.2). Figure 14 shows an example of combining the subgraph from Figure 13 with two additional vertices, E and F. Step 1 in the combination process is to take all of the outputs from the input subgraph, 16 in this case, and combine them exhaustively with all the possible values of the input vertices, or 4 each. This gives a total complexity for step 1 of 16 * 4 * 4 = 256. Constraint satisfaction can then be applied as usual. In the resulting synthesized subgraph, only vertex A has constraints outside the subgraph (assuming vertices E and F have no other constraints, as shown). The output of step 3, therefore, will contain 4 optimized answers, one for each of the possible values of A.
Synthesis of two (or more) subgraphs into one proceeds similarly. All of the step 3 outputs of each input subgraph are exhaustively combined. After constraint satisfaction, step 3 reduction occurs, yielding the output of the synthesis. Figure 15 illustrates how subgraphs are created and processed by the solution synthesis algorithms. The smallest subgraphs, 1, 2 and 3, are processed first. Each is optimized as described above. Next, smaller subgraphs are combined, or synthesized into larger and larger subgraphs. In Figure 15, subgraphs 2 and 3 are combined to create subgraph 4. After each combination, the resulting subgraph typically has one or more additional vertices that are no longer constrained outside the new subgraph. Therefore, the subgraph can be re-optimized, with its fully reduced set of sub-answers being the input to the next higher level of synthesis. This process continues until two or more subgraphs are combined to yield the entire graph. In Figure 15, subgraphs 1 and 4 are combined to yield subgraph 5, which contains the entire problem.
Figure 15: Subgraph Construction
Note that the complexity of the processing described up to this point is dominated by the exhaustive listing of combinations in step 1. With this in mind, subgraphs are constructed to minimize this complexity (see below for a discussion of how this is accomplished in non-exponential time). For this reason, our solution synthesis will be directed at combining subgraphs created to minimize the total effect of all the step 1's. This involves limiting the number of inputs to the subgraph as well as maximizing the branch-and-bound reductions (which in turn will help minimize the inputs to the next higher subgraph). This outlook is the central difference between this methodology and previous efforts at solution synthesis, all of which attempted to maximize the effects of early constraint disambiguation. The pruning driven by this branch-and-bound method typically overwhelms the contribution of constraint satisfaction (see below for actual results).
The other difference between this approach and previous solution synthesis applications is the arrangements of inputs at each synthesis level. Tsang and Freuder both combine pairs of variables at the lowest levels. These are then combined with adjacent variable pairs at the second level of synthesis, and so on. HG removes this artificial limitation. Subgraphs are created which maximize branch-and-bound reductions. Two or more subgraphs are then synthesized with the same goal - to maximize branch-and-bound reductions. In fact, single variables are often added to previously analyzed subgraphs to produce a new subgraph.
