A branching strategy is used when propagation alone is not
strong enough to yield a solution of a constraint problem. After
computing the fixpoint of all propagators, the branching strategy
determines which constraints should be added in order to obtain two or
more branches of the current node in the search tree.
Usually, a branching strategy is defined on a sequence
x1,..., xn
mathend000# of variables. When a
branching step is necessary, the strategy selects a not
yet determined variable in the sequence
and branches on this variable.
There are a few standard possibilities to branch on a
variable x:
- branch with x = l, where l is the least possible value
for x.
- branch with x = u, where u is the largest possible
value for x.
- branch with x = m, where m is a possible value for
x that is in the middle of the least and
largest possible value for x.
- branch with x
m
mathend000# , where m is a possible
value for x that is in the middle of the
least and largest possible value for x (so called
domain splitting).
A naive branching strategy will select the
leftmost undetermined variable in the sequence.
A first-fail branching strategy will select
the leftmost undetermined variable in the
sequence whose domain in the constraint store has minimal
size. In other words, it will select
the leftmost undetermined variable for which the number
of different possible values is minimal.
For most problems in this tutorial,
first-fail strategies yield much smaller
search trees than naive strategies.
Guido Tack
2007-04-26