heuristic NMC , and for the pAC heuristic NpAC . VSC causes less backtracking than MC for γ ≤ 3·10−3( N*V SC*
NMC
< 1). pAC
always causes less backtracking than other heuristics, but has overwhelming computational overhead.

Figure 1.c shows C*V SC* , the number of estimated solution counts of VOI-driven deployment, normalized by the number of estimated solution counts of exhaustive deployment CSC . When γ = 10−3and the best search time is achieved, the solution counts are estimated only in a relatively small number of search states: the average number of estimations is ten times smaller than in the exhaustive case
(mean C*V SC* (10−3)
CSC ≈ 0.099, median C*V SC* (10−3)
CSC ≈
0.048).

The results show that although the solution counting heuristic may provide significant improvement in the search time, further improvement is achieved when the solution count is estimated only in a small fraction of occasions selected using rational metareasoning.

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

## 5.2 Random Instances

Based on the results on benchmarks, we chose γ = 10−3, and applied it to two sets of 100 problem instances. Exhaustive deployment, rational deployment, the minimum conflicts heuristic, and probabilistic arc consistency were compared.

The first, easier, set was generated with 30 variables, 30 values per domain, 280 constraints, and 220 nogoods per constraint. Search time distributions are presented in Figure 2.a.

The shortest mean search time is achieved for rational deployment, with exhaustive deployment next ( T SC
T *V SC*
≈ 1.75),
followed by the minimum conflicts heuristic ( T MC
T *V SC*
≈ 2.16)
and probabilistic arc consistency ( T pAC
T *V SC*
≈ 3.42). Additionally, while the search time distributions for solution counting are sharp ( max TSC
T SC≈ 1.08, max T*V SC*
T *V SC*≈ 1.73), the distribution for the minimum conflicts heuristic has a long tail with a much longer worst case time ( max T*V SC*
T *V SC*≈ 5.67).

The second, harder, set was generated with 40 variables, 19 values, 410 constraints, 90 nogood pairs per constraint.

Search time distributions are presented in Figure 2.b. As with the first set, the shortest mean search time is achieved for rational deployment: T SC
T *V SC*≈ 1.43, while the relative mean search time for the minimum conflicts heuristic is much longer: T MC
T *V SC*≈ 3.45. The probabilistic arc consistency heuristic resulted again in the longest search time due to the overhead of computing relative solution count estimates by loopy belief propagation: max T*V SC*
T *V SC*≈ 3.91.

Thus, the value of γ chosen based on a small set of hard instances gives good results on a set of instances with different parameters and of varying hardness.

## 5.3 Generalized Sudoku

Randomly generated problem instances have played a key role in the design and study of heuristics for CSP. However, one might argue that the benefits of our scheme are specific to model RB. Indeed, real-world problem instances often have much more structure than random instances generated according to Model RB. Hence, we repeated the experiments on randomly generated Generalized Sudoku instances
[Ansotegui ´ *et al.*, 2006], since this domain is highly structured, and thus a better source of realistic problems with a controlled measure of hardness.

The search was run on two sets of 100 Generalized Sudoku instances, with 4x3 tiles and 90 holes and with 7x4 tiles and 357 holes, with holes punched using the doubly balanced method [Ansotegui ´ *et al.*, 2006]. The search was repeated on each instance with the exhaustive solution-counting, VOIdriven solution counting (with the same value of γ = 10−3as for the RB model problems), minimum conflicts, and probabilistic arc consistency value ordering heuristics. Results are summarized in Table 1 and show that relative performance of the methods on Generalized Sudoku is similar to the performance on Model RB.

  \begin{tabular}{|c|c|c|c|c|c|} \hline  & $T_{SC}$, sec & $\left(\frac{T_{YSC}}{T_{SC}}\right)$ & $\left(\frac{T_{MC}}{T_{SC}}\right)$ & $\left(\frac{T_{PAC}}{T_{SC}}\right)$ \\ \hline 4x3, 90 holes & 1.809 & 0.755 & 1.278 & 22.421 \\ \hline 7x4, 357 holes & 21.328 & 0.868 & 3.889 & 3.826 \\ \hline \end{tabular}  
Table 1: Generalized Sudoku

## 5.4 Deployment Patterns

One might ask whether trivial methods for selective deployment would work. We examined deployment patterns of VOIdriven SC with (γ = 10−3) on several instances of different hardness. For all instances, the solution counts were estimated at varying rates during all stages of the search, and the deployment patterns differ between the instances, so a simple deployment scheme seems unlikely.

VOI-driven deployment also compares favorably to random deployment. Table 2 shows performance of VOI-driven