Section 5, γ can be learned offline from a set of problem instances of a certain kind for the given implementation of the search algorithm and the solution counting heuristic.

Algorithm 1 implements rational value ordering. The procedure receives problem instance csp with assigned values for variables X1*, ..., X*k−1, variable Xk to be ordered, and estimate N of the number of solutions of the problem instance
(line 1); N is computed at the previous step of the backtracking algorithm as the solution count estimate for the chosen assignment for Xk−1, or, if k = 1, at the beginning of the search as the total solution count estimate for the instance.

Solution counts estimates ni for some of the assignments are re-computed (lines 4–9), and then the domain of Xk, ordered by non-increasing solution count estimates of value assignments, is returned (lines 11–12).

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

10: **end while**

## 5 Empirical Evaluation

Specifying the algorithm parameter γ is the first issue. γ should be a characteristic of the implementation of the search algorithm, rather than of the problem instance; it is also desirable that the performance of the algorithm not be too sensitive to fine tuning of this parameter.

Most of the experiments were conducted on sets of random problem instances generated according to Model RB [Xu and Li, 2000]. The empirical evaluation was performed in two stages. In the first stage, several benchmarks were solved for a wide range of values of γ, and an appropriate value for γ was chosen. In the second stage, the search was run on two sets of problem instances with the chosen γ, as well as with exhaustive deployment, and with the minimum conflicts heuristic, and the search time distributions were compared for each of the value ordering heuristics.

The AC-3 version of MAC was used for the experiments, with some modifications [Sabin and Freuder, 1997]. Variables were ordered using the maximum degree variable ordering heuristic.2 The solution counting heuristic was based on the solution count estimate proposed in [Meisels *et al.*,
2A dynamic variable ordering heuristic, such as dom/deg, may result in shorter search times in general, but gave no significant improvement in our experiments; on the other hand, static variable ordering simplifies the analysis.

1997]. The source code is available from http://ftp.

davidashen.net/vsc.tar.gz.

## 5.1 Benchmarks

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

CSP benchmarks from CSP Solver Competition 2005
[Boussemart *et al.*, 2005] were used. 14 out of 26 benchmarks solved by at least one of the solvers submitted for the competition could be solved with 30 minutes timeout by the solver used for this empirical study for all values of γ: γ = 0 and the exponential range γ ∈ {10−7, 10−6*, ...,* 1}, as well as with the minimum-conflicts heuristic and the pAC heuristic.

Figure 1.a shows the mean search time of VOI-driven solution count estimate deployment T*V SC* normalized by the search time of exhaustive deployment TSC (γ = 0), for the minimum conflicts heuristic TMC , and for the pAC heuristic T*P AC* . The shortest search time on average is achieved by VSC for γ ∈ [10−4, 3 · 10−3] (shaded in the figure) and is much shorter than for SC (mean T*V SC* (10−3)
TSC ≈ 0.45); the improvement is actually close to getting all the information provided by the heuristic without paying the overhead at all.

For all but one of the 14 benchmarks the search time for VSC
with γ = 3 · 10−3is shorter than for MC. For most values of γ, VSC gives better results than MC ( TV SC
TMC< 1). pAC
always results in the longest search time due to the computational overhead.

Figure 1.b shows the mean number of backtracks of VOIdriven deployment N*V SC* normalized by the number of backtracks of exhaustive deployment NSC , the minimum conflicts