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.
It is important to realize that solution synthesis, in itself, is simply a way to organize search that happens to be useful when all solutions are required. One could just as well perform a depth first search and, when a solution is found, backtrack and continue searching for more answers. Solution synthesis techniques remove the need for backtracking since all possible answers are calculated at each synthesis level. Furthermore, solution synthesis can be used to focus the effects of other methods, most notably constraint satisfaction. (Freuder, 1978) introduced solution synthesis and (Tsang & 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 section 3.