### Citation

(PDF)
Vincent Park.
An Empirical Study of
Different Branching Strategies for Constraint Satisfaction Problems.

MMath thesis,
University of Waterloo, School of Computer Science,
2004.

### Abstract

Many real life problems can be formulated as constraint satisfaction
problems (CSPs). Backtracking search algorithms are usually
employed to solve CSPs and in backtracking search the choice of
branching strategies can be critical since they specify how a search
algorithm can instantiate a variable and how a problem can be reduced
into subproblems; that is, they define a search tree. In spite of the
apparent importance of the branching strategy, there have been only a
few empirical studies about different branching strategies and they all
have been tested exclusively for numerical constraints. In this thesis,
we employ the three most commonly used branching strategies in solving
finite domain CSPs. These branching strategies are described as
follows: first, a branching strategy with strong commitment assigns its
variables in the early stage of the search as in k-Way branching; second,
2-Way branching guides a search by branching one side with assigning
a variable and the other with eliminating the assigned value; third,
the domain splitting strategy, based on the least commitment principle,
branches by dividing a variable's domain rather than by assigning a single
value to a variable. In our experiments, we compared the efficiency
of different branching strategies in terms of their execution times
and the number of choice points in solving finite domain CSPs.
Interestingly, our experiments provide evidence that the choice of
branching strategy for finite domain problems does not matter much
in most cases---provided we are using an effective variable ordering
heuristic---as domain splitting and 2-Way branching end up simulating
k-Way branching. However, for an optimization problem with large domain
size, the branching strategy with the least commitment principle can
be more efficient than the other strategies. This empirical study will
hopefully interest other practitioners to take different branching
schemes into consideration in designing heuristics.

**Return to Publications**