authors 
Galle, Per 
year 
1987 
title 
Branch & Sample : Systematic Combinatorial Search without Optimization 
source 
73 p. 1987. DIKU Research Report No. 87/5. CADLINE has abstract only 
summary 
Many constraint satisfaction problems are combinatorically explosive, i.e. have far too many solutions. Optimization techniques may help in selecting solutions for consideration, but a reasonable measure of optimality is not always at hand. The branch & sample algorithm is presented as an alternative to optimization. If the constraints themselves limit the solution set sufficiently, the algorithm finds all solutions, but otherwise a suitable number of solutions (determined by the user) is generated, such that each new solution has a maximal distance to those already generated. The distance measure used is a so called ultrametric distance expressible in terms of the search tree: solutions are viewed as mtuples of fixed length, each of whose m decision variables corresponds to a level in the search tree. The distance between two solutions is the number of edges from their leaf nodes to the closest common predecessor node in the tree. For problems whose decision variables depend on each other (as is often the case) the set of solutions generated in this way corresponds well to the intuitive notion of a 'representative sample.' The principles of Branch & Sample are first introduced informally, then the algorithm is developed by stepwise refinement, and two examples of its use are given. A fully tested applicationindependent implementation of the algorithm in C is given as an appendix 
keywords 
algorithms, combinatorics, search, constraints, floor plans, layout, synthesis, architecture 
series 
CADline 
references 
Contenttype: text/plain

last changed 
1999/02/12 14:08 
