# Adaptive Branching For Constraint Satisfaction Problems Thanasis Balafoutis And **Kostas Stergiou**1

Abstract.

The two standard branching schemes for CSPs are d**-way**
and 2-way branching. Although it has been shown that in theory the latter can be exponentially more effective than the former, there is a lack of empirical evidence showing such differences. To investigate this, we initially make an experimental comparison of the two branching schemes over a wide range of benchmarks. Experimental results verify the theoretical gap between d**-way and 2-way branching as we move**
from a simple variable ordering heuristic like dom **to more**
sophisticated ones like dom/ddeg. However, perhaps surprisingly, experiments also show that when state-of-the-art variable ordering heuristics like dom/wdeg are used then d**-way**
can be clearly more efficient than 2-way branching in many cases. Motivated by this observation, we develop two generic heuristics that can be applied at certain points during search to decide whether 2-way branching or a restricted version of 2-way branching, which is close to d**-way branching, will**
be followed. The application of these heuristics results in an adaptive branching scheme. Experiments with instantiations of the two generic heuristics confirm that search with adaptive branching outperforms search with a fixed branching scheme on a wide range of problems.

## 1 Introduction

Most complete algorithms for CSPs are based on exhaustive backtracking search interleaved with constraint propagation. Search is typically guided by variable and value ordering heuristics and makes use of either a "d**-way" or a "2-way"**
branching scheme. In the former case, after a variable x **with**
domain {a1, . . . , ad} is chosen, d **branches are built, each one**
corresponding to one of the d **possible value assignments of** x. In the latter case, after a variable x **is chosen, its values are**
assigned through a sequence of binary choices. The first choice point creates two branches, corresponding to the assignment of a1 to x (left branch) and the removal of a1 **from the domain** of x **(right branch). 2-way branching was described by Freuder**
and Sabin within the MAC algorithm [8] and in theory it can achieve exponential savings in search effort compared to d**way branching [5]. Indeed, 2-way is the standard branching**
scheme of most constraint solvers.

Despite the theoretical result of [5], the few experimental studies comparing 2-way and d-way branching have not dis-1 **Department of Information & Communication Systems**
Engineering University of the Aegean, Greece, email:
{abalafoutis,konsterg}**@aegean.gr**
played significant differences between them. Park showed that 2-way and d**-way display very similar performance when the** smallest domain variable ordering heuristic (VOH) is used [6],
while Smith and Sturdy showed that 2-way outperforms d**-way**
when searching for all solutions, albeit not considerably (an average speed-up of 30% was reported) [9]. The reason for this "discrepancy" between theory and experiments is that the experimental studies have considered a "restricted" form of 2-way branching where the variable branched on after the successful propagation of a value removal is always the current variable. This is also the default branching scheme of most constraint solvers. Importantly, "full" 2-way branching as described in [8], allows for a different variable to be chosen.

In this paper we first make a detailed experimental comparison between 2-way branching, in both its restricted and full versions, and d-way branching, under a variety of different VOHs. Results show that the d**-way and restricted 2-**
way branching schemes are closely matched across the different VOHs, with d**-way being slightly more cost effective.**
However, confirming the theoretical results, exponential differences in favor of full 2-way branching are observed as soon as we move from a simple heuristic like smallest domain (dom)
to more sophisticated ones like domain over dynamic degree (dom/ddeg**). Perhaps surprisingly, when state-of-the-art**
conflict-driven heuristics, like dom/wdeg**, are used, significant**
differences in favor of d**-way (and restricted 2-way) are also**
observed. This is because in some cases the VOH mistakenly chooses to branch on a variable other than the current one after the successful propagation of a value removal. This can divert search away from a hard part of the search space, resulting in increased search effort.

Motivated by this observation, we develop two generic heuristics that can be applied at successful right branches once the VOH chooses to branch on a variable other than the current one. At this point the heuristics are used to decide whether the advice of the VOH will be followed or not. The application of these heuristics results in an adaptive branching scheme that dynamically switches between 2-way branching and its restricted version (which is close to d**-way branching). Both of our heuristics can be used in tandem with any**
backtracking search algorithm and VOH. The first heuristic is based on measuring the difference between the scores that the VOH assigns to its selected variable and the current variable. The VOH is followed only if the difference is sufficiently large.

As a downside, this heuristic requires some tuning to optimize its performance. The second heuristic is based on the use of a secondary advisor to decide if the VOH will be followed, and