Branching Strategies

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 x₁,..., 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$\le$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.