
| AC 7   | RPC2     | PIC2   | Max-RPC1   | SAC1 SRPC1   | N IC 1   |
|--------|----------|--------|------------|--------------|----------|
| Scen   |          |        |            |              |          |
| Scen   |          |        |            |              |          |
| Scen   | time out |        |            |              |          |

by a level from   to    The level   corresponds to hard constraints  and levels from   to have a decreasing cost of violation  For each problem ScenXX  resp  GraphXX   we call ScenXX   ScenXX   ScenXX   and ScenXX   resp  GraphXX   GraphXX  
GraphXX
and GraphXX    the problems of satisfaction obtained by considering the problem ScenXX
resp GraphXX with only the constraints of level to      to      to to and respectively In this experimental evaluation  we consider both the cpu time performances and the percentage of values deleted by the local consistencies studied The algorithms used are AC
RPC  Debruyne  Bessière Bessiere Freuder   Régin a PIC  Debruyne Max RPC   Debruyne    Bessière a the singleton arc consistency algorithm of  Debruyne    Bessière       b   SAC    based on AC   a SRPC algorithm based on RPC
SRPC
and the NIC algorithm proposed in  Freuder    Elfe NIC   using FC
as in Freuder Elfe CBJ Prosser heuristic  minimal domain first  in which ties are broken by choosing the variable with the hhighest degree in the constraint graph Frost    Dechter           Bessière Regin AI
these algorithms have been modified to stop as soon as a domain wipe out occurs  We do not show results on strong PC in this section because on these large problems it requires often more than our   hours time out limit  These algorithms have been tested on each ScenXX Scen XX X GraphXX and GraphXX X problem using a Sun UltraSparc Ili Mhz For sake of clarity we only show the results on some representative problems 6.1.1 RESULTS ON PROBLEMS ON WHICH ALL THE STUDIED LOCAL CONSISTENCIES HOLD
(CF. T A B L E 2)
If all the local consistencies studied hold on a constraint network all the corresponding filtering algonthms are useless They waste time to check whether the local consistencies hold without deleting any inconsistent value  On these problems  the stronger the local consistency is  the more important is the time wasted We can see the consequence of the exponential worst case time complexity of NIC     On most of these problems  NIC  requires a reasonable cpu time  But as we can see on the problem Scen a combinatorial explosion can lead to really prohibitive cpu time for NIC

## 6.1.2 Results On Arc Inconsistent Problems (Cf. Table 3)

When arc consistency is sufficient to detect the inconsistency of the problem stronger local consistencies are not always more costly On Figure we can see that Max RPC has often the best cpu time performances and on Graph  for example AC  is one of the