as follows. After a variable x with domain D(x) = {a1, a2, ..., ad} **is selected,** d branches are created, each one corresponding to a value assignment of x**. In the**
first branch, value a1 is assigned to x **and constraint propagation is triggered.**
If this branch fails, a1 is removed from D(x**). Then the assignment of** a2 to x is made (second branch), and so on. If all d **branches fail then the algorithm**
backtracks. An example of a search tree explored with d**-way branching is shown** in Figure 1a.

In 2-way branching, after a variable x and a value ai ∈ D(x**) are selected,**
two branches are created. In the left branch aiis assigned to x**, or in other** words the constraint x=ai**is added to the problem and is propagated. In the** right branch the constraint x 6= ai**is added to the problem and is propagated. If**
there is no failure then any variable can be selected next (not necessarily x**). If**
both branches fail then the algorithm backtracks. Figure 1b shows a search tree explored with 2-way branching.

There are two differences between these branching schemes. In 2-way branching, if the branch assigning a value ai to a variable x **fails then the removal of** ai from D(x) is propagated. Instead, d**-way branching tries the next available value**
aj of D(x). Note that the propagation of aj subsumes the propagation of ai's removal. In 2-way branching, after a failed branch corresponding to **an assignment**
x=ai, and assuming the removal of ai from D(x**) is then propagated successfully, the algorithm can choose to branch on any variable (not necessarily** x),
according to the variable ordering heuristic. In d**-way branching the algorithm**
has to again branch on x after x=ai **fails.**

![0_image_0.png](0_image_0.png)

Another option, that originates from numerical CSPs, is dichotomic **domain**
splitting **[4]. This method proceeds by splitting the current domain of the selected** variable into two sets, usually based on the lexicographical ordering **of the values.** Once the domain has been split, the second set of values is removed from the domain and this removal is propagated. In this way branching is performed on the two created sets and the branching factor is reduced to two. However, domain