Usually, a branching strategy is defined on a sequence
*x*_{1},..., *x*_{n} 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*, 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.

Andreas Rossberg 2006-08-28