
| Table 6: Cpu times (t), and nodes (n) from boolean problems. Best cpu time is in bold. Instance d/wdeg d/wdeg d/wdeg Impact N ode Impact   | alldel   | fully   |                   |         |          |      |      |       |       |
|--------------------------------------------------------------------------------------------------------------------------------------------|----------|---------|-------------------|---------|----------|------|------|-------|-------|
| r.probe                                                                                                                                    | RSC      | Impact  | RSC               | by #del | assigned |      |      |       |       |
| jnh01                                                                                                                                      | t        | 10,2    | 95,2 (3,5)        | 14,2    | 2,2      | 13,2 | 13   | 4,2   | 6,2   |
| (sat)                                                                                                                                      | n        | 970     | 5215 (362)        | 515     | 100      | 100  | 100  | 481   | 692   |
| jnh17                                                                                                                                      | t        | 3,1     | 57,3 (0,5)        | 18,8    | 1,9      | 10,1 | 9,9  | 1,4   | 1,5   |
| (sat)                                                                                                                                      | n        | 477     | 4914 (189)        | 1233    | 132      | 131  | 131  | 216   | 204   |
| jnh201                                                                                                                                     | t        | 3       | 79,6 (2,1)        | 3,3     | 2,6      | 11   | 10,7 | 1,13  | 1,14  |
| (sat)                                                                                                                                      | n        | 336     | 5222 (121)        | 168     | 177      | 180  | 180  | 179   | 178   |
| jnh301                                                                                                                                     | t        | 33,4    | 121 (14,5)        | 38,2    | 2,2      | 5,7  | 5,5  | 7     | 8     |
| (sat)                                                                                                                                      | n        | 2671    | 6144 (1488)       | 1541    | 110      | 108  | 108  | 608   | 787   |
| aim-50-1-                                                                                                                                  | t        | 0,15    | 0,43 (0,13)       | 0,21    | 0,82     | 0,49 | 0,5  | 0,07  | 0,08  |
| 6-unsat-2                                                                                                                                  | n        | 1577    | 6314 (1404)       | 1412    | 6774     | 474  | 474  | 691   | 474   |
| aim-100-1-                                                                                                                                 | t        | 0,34    | 1,47 (1,05)       | 1,42    | 91       | 4,3  | 6,3  | 0,16  | 0,2   |
| 6-unsat-1                                                                                                                                  | n        | 3592    | 17238 (10681)     | 7932    | 697503   | 2338 | 3890 | 1609  | 1229  |
| aim-200-1-                                                                                                                                 | t        | 0,76    | 1,28 (0,47)       | 2,1     | 1,66     | 1,9  | 1,8  | 0,24  | 0,26  |
| 6-sat-1                                                                                                                                    | n        | 4665    | 11714 (3236)      | 1371    | 4747     | 213  | 213  | 1756  | 1442  |
| aim-200-1-                                                                                                                                 | t        | 1,9     | 3,2 (2,4)         | 5,3     | 105,9    | 4,8  | 8,5  | 0,19  | 0,23  |
| 6-unsat-1                                                                                                                                  | n        | 12748   | 26454 (16159)     | 28548   | 436746   | 1615 | 3654 | 1255  | 1093  |
| pret-60-                                                                                                                                   | t        | 1255    | 1385 (1385)       | > 1h    | 3589     | > 1h | > 1h | 1027  | 1108  |
| 25 (unsat)                                                                                                                                 | n        | 44,6M   | 44,777M (43,773M) | -       | 95,4M    | -    | -    | 42,5M | 43,8M |
| dubois-20                                                                                                                                  | t        | 1196    | 1196 (1196)       | > 1h    | > 1h     | > 1h | > 1h | 1004  | 1245  |
| (unsat)                                                                                                                                    | n        | 44,9M   | 44,461M (44,457M) | -       | -        | -    | -    | 40,5M | 43,8M |
| Averaged cpu time                                                                                                                          | t        | 250,3   | 294               | 857,1   | -        | -    | -    | 204,5 | 237   |

## 4.5. Non-Binary Instances

In this set of experiments we have included problems with non-binary constraints. The first three instances are from the chessboard coloration problem.

This problem is the task of coloring all squares of a chessboard composed by r rows and c columns. There are exactly n available colors and the four corners of any rectangle extracted from the chessboard must not be assigned the same color. Each instance is denoted by cc-r-c-n. These instances have maximum arity of 4.

The next two instances are from the academic problem "All Interval Series"
(See prob007 at http://www.csplib.org) which have maximum arity of 3, while the last three instances are from a Renault Megane configuration problem where symbolic domains have been converted to numeric ones. The renault instances have maximum arity of 10.

Results are presented in Table 5. Here again the conflict-driven heuristics have the best performance in most cases. The Impact based heuristics have the best cpu performance in two instances (cc-15-15-2 and series-16), but on the other hand they cannot solve 4 instances within the time limit.

We must also note here that although the "node impact" and "impact RSC"
heuristics are slow on chessboard coloration instances, they visit less nodes.

In general, with impact based heuristics there are cases where we can have a consistent reduction in number of visited nodes, albeit at the price of increasing the running time.

Random probing is very expensive for non-binary problems, especially when