The solver uses d-way branching and can apply any given restart policy. All experiments were run on an Intel dual core PC T4200 2GHz with 3GB RAM.

Concerning the performance of our solver compared to two state-of-the-art solvers, Abscon 109 [24] and Choco [23], some preliminary results showed that all three solvers visited roughly the same amount of nodes, our solver was consistently slower than Abscon, but sometimes faster than Choco. Note that the aim of our study is to fairly compare the various variable ordering heuristics within the same solver's environment and not to build a state-of-the-art constraint solver. Although our implementation is reasonably optimized for its purposes, it lacks important aspects of state-of-the-art constraint solvers such as specialized propagators for global constraints and intricate data structures.

On the other hand, we are not aware of any solver, commercial or not, that offers all of the variable ordering heuristics tested here (see Subsection 4.1).

Concerning the experiments, most results were obtained using a lexicographic value ordering, but we also evaluated the impact of random value ordering on the relative performance of the heuristics. We employed a geometric restart policy where the initial number of allowed backtracks for the first run was set to 10 and at each new run the number of allowed backtracks increased by a factor of 1.5. In addition, we evaluated the heuristics under a different restart policy and in the absence of restarts. Since our solver does not yet support global constraints, we have left experiments with problems that include such constraints as future work.

In our experiments the random probing technique is run to a fixed failurecount cutoff C = 40, and for a fixed number of restarts R = 50 (these are the optimal values from [21]). After the random probing phase has finished, search starts with the failure-count cutoff being removed and the dom/wdeg heuristic used based on the accumulated weights for each variable. According to [21],
there are two strategies one can pursue during search. The first is to use the weights accumulated through probing as the final weights for the constraints.

The second is to continue to increment them during search in the usual way.

In our experiments we have used the latter approach. Cpu time and nodes for random probing are averaged values for 50 runs. For heuristics that use probing we have measured the total cpu time and the total number of visited nodes (from both random probing initialization and final search). In the next tables
(except Table 2) we also show in parenthesis results from the final search only
(with the random probing initialization overhead excluded).

Concerning impacts, we have approximated their values at the initialization phase by dividing the domains of the variables into (at maximum) four subdomains.

As a primary parameter for the measurement of performance of the evaluated strategies, we have used the cpu time in seconds (t). We have also recorded the number of visited nodes (n) as this gives a measure that is not affected by the particular implementation or by the hardware used. In all the experiments, a time out limit has been set to 1 hour.

In Section 4.1 we give some additional details on the heuristics which we have selected for the evaluation. In Section 4.2 we present results from the radio link