and bound ends. All algorithms are named by means of the three parameters. For example, algorithm DPI.WORST.BRANCH has parameters Who=dpi, What=worst, and When=branch. For the baseline algorithm, we use the name DPI.RANDOM.TREE.

For every choice of parameter values, 100 problem instances are generated. The results shown are the average over the 100 instances. Also, when it is not specified otherwise, we set n = 10 and m = 5. However, we have similar results (although not shown in this paper for lack of space) for n = 5, 8, 11, 14, 17, and 20. All our experiments have been performed on an AMD Athlon 64x2 2800+, with 1 Gb RAM,
Linux operating system, and using JVM 6.0.1.

## 5 Results

  \begin{tabular}{l l l} \multicolumn{2}{l}{ DP AIL TREE --$\bullet$--} & \multicolumn{2}{l}{ PD1 WQOST MOE --$\bullet$--} & SUALI-BPANUCI --$\bullet$--} \\ DP,WQOST,REE --$\bullet$--} & \multicolumn{2}{l}{ DP1,WQOST,REE --$\bullet$--} & SUALI-WDOE --$\bullet$--} \\ \multicolumn{2}{l}{ DP1,AIL,BPANCH --$\bullet$--} & \multicolumn{2}{l}{ ULAI,BPANCH --$\bullet$--} & SUWOST,BPANCH --$\bullet$--} \\ \multicolumn{2}{l}{ DP1,
In this section we summarize and discuss our experimental comparison of the different algorithms. We first focus on incomplete fuzzy CSPs. We then consider two special cases: incomplete CSPs where all constraints are hard, and incomplete fuzzy temporal problems. In all the experimental results, the association between an algorithm name and a line symbol is shown below.

## 5.1 Incomplete Fuzzy Csps

Figure 4 shows the percentage of elicited preferences when we vary the incompleteness, the density, and the tightness respectively. For reasons ofspace, we show only the results for specific values of the parameters. However, the trends observed here hold in general. It is easy to see that the best algorithms are those that elicit at the branch level. In particular, algorithm SU.WORST.BRANCH elicits a very small percentage of missing preferences (less than 5%), no matter the amount of incompleteness in the problem, and also independently of the density and the tightness. This algorithm outperforms all others, but relies on help from the user. The best algorithm that does not need such help is DPI.WORST.BRANCH. This never elicits more than about 10% of the missing preferences. Notice that the baseline algorithm is always the worst one, and needs nearly all the missing preferences before it finds a necessarily optimal solution. Notice also that the algorithms with What=worst are almost always better than those with What=all, and that When=branch is almost always better than When=node or When=tree.

Figure 5 (a) shows the user's effort as incompleteness varies. As could be predicted, the effort grows slightly with the incompleteness level, and it is equal to the percentage of elicited preferences only when What=all and Who=dp or dpi. For example, when What=worst, even if Who=dp or dpi, the user has to consider more preferences than those elicited, since to identify the worst preference value the user needs to check all of them (that is, those involved in a partial or complete assignment). DPI.WORST.BRANCH requires the user to look at 60% of the missing preferences at most, even when incompleteness is 100%.